|
排序算法在程序中会用到很多，这里介绍几种常见的排序方法以及比较
冒泡排序：对一个队列里的数据，挨个进行轮询和交换，每次轮询出一个当前最大或者最小的值放在队尾，然后继续下次轮询，轮询长度-1，就跟冒泡一样，所以称为冒泡排序，运算时间复杂度N平方
选择排序：对一个队列里的数据，选出当前最大或者最小的值，然后将他与队首的数据交换，然后从第二个开始，进行相同的操作，运算时间复杂度N平方，但由于他不像冒泡一样需要不停的交换位置，所以会比冒泡快一些
插入排序：对一个队列里的数据，从第二个开始，与此位置之前的数据进行比较，形成局部有序的队列，循环此操作，直到队尾，运算时间复杂度依然为N平方，但他由于保证了局部的有序性，所以比较的次数会更少一些，相对前两种会更快
希尔排序：其实就是用步长控制的插入排序，希尔排序通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而让数据项可以大幅度移动，这样的方式可以使每次移动之后的数据离他们在最终序列中的位置相差不大，保证数据的基本有序，大大提升了排序速度，运算时间复杂度N*logN
快速排序：对一个队列，以他队尾的数据为基准值，先划分成两块数据，一块都大于这个值，一块小于这个值，然后对这两块进行同样的操作，这是最快的排序方法，运算时间复杂度N*logN
下面是代码：
public static void sort(int[] a) { long time1,time2; int c; time1=System.currentTimeMillis(); // /*冒泡排序*/// for(int i=a.length-1;i>1;i--)// {// for(int j=0;j<i;j++)// {//// if(a[j]<a[j+1])// {// c=a[j];// a[j]=a[j+1];// a[j+1]=c;// }// }// }
// /*选择排序*/// int pos=0;// for(int i=0;i<a.length-2;i++)// {// for(int j=i;j<a.length-1;j++)// {// if(a[pos]<a[j+1])// pos=j+1;// }// c=a[i];// a[i]=a[pos];// a[pos]=c;// pos=i+1;// }
// /*插入排序*/// for(int i=1;i<a.length;i++)// {// c=a[i];// int m=i-1;// while(m>=0&&a[m]<c)// {// a[m+1]=a[m];// m--;// }// a[m+1]=c;// }
// /*希尔排序*/// int h=1;// int m=0;// while(3*h+1<a.length)// h=3*h+1;// while(h>0)// {// for(int i=h;i<a.length;i++)// {// c=a[i];// m=i-h;// while(m>=0&&a[m]<c)// {// a[m+h]=a[m];// m-=h;// }// a[m+h]=c;// // }// h=(h-1)/3;// }
/*快速排序*/ provide(a,0,a.length-1); time2=System.currentTimeMillis(); System.out.println("time:"+(time2-time1)); } /*递归调用划分*/ public static void provide(int[] a,int left,int right) { try { if(right<=left) return; else { /*设置基准点*/ int prov=a[right]; /*取得划分中断点*/ int par=partitionIt(a,left,right,prov); /*对划分后的两边再次划分*/ provide(a,left,par-1); provide(a,par+1,right); } } catch(Exception e) { System.out.println("eer:"+left+"."+right); } } /*划分算法*/ public static int partitionIt(int[] a,int left,int right,int prov) { /*设置左右端点的指针*/ int leftP=left-1; int rightP=right; int c;//用于交换的中间变量 /*当左右指针未相遇时继续操作*/ while(leftP<rightP) { /*当左指针的数据小于基准值时跳出*/ while(leftP<a.length-1&&a[++leftP]>prov) ; /*当右指针的数据大于基准值时跳出*/ while(rightP>leftP&&a[--rightP]<prov) ; /*左右指针都停下时交换数据*/ c=a[leftP]; a[leftP]=a[rightP]; a[rightP]=c; } /*划分结束，将基准点与指针的相遇点交换*/ c=a[rightP]; a[rightP]=a[right]; a[right]=c; return leftP; }
阅读全文(1387) | 回复(1) | 编辑 | 精华
|
