首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》快速排序

关灯直达底部

如果我们仔细考虑中值排序的性能,我们会发现随机选择pivotIndex将仍使selectKth的性能为线性时间。我们可以简化算法但是不会引起额外的性能开销吗?在某些情况下,这种简化实现能够快些吗?C.A.R.Hoare发明的快速排序虽然使用了大致相同的思想(这就是为什么我们首先介绍中值排序),但事实上确实比中值排序简单。

在快速排序中,我们不再寻找中值,而是通过某些策略(有时是随机的,有时是最左的,有时是中间的)来选择一个元素,这个元素将数组切分成了两个子数组。快排包含两步,如图4-11所示。首先数组根据中枢值分成两个数组,左子数组的元素都小于或者等于中枢值,右子数组的元素都大于或者等于中枢值。然后每个子数组被递归地排序。

图 4-11 快速排序详解

就像描述的那样,此算法的随机性使得我们很难证明平均情况下的性能仍然为O(nlogn)。在这里我们不会介绍得到这个结果所使用的高级数学分析工具,更多的细节在Cormen等(2001)中可以找到。

图4-12中的是快速排序的行为。图中的黑色方块表示切分函数第一行中的中枢值。选择的第一个中枢值是“2”,这是一个质量比较差的选择,因为这个值将数组切分成两个数组,一个大小为1,另一个为14。在下一次快速排序的递归调用,右边数组中的“12”被选中作为中枢值,这个中枢值切分成两个大小为9和4的子数组。在这里,你已经可以看到使用切分的好处,因为数组中的最后四个元素是最大的四个。因为中枢值选择的随机性,所以会有很多不同的行为。在不同的执行过程中,如图4-13所示,第一次选择的中枢值精确地将这个问题细分成两个可比较的问题。

图 4-12 快速排序的样例 图 4-13 快速排序的不同行为

使用环境

在每一个递归步骤中,大小为n的数组都被切分成两个集合,如果其中一个集合为空,另外一个集合的大小为n-1,快速排序将会退化成最坏的二次方行为。

在每一次切分后,中枢值的选择强烈地影响了两个子数组的大小。我们可以选择k(k为奇数)个随机元素的中值,而不是选择一个随机元素。在随后的“变种”一节中,我们将讨论不同的选择中枢值的策略。