知识卡片
三点取中选择枢轴
随机快排的三点取中法从子数组随机抽取三个元素,以三者中位数为枢轴。样本极端值不会成为枢轴,因而降低极端划分的机会;它改变枢轴分布和常数因子,不能把快排最坏时间界改写为 O(n log n)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 三点取中选择枢轴
原书出处 · 1 处
- 第7章 快速排序 · 查看原书依据
A common approach is the median-of-3 method: choose the pivot as the median (middle element) of a set of 3 elements randomly selected from the subarray.
参考来源
- 位置:《算法导论(第4版)》第 7 章问题 7-6(`OEBPS/chapter007.xhtml`,文本字符 [38000, 40000))。
- 结论依据:原文定义三点取中法,指出最小/最大秩次不可能选中,并要求分析分区概率与渐近阶。
- 原始内容:A common approach is the median-of-3 method: choose the pivot as the median (middle element) of a set of 3 elements randomly selected from the subarray.