本文共 2432 字，大约阅读时间需要 8 分钟。

几乎所有的编程语言都会提供排序函数，比如C语言中的qsort()、C++ STL中的sort()、stable_sort()，还有 Java 语言中的Collections.sort()。在平时的开发中，我们也都是直接使用这些现成的函数来实现业务逻辑中的排序工具，那这些函数是如何实现的呢？底层都利用了哪种排序算法，应该如何实现一个通用的、高性能的排序函数呢？

如何选择合适的排序算法

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

• 线性排序算法的时间复杂度虽然比较低，但是适用场景比较特殊。所以如果要写一个通用的排序函数，不能选择线性排序算法。
• 如果对小规模的数据进行排序，可以选择时间复杂度为O($n^2$)的算法；如果对大规模数据进行排序，时间复杂度是 O(nlogn) 的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。
• 时间复杂度是 O(nlogn) 的排序算法不止一个，比如归并排序、快速排序、堆排序等。堆排序和快排有比较多的应用，比如Java语言采用堆排序实现排序函数，C语言使用快排实现排序函数。但是归并排序用的并不多
• 我们知道，快排在最坏情况下的时间复杂度是O($n^2$)，而归并排序可以做到平均情况、最坏情况下的时间复杂度都是O(nlogn)，从这点上看起来很诱人，那为什么它还是没能得到“宠信”呢？这是因为归并排序并不是原地排序算法，空间复杂度是O(n)。所以，粗略点、夸张点讲，如果要排序 100MB 的数据，除了数据本身占用的内存之外，排序算法还要额外再占用 100MB 的内存空间，空间耗费就翻倍了。

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

如何优化快速排序

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

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

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

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

因此，比较常用的分区由两种：

• 三数取中法
• 随机法

三数取中法

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

随机法

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

举例分析排序函数

以拿 Glibc 中的 qsort() 函数分析举例

• qsort()会优先使用归并排序来排序输入数据，因为归并排序的空间复杂度是O(n)，所以对于小数据量的排序，比如1KB、2KB等，归并排序额外需要1KB、2KB 的内存空间，这个问题不大。现在计算机的内存都挺大的，我们很多时候追求的是速度。
• 当要排序的数据量比较大的时候，qsort() 会改为用快速排序算法来排序。那 qsort() 是如何选择快速排序算法的分区点的呢？选择分区点的方法就是“三数取中法”
• 对于递归太深会导致堆栈溢出的问题，qsort()是通过自己实现一个堆上的栈，手动模拟递归来解决的
• 另外，qsort()并不仅仅用到了归并排序和快速排序，它还用到了插入排序。在快速排序的过程中，当要排序的区间中，元素的个数小于等于4时，qsort()就会退化为插入排序，不再用递归来做快速排序，因为O($n^2$) 时间复杂度的算法并不一定比O(nlogn)的算法执行时间长。
• 在 qsort() 插入排序的算法实现中，也利用了哨兵这种编程技巧。虽然哨兵可能只是少做一次判断，但是毕竟排序函数是非常常用、非常基础的函数，性能的优化要做到极致。

为什么O($n^2$) 时间复杂度的算法并不一定比O(nlogn)的算法执行时间长呢？

• 虽然算法的性能可以通过时间复杂度来分析，但是，这种复杂度分析是比较偏理论的，如果我们深究的话，实际上时间复杂度并不等于代码实际的运行时间。
• 时间复杂度代表的是一个增长趋势，如果画成增长曲线图，你会发现 O($n^2$) 比 O(nlogn) 要陡峭，也就是说增长趋势要更猛一些。但是，我们前面讲过，在大 O 复杂度表示法中，我们会省略低阶、系数和常数，也就是说，O(nlogn) 在没有省略低阶、系数、常数之前可能是 O(knlogn + c)，而且 k 和 c 有可能还是一个比较大的数。
• 当我们对小规模数据（比如 n=100）排序时，$n^2$的值实际上比knlogn+c 还要小。
• 所以，对于小规模数据的排序，O($n^2$) 的排序算法并不一定比 O(nlogn) 排序算法执行的时间长。对于小数据量的排序，我们选择比较简单、不需要递归的插入排序算法。

转载地址：https://blog.csdn.net/zhizhengguan/article/details/122401166 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！