排序优化：如何实现一个通用的、高性能的排序函数？

文章来源于极客时间前google工程师−王争专栏。

几乎所有的编程语言都会提供排序函数，比如java中的Collections.sort()。在平时的开发中，我们都是直接使用，这些排序函数是如何实现的？底层都利用了哪种排序算法呢？

问题：如何实现一个通用的、高性能的排序函数？

如何选择合适的排序算法？

线性排序算法时间复杂度比较低，使用场景比较特殊。所以如果要写一个通用的排序函数，不能选择线性排序算法。

对于小规模数据进行排序，可以选择O(n^2)的算法；如果对大规模数据进行排序，O(nlogn)的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度为O(nlogn)的算法。

O(nlogn)的排序算法有归并排序、快速排序、还有堆排序。快排和堆排都有比较多的应用，比如java语言采用堆排序实现排序函数；c语言使用快排实现排序函数。

快排比较适合来实现排序函数，但是快排在最坏情况下时间复杂度为O(n^2)，如何来解决这个“复杂度恶化”的问题呢？

如何优化快速排序？

时间复杂度退化为O(n^{2)的原因是，数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数据。**实际上，这种O(n}2)时间复杂度出现的主要原因还是因为我们分区点选的不够合理。**

最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。

为了提高排序算法的性能，我们也要尽可能地让每次分区都比较平均。

比较常用、简单的分区算法：

1.三数取中法

从区间的首、尾、中间取出一个数，然后对比大小，取这3个数的中间值作为分区点。如果排序的数组比较大，那么“三数取中”可能就不够了，可能要“五数取中”或者“十数取中”。

2.随机法

从排序区间中随机选择一个元素作为分区点。

快排是用递归来实现的。递归要警惕堆栈溢出。

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

举例分析排序函数

C语言中的qsort()函数。源码解析：

qsort()优先使用归并排序来排序输入数据，归并排序空间复杂度为O(n)，对于小数据量的排序，比如1KB、2KB等，归并排序额外需要1KB、2KB的内存空间，问题不大。空间换时间思想。

如果数据量太大，比如100MB，归并排序就不合适了。所以，当数据量比较大的时候，qsort()会改用快速排序算法来排序。qsort()选择分区点的方法就是“三数取中法”

递归太深导致堆栈溢出的问题，qsort()通过自己实现一个堆上的栈，手动模拟递归来解决。

qsort()不仅仅用到了归并排序和快速排序，它还用了插入排序。排序过程中，当要排序的区间中，元素的个数小于等于4，qsort()就退化为插入排序，不再继续用递归来做快速排序。在小规模数据面前，O(n^2)时间复杂度的算法并不一定比O(nlogn)的算法执行时间长。

复杂度分析比较偏理论，深究的话，实际上时间复杂度并不等于代码实际的运行时间。

如果不省略低阶、系数和常数。O(nlogn) = O(knlogn+c)

假设K=1000，c=200，当我们对小规模数据（n=100）排序，n^2实际上比Knlogn+c还要小。

knlogn+c = 1000 * 100 * log100 + 200 远大于 10000

n^2 = 100*100 = 10000

1
2
3
4

qsort()插入排序的算法实现中，使用哨兵编程技巧，虽然哨兵可能只是少做一次判断，但毕竟排序函数是非常常用、基础的函数，性能优化要做到极致。

总结

大部分排序函数都是采用O(nlogn)排序算法实现，但是为了尽可能提高性能，会做很多优化。

排序中的优化策略，比如合理选择分区点、避免递归太深等。

思考

学习Arrays.sort()源码