预计阅读本页时间：-
快速排序
如果我们仔细考虑中值排序的性能，我们会发现随机选择pivotIndex将仍使selectKth的性能为线性时间。我们可以简化算法但是不会引起额外的性能开销吗？在某些情况下，这种简化实现能够快些吗？C.A.R.Hoare发明的快速排序虽然使用了大致相同的思想（这就是为什么我们首先介绍中值排序），但事实上确实比中值排序简单。
在快速排序中，我们不再寻找中值，而是通过某些策略（有时是随机的，有时是最左的，有时是中间的）来选择一个元素，这个元素将数组切分成了两个子数组。快排包含两步，如图4-11所示。首先数组根据中枢值分成两个数组，左子数组的元素都小于或者等于中枢值，右子数组的元素都大于或者等于中枢值。然后每个子数组被递归地排序。
就像描述的那样，此算法的随机性使得我们很难证明平均情况下的性能仍然为O(nlogn)。在这里我们不会介绍得到这个结果所使用的高级数学分析工具，更多的细节在Cormen等（2001）中可以找到。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
图4-12中的是快速排序的行为。图中的黑色方块表示切分函数第一行中的中枢值。选择的第一个中枢值是“2”，这是一个质量比较差的选择，因为这个值将数组切分成两个数组，一个大小为1，另一个为14。在下一次快速排序的递归调用，右边数组中的“12”被选中作为中枢值，这个中枢值切分成两个大小为9和4的子数组。在这里，你已经可以看到使用切分的好处，因为数组中的最后四个元素是最大的四个。因为中枢值选择的随机性，所以会有很多不同的行为。在不同的执行过程中，如图4-13所示，第一次选择的中枢值精确地将这个问题细分成两个可比较的问题。
使用环境
在每一个递归步骤中，大小为n的数组都被切分成两个集合，如果其中一个集合为空，另外一个集合的大小为n-1，快速排序将会退化成最坏的二次方行为。
在每一次切分后，中枢值的选择强烈地影响了两个子数组的大小。我们可以选择k（k为奇数）个随机元素的中值，而不是选择一个随机元素。在随后的“变种”一节中，我们将讨论不同的选择中枢值的策略。
