排序优化 #

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

排序算法的选择 #

先回顾前面的几种排序算法：

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

而归并排序的时候并没有快排多。我们知道快排最坏情况时间复杂度是 O(n^2)，而归并非常稳定，最好、最坏和平均时间复杂度都是 O(nlogn)，但是为什么用的比较少呢？

因为，归并排序不是原地排序算法，它的空间复杂度是 O(n)。扩展一点，要排序 100MB 的数据，除了数据本身占用内存之外，算法还需要额外的 100MB，空间消耗翻倍了。

如何优化快速排序 #

快排的最坏时间复杂度是 O(n^2)。这种情况是在数据原来就有序或者接近有序，每次分区点选择最后一个数据，这时快排就变得很糟糕，时间复杂度就退化为 O(n^2)。也就是说，这种 O(n^2) 时间复杂度的出现主要原因还是因为我们分区点选择的不够合理。

最理想的分区点应该使得被分区点分开的两个分区的数据差不多相等。

很粗暴的选择第一个后者最后一个，不考虑数据的特点，肯定会出现最坏的情况。为了提高性能，应该尽可能让每次分区都比较平均。

这里有介绍两个比较常用、简单的分区方法，直观的感受一下：

1. 三数取中

就是从区间首、尾、中间，分别取出一个数，然后比较大小，取这 3 个数的中间值作为分区点。

这种每间隔某个固定长度，取数据比较，将中间值作为分区点的分区算法，肯定比单纯地取某个位置的数据要好。

当排序的数组较大的时候，“三数取中”可能不够了，那就可以“五数取中”或者“十数取中”。

2. 随机法

随机法就是每次从排序的区间中，随机选择一个元素作为分区点。虽然不能保证每次选择的分区点都比较好，但是从概率来说，也不太可能每次分区点的选择都是最差的。平均来说，分区点选择还是比较好的，所以时间复杂度退化为 O(n^2) 的可能性不大。

另外，快排是通过递归实现的，递归实现要警惕栈溢出，有两种解决办法：

1. 限制递归深度

限制递归深度，一旦递归的深度过深，超过了事先设定的阈值，就停止递归。

2. 模拟调用栈

通过在堆上模拟实现一个函数调用栈，手动模拟递归的压栈、出栈过程，这样就不会有栈的大小限制了。