知识卡片
随机枢轴消除固定坏输入
随机化快排从当前子数组均匀选一个枢轴,交换到末位后沿用普通分区。
对固定输入,分区质量由算法内部随机选择决定,因此不存在仅由元素顺序确定的坏输入;但单次仍可能遇到连续差枢轴,最坏时间仍为 Θ(n²)。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第7章 快速排序 · 查看原书依据
Instead of always using A[r] as the pivot, a randomized version randomly chooses the pivot from the subarray A[p : r]
参考来源
- 位置:《算法导论(第4版)》第 7 章 7.1–7.3 节(`OEBPS/chapter007.xhtml`,文本字符 [15000, 20000);图 7.1–7.5)。
- 结论依据:7.3 节 RANDOMIZED-PARTITION 从当前子数组等概率选枢轴并与末位交换;随机选择改变固定输入的划分分布,仍保留 Θ(n²) 最坏路径。
- 原始内容:Instead of always using A [ r ] as the pivot, a randomized version randomly chooses the pivot from the subarray A [ p : r ]