本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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），它本质也是一种快速排序，但是在序列较短的时候采用插入排序，在递归栈太深的时候采用堆排序。工业用的大多数通用排序算法大多也基于此。