如何实现一个通用的，高性能的排序函数

常见排序算法

pic

选择

如果对小规模数据进行排序，可以选择时间复杂度是 O(n2) 的算法；如果对大规模数据进行排序，时间复杂度是 O(nlogn) 的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。时间复杂度是 O(nlogn) 的排序算法不止一个，我们已经讲过的有归并排序、快速排序，后面讲堆的时候我们还会讲到堆排序。堆排序和快速排序都有比较多的应用，比如 Java 语言采用堆排序实现排序函数，C 语言使用快速排序实现排序函数。

归并排序为什么使用情况不多

优点：

快排在最坏情况下的时间复杂度是 O(n2)，而归并排序可以做到平均情况、最坏情况下的时间复杂度都是 O(nlogn)

缺点：

归并排序并不是原地排序算法，空间复杂度是 O(n)。所以，粗略点、夸张点讲，如果要排序 100MB 的数据，除了数据本身占用的内存之外，排序算法还要额外再占用 100MB 的内存空间，空间耗费就翻倍了。

优化快速排序

快速排序在最坏情况下的时间复杂度是O(n^2)。

出现O(n^2)原因： 分区点选的不合理

如何选分区：

三数取中法

降低取的分区点不合理的概率，夺取几次取中间值，数组较大时可能要考虑“五数取中”或者“十数取中”

随机法

随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选的很差的情况，所以平均情况下，这样选的分区点是比较好的。时间复杂度退化为最糟糕的 O(n2) 的情况，出现的可能性不大。

递归警惕堆栈溢出

  • 第一种是限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归。
  • 第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制。

举例分析排序函数

C 语言中的qsort()

  • qsort() 会优先使用归并排序来排序输入数据
  • 要排序的数据量比较大的时候，qsort() 会改为用快速排序算法来排序
  • qsort() 并不仅仅用到了归并排序和快速排序，它还用到了插入排序。在快速排序的过程中，当要排序的区间中，元素的个数小于等于 4 时，qsort() 就退化为插入排序，不再继续用递归来做快速排序，因为我们前面也讲过，在小规模数据面前，O(n2) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长

JS 中的Array.sort()

主要采用TimSort算法

  • 元素个数 < 32, 采用二分查找插入排序(Binary Sort)
  • 元素个数 >= 32, 采用归并排序，归并的核心是分区(Run)
  • 找连续升或降的序列作为分区，分区最终被调整为升序后压入栈
  • 如果分区长度太小，通过二分插入排序扩充分区长度到分区最小阙值
  • 每次压入栈，都要检查栈内已存在的分区是否满足合并条件，满足则进行合并
  • 最终栈内的分区被全部合并，得到一个排序好的数组

Timsort的合并算法非常巧妙：

  • 找出左分区最后一个元素(最大)及在右分区的位置
  • 找出右分区第一个元素(最小)及在左分区的位置
  • 仅对这两个位置之间的元素进行合并，之外的元素本身就是有序的

golang标准库中的Sort()

快排 + 希尔排序 + 插排

数据量大于12时用快排（pivot的选择做了很多工作），小于等于12时用6作为gap做一次希尔排序，然后走一遍普通的插排（插排对有序度高的序列效率高）

java 1.8 中的排序

在元素小于47的时候用插入排序，大于47小于286用双轴快排，大于286用timsort归并排序，并在timesort中记录数据的连续的有序段的的位置，若有序段太多，也就是说数据近乎乱序，则用双轴快排，当然快排的递归调用的过程中，若排序的子数组数据数量小，用插入排序。

.NET中的Array排序

  • 三个以内的，直接比较，交换进行实现
  • 大于3个小于16个的，用的是插入排序进行的实现
  • 对于大于16，并且深度限制是0的，用的是堆排序实现的
  • 对于大于15，并且深度限制不是0的，使用的是快速排序；然后快速排序分区使用的也是三数取中法

Google v8中对QuickSort的实现

  • 数据规模在10以内的话使用快排;
  • 数据规模在10到1000之间时选择中点作为pivot进行快排;
  • 数据规模在1000以上时，每隔200到215个数选一个数，将选出来的数排序，选择中间值作为pivot进行快排；

而且还有几个细节：

1 是折半的时候用的是位运算；

2 是每一次遍历都会分成小于pivot，等于pivot，大于pivot的三个区间；

3 是小于pivot和大于pivot这两个区间中数据规模比较小的会递归执行QuickSort，数据规模大的会先通过while循环减小数据规模。