[关闭]
@myecho 2018-03-29T13:36:39.000000Z 字数 6281 阅读 828

排序总结

数据结构

首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法

针对昨天面试中出现的问题，今天又把所有的排序算法重写了一遍，加深印象。

  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  6. using namespace std;
  8. //冒泡排序 稳定的
  9. void BubbleSort(int * a, int length) {
  10.     bool change = true;
  11.     for (int i = length - 1; i >= 0 && change; --i) {
  12.         change = false;
  13.         for (int j = 0; j < i; ++j) {
  14.             if (a[j+1] < a[j]) {
  15.                 change = true;
  16.                 int tmp = a[j+1];
  17.                 a[j+1] = a[j];
  18.                 a[j] = tmp;
  19.             }
  20.         }
  21.     }
  22. }
  24. 最好情况比较N-1次，交换0次(有序的情况)，最差情况比较N^2/2次，交换N^2/2次(逆序)
  25. //插入排序 稳定的
  26. void InsertSort(int * a, int length) {
  27.     for (int i = 1; i < length; ++i) {
  28.         for (int j = i; j > 0 && a[j] < a[j-1]; j--)
  29.             exch(a, j, j-1);
  30.          //可二分查找代替，但是虽然比较和查找时间复杂度降低，但是每次需要移动的元素个数与顺序比较和查找是相同的。
  31.     }
  32. }
  34. 平均是N^2/4次比较以及N^2/4次交换，最坏情况下需要N^2/2次比较和N^2/2次交换，最好情况下需要N-1次比较和0次交换(指的是每次比较如果小则交换，而不是将要插入的值右移)
  35. void shellSort(int * a, int length) {
  36.     int N = length;
  37.     int h = 1;
  38.     while (h < N/3) h= 3*h + 1; //1,4,13,40,121,364...
  39.     while (h >= 1) {
  40.         for (int i = h; i < N; i++) {
  41.             //将a[i]插入到a[i-h],a[i-2*H],a[i-3*h]等
  42.             for(int j = i; j >= h && less(a[j],a[j-h]); j-=h)
  43.                 exch(a,j,j-h);
  44.         }
  45.     }
  46. }
  47. 一个有趣的结论是使用如上所示的递增序列时，算法的最坏运行时间不会超过N^(3/2),也属于是不稳定排序算法
  49. //选择排序 不稳定
  50. void SelectSort(int * a, int length) {
  51.     for (int i = length - 1; i >= 0; --i) {
  52.         int k = i;
  53.         for(int j = 0; j < i; ++ j) { 
  54.             if (a[k] < a[j]) k = j;
  55.         }
  56.         if (k != i) {
  57.             int tmp = a[i];
  58.             a[i] = a[k];
  59.             a[k] = tmp;
  60.         }
  61.     }
  62. }
  63. 1. 运行时间与输入无关，都有N次交换以及N^2/2次比较
  64. 2. 数据的移动是最少的，只需要N次交换
  66. //堆排序 不稳定
  67. void HeapAdujst(int * a, int s, int length) { 下沉操作 //调用的必要条件是左右均为最小堆了
  68.     int tmp = a[s];
  69.     int j = 2*s + 1; //1~length时和0~length-1时是不同的
  70.     while (j < length) {
  71.         if ((j < length - 1) && a[j+1] < a[j]) j++;
  72.         if (tmp < a[j]) break;
  73.         else {
  74.             a[s] = a[j]; 
  75.             s = j;
  76.             j = 2*s + 1;
  77.         }
  78.     }
  79.     a[s] = tmp;
  80. }
  82. private void swim(int * a, int s) { //上浮操作
  83.     while (s > 0 && a[(s-1)/2] > a[s]) {
  84.         exch((s-1)/2, s);
  85.         s = (s-1)/2;
  86.     }
  87. }
  89. void HeapSort(int * a, int length) {
  90.     for (int i = length/2; i >= 0; --i) HeapAdujst(a, i, length); //只有这样才满足调用的必要条件 建堆的复杂度是O(N) 证明在:https://www.zhihu.com/question/20729324
  91.     for (int i = length - 1; i >= 0; --i) {
  92.         int tmp = a[i];
  93.         a[i] = a[0];
  94.         a[0] = tmp;
  95.         HeapAdujst(a, 0, i); //最后长度是i
  96.     }
  97. }
  98. 堆排总的时间复杂度为O(N*logN)
  99. 补充:建堆的过程可以上升也可以下沉，下沉时必须保证子树已经是堆的形式，上升时则必须保证目前的上边的树已经是堆的状态了。上升建堆的复杂度是nlogn
  101. //快速排序 不稳定
  102. int partition(int * a, int low, int high) { //从大到小
  103.     int pivotkey = a[low];
  104.     while (low < high) {
  105.         while(low < high && a[high] < pivotkey) high--;
  106.         a[low] = a[high];
  107.         while(low < high && a[low] > pivotkey) low++;
  108.         a[high] = a[low];
  109.     }  //上式中应该尽量把=当做停下扫描的条件，尽管这样可能会不必要的进行一些等值元素的交换，避免在数组包含大量重复值得情况下将左右数组分的不均匀，从而导致运行时间变成平方级别
  110.     a[low] = pivotkey;
  111.     return low;
  112. }
  114. void QuickSort(int * a, int low, int high) {
  115.     if (low < high) {
  116.         int pivotloc = partition(a, low, high);
  117.         QuickSort(a, low, pivotloc - 1);
  118.         //do something on privot
  119.         QuickSort(a, pivotloc + 1, high);
  120.     }
  121. }
  122. 关于快速排序的优化:
  123. 1. 切换到插入排序，将if (low < high)修改为if (high <= low + M) 进行插入排序，5~15之间的任意值在大多数情况下可以令人满意
  124. 2. 三取样切分，取样大小为3，取中间的数作为中枢
  125. 3. 三向切分，适用于存在大量重复元素的数组 http://www.cnblogs.com/kirov/p/5041075.html
  127. 快排非递归版本:http://www.cnblogs.com/zhangchaoyang/articles/2234815.html
  128. 快速排序的稳定化:开额外O(n)空间.每轮partition都直接扫一遍l..r, 小于pivot的放一个数组,大于pivot的放另外一个数组. 然后再合并到原数组当中.这样就是稳定的了
  130. //归并排序 稳定
  131. //将有二个有序数列a[first...mid]和a[mid...last]合并
  132. void Merge(int a[], int first, int mid, int last, int c[]) {
  133.     int i = first, j = mid + 1;
  134.     for (int k = first; k <= last; ++k)
  135.         if (i > mid) c[k] = a[j++]; //左边用尽
  136.         else if (j > last) c[k] = a[i++]; //右边用尽
  137.         else if (a[i] <= a[j]) c[k] = a[i++]; //相等时优先放置前边的，保持稳定性
  138.         else c[k] = a[j++];  //求逆序对时只需要加上一句cnt += mid - i + 1; 即可统计得到逆序对的数目(必须以a[j]为准,不能以a[i]为准会产生重复)
  139.     for (int k = first; k <= last; ++k) {
  140.         a[k] = c[k]; 
  141.     }
  142. }
  144. void MergeSort(int a[], int low, int high, int temp[]) {
  145.     if (low < high) {
  146.         int mid = low + (high - low) / 2; //避免溢出
  147.         MergeSort(a, low, mid, temp);//[low, mid]
  148.         MergeSort(a, mid+1, high, temp); //[mid+1, high]
  149.         Merge(a, low, mid, high, temp);
  150.     }
  151. }
  152. 以上所示为自顶向下的归并排序，也可以使用自底向上的归并排序(如下所示)，子数组的大小分别为1,2,4,8等。
  153. 算法复杂度为N*logN，但是需要O(N)的额外的时间消耗
  155. public static void sort(Comparable[] a) {
  156.     int N = a.length;
  157.     aux = new Comparable[N];
  158.     for (int sz = 1; sz < N; sz = sz + sz) //sz子数组的大小，整体数组的一半
  159.         for (int lo = 0; lo < N - sz; lo += sz + sz) //lo子数组索引
  160.             merge(a, lo, lo + sz -1, Math.min(lo + sz + sz - 1, N - 1));
  161. } 
  162. 自底向上的归并排序适合用链表组织的数据，这种方法只需要重新组织链表就能原地排序，不需要创建任何新的链表结构
  163. 归并排序的优化:
  164. 1. 对小规模子数组使用插入排序
  165. 2. 测试数组是否已经排序 如果a[mid] <= a[mid+1]，我们就认为已经有序，这样可以直接跳过Merge过程
  166. 3. 不将元素复制到辅助数组 需要在递归调用时不断交换输入数组和辅助数组的角色
  167. http://algs4.cs.princeton.edu/22mergesort/MergeX.java.html
  169.  private static void sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
  170.         // if (hi <= lo) return;
  171.         if (hi <= lo + CUTOFF) { 
  172.             insertionSort(dst, lo, hi);
  173.             return;
  174.         }
  175.         int mid = lo + (hi - lo) / 2;
  176.         sort(dst, src, lo, mid);
  177.         sort(dst, src, mid+1, hi);
  179.         // if (!less(src[mid+1], src[mid])) {
  180.         //    for (int i = lo; i <= hi; i++) dst[i] = src[i];
  181.         //    return;
  182.         // }
  184.         // using System.arraycopy() is a bit faster than the above loop
  185.         if (!less(src[mid+1], src[mid])) {
  186.             System.arraycopy(src, lo, dst, lo, hi - lo + 1);
  187.             return;
  188.         }
  189.         merge(src, dst, lo, mid, hi); //merge中仅需要将src中合并到有序到dst中，不需要拷贝的动作了
  190.     }
  192. 非递归的归并排序:
  193. http://www.cnblogs.com/xing901022/p/3671771.html
  195. //桶排序
  196. void BucketSort(int a[], int length, int max) {
  197.     int * bucket = new int [max+1];
  198.     memset(a, 0, sizeof(bucket));
  199.     for (int i = 0; i < length; ++i) bucket[a[i]]++;  //计数
  200.     for (int i = 0, j = 0; i < max; i++) {
  201.         while (bucket[i]-- > 0)
  202.             a[j++] = i;
  203.     }
  204. }
  206. //基数排序
  207. 原理类似桶排序,这里总是需要10个桶,多次使用
  208. 每次循环将一位上的数入桶并进行排序
  209. void RadixSort(int a[], int n, int maxd) {
  210.     int r = 1;
  211.     int * cnt = new int[10];
  212.     int * tmp = new int[10];
  213.     //maxd为最大的位数，比如3000时 maxd为4
  214.     for (int i = 0; i < maxd; ++i) {
  215.         for (int j = 0; j < 10; ++j) cnt[j] = 0;
  216.         for (int j = 0; j < n; ++j) {
  217.             int k = a[j] / r;
  218.             int q = k % 10;
  219.             cnt[q] ++;
  220.         }
  221.         for (int j = 1; j < 10; ++j) {
  222.             cnt[j] += cnt[j - 1]; //计算累积和，为了计算排名
  223.         }
  224.         for (int j = n - 1; j >= 0; j--) {
  225.             int p = a[j] / r;
  226.             int s = p % 10;
  227.             tmp[cnt[s] - 1] = a[j];
  228.             cnt[s] --;
  229.         }
  230.         for (int j = 0; j < n; ++j) {
  231.             a[j] = tmp[j]; //重排序
  232.         }
  233.         r *= 10;
  234.     }
  235. }
  237. //计数排序
  238. 当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。
  240.     public static void countsort(int[] input, int[] output, int k) {  
  241.         // input为输入数组，output为输出数组，k表示有所输入数字都介于0到k之间  
  242.         int[] c = new int[k];
  243.         int len = c.length;  
  244.         for (int i = 0; i < len; i++) {  
  245.             c[i] = 0;  
  246.         } 
  247.         for (int i = 0; i < input.length; i++) {  
  248.             c[input[i]]++;  
  249.         }
  250.         for (int i = 1; i < len; i++) {  
  251.             c[i] = c[i] + c[i - 1];  
  252.         }
  253.         // 把输入数组中的元素放在输出数组中对应的位置上  
  254.         for (int i = input.length - 1; i >= 0; i--) {
  255.             output[c[input[i]] - 1] = input[i];  
  256.             c[input[i]]--; 
  257.         }
  258.     }

