知识卡片

普通读书笔记卡 · 3615.d.2

三点取中选择枢轴

理解等级:中级

随机快排的三点取中法从子数组随机抽取三个元素,以三者中位数为枢轴。样本极端值不会成为枢轴,因而降低极端划分的机会;它改变枢轴分布和常数因子,不能把快排最坏时间界改写为 O(n log n)。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.