算法
是否稳定
是否原地排序
时间复杂度
空间复杂度
备注
选择排序
否
是
N^2
1
插入排序
是
是
介于N~N^2
1
取决于输入元素的排列
希尔排序
否
是
快于上面2个方法
1
快速排序
否
是
NlogN
lgN
运行效率由概率保证
归并排序
是
否
NlogN
N
堆排序
否
是
NlogN
1
三向快速排序
否
是
N~NlogN
lgN
运行效率由概率提供保证，同时也取决与输入元素
冒泡排序性能近似与选择排序· 在最后一项列出 1.选择排序 public static void sort1(){ //将a[]按升序排列 int N = a.length; for(int i = 0; i < N; i++){ //将a[i]和数组中最小的元素交换 int min = i; for(int j = i+1; j<N; j++){ if(a[j]<a[min]){ min = j; //交换a[i]和a[min]位置 int t = a[[min]; a[min]=a[i]; a[i]=t; } } } } } //对于长度位N的数组，选择排序需要大约（N^2/2）次比较和N次交换 //从下标0到N-1的任意i都会进行一次交换和N-1-i次比较，因此总共有N次交换 和 (N-1)+(N-2)+(N-3)+...+2+1=N*(N-1)/2次比较 //数据移动(交换)是所有排序里面最少的，交换次数与数组线性相关 2.插入排序 public static void sort2(){ //将a[]按升序排列 int N = a.length; for(int i = 1; i<N; i++){ //将a[i]插入到a[i-1] a[i-2] a[i-3]...a[1]之中 for(int j = i; j>0; j--){ if(a[j-1] > a[j]){ //交换位置a[j] a[j-1] int t = a[j]; a[j-1] = a[j]; a[j] = t; } } } } //对于1到N-1之间的每一个i，将a[i]与a[0]到a[i-1]中比它小的所有元素依次有序的交换 //在索引i由左向右变化的过程中，它左侧的元素总是有序的，当i到达数组的右端时排序就完成了 //当原数组中倒序的元素数量很少时，插入排序可能比任何排序都快 //在最坏的完全倒序情况下需要 ~N^2/2次比较 和 ~N^2/2次交换 最好的情况下需要N-1次比较和0次交换 3.希尔排序 基于插入排序的改进是排序算法 交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序 使数组中任意间隔为h的元素都是有序的，将数组分为h个子数组 平衡了子数组的规模和有序性 下面例子h=3 public static void sort3(){ //a[]升序排列 int N = a.length; int h =1; while(h < N/3) h = 3*h + 1; //1,4,13,40..... while(h>=1){ //将数组变为有序 for(int i = h; i <N; i++){ //将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]...之中 for(int j =i; j>=h; j= j-h){ if(a[j]<a[j-h]){ //交换位置 int t = a[j]; a[j]=a[j-h]; a[j-h]=t; } } h =h/3; } } } //在最坏情况下 比较次数和N^(3/2)成正比 4.归并排序 归并：即将两个有序的数组归并为一个更大的有序数组 优点：保证任意长度为N的数组排序时间与N*logN成正比 缺点：递归所需的额外内存空间和N成正比 Java的数组排序Arrays类的sort()即实现了归并排序 首先定义一个归并方法merge() public static void merge(int low, int mid, int high){ //将a[lo...mid]和 a[mid+1...high]归并 int i = low; int j = mid + 1; for(int k = low; k<=high; k++){ //将a[low...high]复制到b[low...high] b[k] = a[k]; } for(int k= low; k<=high; k++){ //归并回到a[low..high] if(i>mid) a[k]=b[j++]; else if(j>high) a[k]=b[i++]; else if(b[j]<b[i]) a[k]=b[j++]; else a[k]=b[i++]; } } 自顶向下的归并排序 这段递归代码是归纳证明算法能够正确的将数组排序的基础：如果他能将两个子数组排序，就能通过归并两个子数组将整个数组排序 //对数组a[]排序 public static void sort4(int[] a, int low, int high){ //创建辅助数组并分配空间 private static int[] b = new int[a.length]; //将数组a[low ...high]排序 if(high <= low) return; int mid = low + (high-low)/2; sort4(low,mid);//将左半边排序 sort4(mid+1;high);//将右半边排序 merge(low,mid,high);//归并结果 } 5.自底向上的归并排序 比较适合链表组织的数据 先归并小数组，再成对归并得到的子数组，知道我们将整个数组归并到一起 public static void sort5(int[] a){ //进行lgN次两两归并 int N= a.length; int b[] = new int[N]; for(int sz = 1; sz < N; sz = sz +sz){ for(int low =0; low<N-sz;low+=sz+sz){ merge(low,low+sz-1;Math.min(low+sz+sz-1,N-1); } } } 6.快速排序 快速排序是一种分治排序算法，将一个数组分为2个部分独立排序；快速排序与归并排序是互补的 归并排序进发数组等分成2个数组分别排序，并将有序的子数组归并以将整个数组排序，而快速排序将数组排序的方式则是将当2个子数组都有序时 整个数组有人就自然有序了，其数组切分的位置取决于数组的内容。 public static void sort6(int[] a, int low, int high){ //消除对输入的依赖 StdRandom.shuffle(a); if(high <= low) return; //切分 int j = partition(a,low,high); //将左半部分排序 sort6(a,low,j-1); //将右半部份排序 sort6(a,j+1,high); } //切分方法 public staic int partition(int[] a, int low, int high){ //将数组切分为a[low ..i-1],a[i],a[i+1..high] int i = low, int j = high+1; //左右扫描指针 int[] v = a[low]; //切分元素 while(true){ //扫描左右，检查扫描是否结束并交换元素 while(a[i++]<v) if(i==high) break; while(v<a[--j]) if(j==low) break; if(i>=j) break; int t=a[i]; a[i]=a[i+1]; a[i+1]=t; } //将v=a[j]放入正确的位置 int x = a[low]; a[low] = a[j]; a[j] = t; //a[low...j-1] <= a[j] <= a[j+1..high]达成 return j; } 7.堆排序 数据结构二叉堆能很好的实现优先队列的基本操作 public static void sort7(int[] a){ //sink()方法将a[1]到a[N]的元素排序 int N = a.length; for(int k=N/2; k>=1; k--) sink(a,k,N) while(N>1){ //交换 a[i] 和a[N--]的位置 ex(a,1,N--); sink(a,1,N); } } 8.冒泡排序 static void sort(){ for (int i = 0; i < N; i++){ for (int j = 0 ; j < N - i-1; j++){ if (a[j] > a[j+1]){ int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } }