快速排序与其优化

__ryp__ · 2024-01-20 15:21:09 · 个人记录

快速排序是一种不稳定的通用排序算法，也是应用最为广泛的排序算法之一。它有着 O(n\lg n) 的优秀期望复杂度（众所周知，排序的最优复杂度就是 \Omega(n\lg n) 的）。

同时，对比一般的归并排序，它是原地的，空间复杂度 O(1)。唯一美中不足的是它不稳定，即，它会交换两个相同的元素顺序。因此如果对稳定性有需求，还是需要使用稳定的归并排序。

快速排序的思想很简单：取一个元素记作 p，然后将序列分为两部分，一部分严格小于 p，另一部分大于等于 p，然后在这两部分上递归。到达单元素序列回溯。

关键在于怎么选这个 p。朴素的快速排序总是选择序列的第一个或者最后一个元素，但是在一些极端情况会被卡掉：全部是一个元素的序列，与本来就有序的序列。

我们需要进行优化。显然，我们希望 p 的选择接近原序列的中位数。这样，我们就可以将原序列划分为两个长度相同的序列，达到 O(n\lg n) 的复杂度。问题在于如何选择这样的 p。

其实很简单，可以在选取序列头尾以及中间的三个数的中位数，或者取随机值。在本题中，随机值比三数取中跑得快 9 ms。

实际上，std::sort 用的是内省排序（introsort），它本质也是一种快速排序，但是在序列较短的时候采用插入排序，在递归栈太深的时候采用堆排序。工业用的大多数通用排序算法大多也基于此。