知识卡片
五元组中位数选枢轴
对互异元素(或先以原下标打破同值),确定性线性选择把元素分成五元组,各组排序并抽取中位数,再递归求组中位数的中位数作枢轴。
组内次序保证分区两侧有足够多可排除的元素,不依赖随机性;代价是额外一次求枢轴递归。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第9章 中位数和顺序统计量 · 查看原书依据
Find the pivot x recursively as the median of the group medians.
参考来源
- 位置:《算法导论(第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.