补充证明:基于比较的排序算法的下界
实际上应该是lgN!~nlogN 只不过可以将lgN!近似为nlogN
http://www.cnblogs.com/sanghai/p/6378072.html

（比较）排序算法时间的下界：比较排序算法的复杂度下界是 O(nlog(n))

证明
对于n个待排序元素，在未比较时，可能的正确结果有n!种。
在经过一次比较后，其中两个元素的顺序被确定，所以可能的正确结果剩余n!/2种。
依次类推，直到经过m次比较，剩余可能性n!/(2^m)种。
直到n!/(2^m)<=1时，结果只剩余一种。此时的比较次数m为o(nlogn)次。
所以基于排序的比较算法，最优情况下，复杂度是o(nlogn)的。

因为log(n!)的增长速度与 nlogn 相同,即 log(n!)=Θ(nlogn)

证明过程

关于快速排序的实现:
1. image_1brvb1htc9s4id651j1d1d1fn39.png-192.1kB
2. image_1brvb4j4113er9jq2rjq001cp5m.png-178.9kB
我们大多数的实现都是基于第二种改动来的，因为在第2种实现中，我们可以发现其并没有将pivot放入正确的位置，因此出现了递归时左端需要处理p位置的边界情况

两种实现方式的对比:
1. Hoare’s scheme is more efficient than Lomuto’s partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal.
2. Like Lomuto’s partition scheme, Hoare partitioning also causes Quicksort to degrade to O(n^2) when the input array is already sorted, it also doesn’t produce a stable sort.
3. Note that in this scheme, the pivot’s final location is not necessarily at the index that was returned, and the next two segments that the main algorithm recurs on are (lo..p) and (p+1..hi) as opposed to (lo..p-1) and (p+1..hi) as in Lomuto’s scheme.

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注