快速排序

作者: Sun东辉 | 来源:发表于2022-05-21 20:26 被阅读0次

七大排序算法之快速排序
面试准备--排序
排序
算法笔记01-排序#2
PHP 实现快速排序
快速排序的Python实现
数据结构与算法快速排序
数组-快速排序
OC数据结构&算法
要成功就做一百题-94

顾名思义，快速排序（quicksort）是在实践中最快的已知排序算法，它的平均运行时间是 $O(N \log N)$ 。该算法之所以特别快，主要是由非常精炼且高度优化的内部循环。它的最坏情形的性能为 $O(N^2)$ ，但稍加努力就可以避免这种情形。虽然多年来快速排序算法被认为是理论上高度优化而在实践中却不可能正确的编程的一种算法，但是如今该算法简单易懂而且不难证明。像归并排序一样，快速排序也是一种分治的递归算法。将数组 S 排序的基本算法由下列简单的四步组成：

如果 S 中元素个数是 0 或 1，则返回。
取 S 中任意元素 v，称之为枢纽元（pivot）。
将 S-{v}（S 中其余元素）分成两个不相交的集合： $S_1=\{x\in S-\{v\}\;\vert\;x\;\leq v\}$ 和 $S_2=\{x\in S-\{v\}\;\vert\;x\;\geq v\}$ 。
返回 { $quicksort(S_1)$ 后，继而 ${quicksort(S_2)}$ }。

由于对那些等于枢纽元的元素的处理，第 3 步分割的描述不是唯一的，因此这就成了一个设计上的决策。一部分好的实现方法是将这种情形尽可能有效地处理。直观地看，我们希望把等于枢纽元的大约一半的关键字分到 $S_1$ 中，而另外的一半分到 $S_2$ 中，很像二叉查找树保持平衡一样。

如同归并排序那样，快速排序递归地解决了两个子问题并需要线性的附加工作（第 3 步），不过，与归并排序不同，这两个子问题并不保证具有相等的大小，这是个潜在的隐患。快速排序更快的原因在于，第 3 步的分割实际上是在适当的位置进行并且非常有效，它的高效大大弥补了大小不等的递归调用的缺憾。

选取枢纽元

虽然无论选择哪个元素做为枢纽元都能完成排序的工作，但是有些选择显然更优。

一种错误的方法

没有经过充分考虑的常见选择是将第一个元素用作枢纽元。如果输入是随机的，那么这是可以接受的，但是如果输入是预排序的或是反序的，那么这样的枢纽元就产生一个劣质的分割，因为所有的元素不是都被划入 $S_1$ 就是被划入 $S_2$ 。更有甚者，这种情况可能发生在所有的递归调用中。实际上，如果第一个元素用作枢纽元而且输入是预先排序的，那么快速排序花费的时间将是二次的，可是实际上却根本没干什么事，这是相当尴尬的。然而，预排序的输入（或具有一大段预排序数据的输入）是相当常见的，因此，使用第一个元素作为枢纽元绝对是糟糕的注意，应该立即放弃这种想法。另一种想法是选取前两个互异的关键字中的较大者为枢纽元，而这和只选取第一个元素作为枢纽元具有相同的害处。不要使用这两种选取枢纽元的策略。

一种安全的做法

一种安全的方针是随机选取枢纽元。一般来说这种策略非常安全，除非随机数生成器有问题（这并不罕见），因为随机的枢纽元不可能总是能接连不断地产生劣质的分割。另一方面，随机数的生成一般是昂贵的，根本减少不了算法其余部分的平均运行时间。

三数中值分割法（Median-of-Three Partitioning）

一组 N 个数的中值是第 $\frac{N}{2}$ 个最大的数。枢纽元额最好选择是数组中的中值。不幸的是，这很难算出，且会明显减慢快速排序的速度。这样的中值的估计量可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。例如，输入为 8、1、4、9、6、3、5、2、7、0，它的左边元素是 8，右边元素是 0，中心位置 $\frac{Left+Right}{2}$ 上的元素是 6。于是枢纽元是 $v=6$ 。显然使用三数中值分割法消除了预排序输入的坏情形（在这种情形下，这些分割都是一样的），并且减少了快速排序大约 $5\%$ 的运行时间。

分割策略

这里需要注意，对于那些等于枢纽云的关键字，进行不必要的交换建立两个均衡的子数组要比蛮干冒险得到两个不均衡的子数组好。因此，如果 $i$ 和 $j$ 遇到等于枢纽元的关键字，那么我们就让 $i$ 和 $j$ 都停止。对于这种输入，这实际上是不花费二次时间的四种可能性中唯一的一种可能。

小数组

对于很小的数组（ $N\leq20$ ），快速排序不如插入排序好。不仅如此，因为快速排序是递归的，所以这样的情形还经常发生。通常的解决办法是对于小的数组不是递归地使用快速排序，而是使用诸如插入排序这样对小数组有效的排序算法。使用这种策略实际上可以节省大约 $15\%$ （相对于自始至终使用快速排序时）的运行时间。一种好的截止范围（cutoff range）是 N=10，虽然在 5 到 20 之间任意截止范围都有可能产生类似的结果。这种做法也避免了一些有害的特殊情形，如取三个元素的中值而实际上却只有一个或两个元素的情况。

选择的线性期望时间算法

由于我们能够以 $O(N\log N)$ 时间给数组排序，因此可以期望为选择问题得到一个更好的时间界，即查找集合 $S$ 中第 $k$ 个最小元素的算法几乎与快速排序相同。事实上，其前三步是一样的。我们把这种算法叫做快速选择（quickselect）。令 $|S_i|$ 为 $S_i$ 中元素的个数。快速选择的步骤如下：

如果 $|S|=1$ ，那么 $k=1$ ，并将 $S$ 中的元素作为答案返回。如果使用小数组的截止(cutoff)方法且 $|S|\leq CUTOFF$ ，则将 $S$ 排序并返回第 $k$ 个最小元。
选取一个枢纽元 $v\in S$ 。
将集合 $S-\{v\}$ 分割成 $S_1$ 和 $S_2$ ，就像我们在快速排序中所做的那样。
如果 $k\leq|S_1|$ ，那么第 $k$ 个最小元必然在 $S_1$ 中。在这种情况下，返回 $quickselect(S_1,k)$ 。如果 $k=1+|S_1|$ ，那么枢纽元就是第 $k$ 个最小元，我们将它作为答案返回。否则，这第 $k$ 个最小元就在 $S_2$ 中，它是 $S_2$ 中的第 $(k-|S_1|-1)$ 个最小元。我们进行一次递归调用并返回 $quickselect(S_2,k-|S_1|-1)$ 。