排序优化

几乎所有的编程语言都会提供排序函数，比如 C 语言中 qsort()，C++ STL 中的 sort()、stable_sort()，Java 语言中的 Collection.sort()，还有 JavaScript 中的 sort()。在平时开发中中，我们也是直接使用这些现成的函数来实现业务逻辑中的排序功能。那你知道这些排序函数是如何实现的吗？底层都利用了哪种排序算法？

基于这些问题，我们来研究如何实现一个通用的、高性能的排序函数？

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

如果要实现一个通用的、高效率的排序函数，我们应该选择哪种排序算法？

我们前面讲过，线性排序算法的时间复杂度比较低，适用场景比较特殊。所以要写一个通用的排序函数，不能选择线性排序算法。

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

时间复杂度是 $O(ologn)$ 的排序算法不止一个，我们已经讲过归并排序、快速排序，后面讲堆的时候还有讲到堆排序。堆排序和快速排序都有比较多的应用，比如 Java 语言采用堆排序实现排序函数，C 语言使用快速排序实现排序函数。

不知道你有没有发现，使用归并排序的情况并不多。我们知道，快排在最坏情况下的时间复杂度是 $O(n^2)$，而归并排序可以做到平均情况、最坏情况下的时间复杂度都是 $O(nlogn)$，但是为什么它还是没有得到广泛应用？

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

前面我们讲到，快速排序比较适合来实现排序函数，但是，我们也知道，快速排序在最坏情况下的时间复杂度是 $O(n^2)$，如果来解决这个 “复杂度恶化” 的问题？

如何优化快速排序？

为什么快速排序在最坏情况下的时间复杂度是 $O(n^2)$ ? 前面我们讲过，如果数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数据，那快速排序算法就会变得非常糟糕，时间复杂度就会退化为 $O(n^2)$。实际上，这种 $O(n^2)$ 时间复杂度出现的主要原因还是因为我们分区点选的不够合理。

那什么样的分区点是好的分区点？或者说如何来选择分区点？

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

如果很粗暴地直接选择第一个或者最后一个数据作为分区点，不考虑数据特点，肯定会出现之前讲的那样，在某些情况下，排序的最坏情况时间复杂度是 $O(n^2)$。为了提高排序算法的性能，我们也要尽可能地让每次分区都比较平均。

这里介绍两个比较常用、比较简单的分区算法。

1. 三数取中法

我们从区间的首、尾、中间，分别取出一个数，然后对比大小，去这三个数的中间值作为分区点。这样每间隔某个固定的长度，取数据出来进行比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。但是，如果要排序的数组比较大，那 “三数取中” 可能就不够了。可能要 “五数取中” 或者 “十数取中”。

2. 随机法

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

如果想了解更多寻找分区点的方法，可以自己再去深入学习一下。

我们知道，快速排序是用递归来实现的。递归的话，必须要警惕堆栈溢出。
为了避免在快速排序里，递归过深而堆栈过小，导致堆栈溢出，我们有两种解决方法：

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

分析排序函数

为了让你对实现一个排序函数有一个直观的感受，这里拿 Glibc 中的 qsort() 函数举例说明一下。qsort() 从名字上来看，很像是基于快速排序算法实现的，实际上它并不仅仅用了快排这一种算法。

如果你去看源码，你会发现，qsort() 会优先使用归并排序来排序输入数据，因为归并排序的空间复杂度是 $O(n)$，所以对于小数据量的排序，比如 1 KB、2 KB 等，归并排序额外需要 1 KB、2 KB 的内存空间，这个问题不大。这就是一个空间换时间的技巧。

但是如果数据量太大，就和我们之前提到的，排序 100 MB 的数据，这个时候我们再用归并排序就不合适了。所以，要排序的数据量比较大时，qsort() 会改用快速排序算法来排序。

那 qsort() 是如何选择快速排序算法中的分区点的？如果去看源码，就会发现，qsort() 选择分区点的方法就是 “三数取中法”。
还有我们前面提到的递归太深会导致堆栈溢出的问题，qsort() 是通过自己实现一个堆上的栈，手动模拟递归来解决的。

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

我们在讲复杂度分析的时候讲过，算法的性能可以通过时间复杂度来分析，但是，这种复杂度分析是偏理论的，如果我们深究的话，实际上时间复杂度并不等于代码实际的运行时间。

时间复杂度代表的是一个增长趋势，如果画成增长曲线图，你会发现 $O(n^2)$ 比 $O(nlogn)$ 要陡峭，也就是说增长趋势要更猛一些。但是，我们前面讲过，在大 O 复杂度表示法中，我们会省略低阶、系数和常数，也就是说，$O(nlogn)$ 在没有省略低阶、系数、常数之前可能是 $O(knlogn + c)$，而且 k 和 c 有可能还是一个比较大的数。

假设 k = 1000，c = 200，当我们对小规模数据（比如 n = 100） 排序时，$n^2$ 的值实际上比 $knlogn + c$ 还要小。

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

n^2 = 100 * 100 = 10000

所以，对于小规模的排序，$O(n^2)$ 的排序算法并不一定比 $O(nlogn)$ 排序算法执行的时间长。对于小数据量的排序，我们可以选择比较简单、不需要递归的插入排序算法。

在 qsort() 插入排序的算法实现中，利用了我们之前讲到的哨兵简化代码，提高执行效率。虽然哨兵可能只是少做一次判断，但是毕竟排序函数是非常常用、非常基础的函数，性能的优化要做到极致。

好了，上面的 qsort() 已经分析完毕，其实也没有很难。基本上都用到了我们前面讲的知识点，有了前面的积累，看一些底层的类库实现也会更容易一些。

总结

这篇文章分析了一个如何实现一个工业级的通用的、高效的排序函数，内容比较偏实战，而且也贯穿了前面几节的内容。大部分排序函数都是采用 $O(nlogn)$ 排序算法来实现，但是为了尽可能地提高性能，会做很多优化。还讲了快速排序的一些优化策略，比如合理选择分区点，避免递归太深等。

技术拓展

你所熟知的语言的排序函数是如何实现的？

上面我们分析的 qsort() 是 C 语言中的底层排序算法。你能不能分析一下你所熟悉的语言中的排序函数是用什么排序算法实现的？都存在哪些优化技巧？

。。。