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

2019-01-12 本文已影响0人红酥手黄藤酒丶

有一节线性排序先搁置一下，讲了 桶排序 基数排序 计数排序，这三种排序的时间复杂度是线性的 ○(n)，所以也被称作线性排序，因为这三个算法是非基于比较的算法，都不设计元素之间的比较操作，因为对数据的要求条件较高，暂时就不写笔记了。

今天学习一下排序优化。

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

如果要是实现一个通用的、高效率的排序函数，我们应该选择哪种算法？
先回顾前面学到的几种算法：

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

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

时间复杂度是 ○(n㏒n) 的排序算法不止一个，已经学到的有 归并排序 快速排序，后面还会学到 堆排序。堆排序 和 快速排序 都有较多的应用，Java 中就采用的 堆排序 实现排序函数，C 语言使用 快速排序 实现排序函数。

此时我们发现，使用归并排序的情况并不多。我们知道快排只有在最坏情况下的时间复杂度是 ○(n²) ，而归并排序可以做到平均情况，最坏情况的时间复杂度都是 ○(n㏒n) ，那么为什么它还是没能干过快排呢？

首先一点，归并排序不是原地排序，会占用更多的内存。

但是，快排在最坏情况下的时间复杂度也是 ○(n²) ，如何解决这个 复杂度恶化 的问题呢？

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

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

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

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

三数取中法
从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点。这样每间隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据要好。但是如果要排序的数组比较大，那 三数取中 可能就不够了，可能要 五数取中 或 十数取中。
随机法
随机法就是每次从要排序的取件中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选择很差的情况，所以平均情况下，这样选的分区点是比较好的。时间复杂度退化为最糟糕的 ○(n²) 的情况，出现的可能性也很小。