知识卡片
快速排序递归处理分区
选择枢轴并将其放到最终位置;左侧不大于枢轴,右侧不小于枢轴,再独立排序两个子区间。具体不等号由分区实现决定,书中代码把等值放左侧。图中首次选2得到1和14个元素,另一次选择中值附近元素则较平衡。
均匀随机枢轴在互异键下有期望 O(n log n) 时间,最坏仍为 O(n²);分区质量和重复键处理决定实际性能。图中的原地交换一般不保持相等元素的原始顺序。
80指出一侧为空而另一侧只少一个元素时,递归总工作量为二次。选择多个样本的中位数可改善通常的分区质量,但增加采样成本,不能无条件保证最坏情况。
82强调实践中的快速排序及其优化;具体性能需要与数据结构、输入分布和替代算法在同一环境下比较,不能把书中历史结论视为对所有工作负载的保证。
83分析:若每次均等分区,线性分区成本加上两半递归得到 O(n log n);若持续只排定一个元素,递推 T(n)=T(n−1)+O(n) 得到 O(n²)。随机策略的期望复杂度与每次恰好平衡是不同命题。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 快速排序递归处理分区
- · 使用环境
- · 结论
- · 分析
原书出处 · 4 处
- · 查看原书依据
快速排序 如果我们仔细考虑中值排序的性能,我们会发现随机选择pivotIndex将仍使selectKth的性能为线性时间。我们可以简化算法但是不会引起额外的性能开销吗?在某些情况下,这种简化实现能够快些吗?C.A.R.Hoare发明的快速排序虽然使用了大致相同的思想(这就是为什么我们首先介绍中值排序
- · 查看原书依据
二次方行为。 在每一次切分后,中枢值的选择强烈地影响了两个子数组的大小。我们可以选择k(k为奇数)个随机元素的中值,而不是选择一个随机元素。在随后的“变种”一节中,我们将讨论不同的选择中枢值的策略。
- · 查看原书依据
优化和强化研究使得快速排序成为最为高效的算法。稍后我们将会在“变种”一节中讨论各种变种的细节。
- · 查看原书依据
t(n)=2*t(n/2)+O(n) O(n)表示切分数组需要花费线性时间。第2章已经介绍过,如果一个算法能够用这样的t(n)来定义行为,那么其性能为O(n log n)。从大量实践的经验上来看,因为被抽象成为O(n)的常数比较小,快速排序要比中值排序快。快速排序的总开销也比较少,因为它不需要在构建