常用排序方法代码

冒泡排序

通过相邻数据交换达到排序目的

public static void maopao(int[] a){ int temp = 0; for (int i = 0; i < a.length-1; i++) { for (int j = i+1; j < a.length; j++) { if (a[i]>a[j]){ temp = a[i]; a[i]=a[j]; a[j]=temp; } } } for (int t:a ) { System.out.println(t); } }

选择排序

每一步都选取一个极值来重新排列，达成排序

从原始数据中选择一个最小的，跟第一个交换。从剩下的数据中选择一个最小的，跟第二个交换。。。。。。。重复上面的过程知道最后两个数据交换完成。 public static void xuanze(int[] a){ int temp=0; int index=0; for (int i = 0; i < a.length - 1; i++) { index =i; for (int j = i+1; j < a.length; j++) { if (a[j]<a[index]) index=j; //找到最小值的下标 } if (index!=i){ //将最小值和第i个数交换 temp = a[i]; a[i]=a[index]; a[index] = temp; } } for (int t:a) { System.out.println(t);

插入排序

通过对未排序的数据进行逐个插入到合适的位置来达到排序的目的

将数据的前两个进行比较排序。将第三个数与排好序的前两个数比较，插入到合适的位置。。。。。。。重复上面的过程知道最后一个数据插入到合适的位置。

当数据在已有一定顺序的情况下，效率比较高。

public static void charu(int[] a){ int j=0,t=0; for ( int i = 1; i < a.length; i++) { t=a[i]; j=i-1; while (j>=0&&t<a[j]){ a[j+1]=a[j]; j--; } a[j+1]=t; } for (int q:a ) { System.out.println(q); } }

希尔排序 shell排序 缩小增量排序

将那个数据分为n/2个序列，将第1个和第n/2+1 个数据组成一对，然后每一对比较排序。在变为n/4个序列，排序。重复上述过程，知道序列数量变为1，最后执行插入排序达到排序目的。 private static void shell(int[] a) { int j; int temp; for (int r= a.length/2; r >=1; r/=2) { for (int i=r;i< a.length;i++){ temp=a[i]; j=i-r; while (j>=0&&temp<a[j]){ a[j+r]=a[j]; j-=r; } a[j+r]=temp; } } for (int t:a ) { System.out.println(t); } }

快速排序

通过多次比较和交换来实现

设一个分界值，可以是第一个，通过分界值将数据分为左右两部分将大于等于分界值的数据放在右边，小鱼分界值的放在左边。将左右两部分数据分别采用上面的方法排序。直到整个数组排序完成。 private static void kuaisu(int[] a, int left, int right) { int f,t; int rtemp,ltemp; ltemp = 0; rtemp=a.length-1; f = a[(left+right)/2]; while (ltemp<rtemp){ while (a[ltemp]<f){ ltemp++; } while (a[rtemp]>f){ rtemp--; } if (ltemp<=rtemp){ t = a[ltemp]; a[ltemp] = a[rtemp]; a[rtemp]=t; rtemp--; ltemp++; } } if (left<rtemp){ kuaisu(a,left,ltemp-1); } if (ltemp<right){ kuaisu(a,rtemp+1,right); } }

堆排序

包括构造对结构和对排序输出两个过程

public static void dui(int[] a) { int i, j, k; int t; int n = a.length; //堆排序 for (i = n / 2 - 1; i >= 0; i--) { while (2 * i + 1 < n) { j = 2 * i + 1; if ((j + 1) < n) { if (a[j] < a[j + 1]) j++; } if (a[i] < a[j]) { t = a[i]; a[i] = a[j]; a[j] = t; i = j; }else { break; } } } //堆输出 System.out.println("元数据构成的堆"); for (int aa:a ) { System.out.println(aa); } for (i=n-1;i>0;i--){ t=a[0]; a[0]=a[i]; a[i]=t; k=0; while (2*k+1<i){ j=2*k+1; if ((j+1)<i){ if (a[j]<a[j+1]){ j++; } } if (a[k]<a[j]){ t=a[k]; a[k]=a[j]; a[j]=t; k=j; }else { break; } } } System.out.println("结果"); for (int aa:a ) { System.out.println(aa); } }

合并排序

将多个有序数据合成一个有序数据。如果合成的数据只有两个数据，就叫二路合并。

//二路合并 public static void mergeOne(int[] a,int[] b,int n,int len){ int i,j,k,s,e; s=0; while (s+len<n){ e=s+2*len-1; if ((e>=n)){ e=n-1; } k=s; i=s; j=s+len; while (i<s+len&&j<=e){ if (a[i]<=a[j]){ b[k++]=a[i++]; }else { b[k++]=a[j++]; } } while (i<s+len){ b[k++]=a[i++]; } while (j<=e){ b[k++]=a[j++]; } s=e+1; } if (s<n){ for (;s<n;s++){ b[s]=a[s]; } } } public static void Hebing(int[] a,int n){ int h,count,len,f; count = 0; len=1; f=0; int[] p = new int[n]; while (len<n){ if (f==1){ mergeOne(p,a,n,len);//合并两个数组 }else { mergeOne(a,p,n,len);//合并两个数组 } len=len*2; f=1-f; count++; } if (f==1){ for (h=0;h<n;h++){ a[h]=p[h]; } } for (int aa:a ) { System.out.println(aa); } }

效率比较

冒牌排序，平均速度为O( n2 ),最坏的情况也是O( n2 );快速排序，平均速度为O(n log2n ），最坏为O(n^2);选择排序，平均速度为O( n2 )，最坏为O( n2 );堆排序，平均速度为O(n log2n )，最坏为O(n log2n )；插入排序，平均速度为O( n2 ),最坏为O( n2 );Shell排序，平均速度为O( n32 ),最坏为O( n2 )；合并排序，平均速度为O(n log2n )，最坏为O(n log2n )；