知识卡片

普通读书笔记卡 · 3612.a.3

五元组中位数选枢轴

理解等级:高级

对互异元素(或先以原下标打破同值),确定性线性选择把元素分成五元组,各组排序并抽取中位数,再递归求组中位数的中位数作枢轴。

组内次序保证分区两侧有足够多可排除的元素,不依赖随机性;代价是额外一次求枢轴递归。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 9 章 9.3 节(`OEBPS/chapter009.xhtml`,文本字符 [20000, 25500);图 9.3/Art_P356)。 - 结论依据:原文 SELECT 伪代码把五元组中位数放在中间五分之一,并递归选其中位数作为分区枢轴。 - 原始内容:Find the pivot x recursively as the median of the group medians.