知识卡片
枢轴决定元素是否比较
在元素互异的前提下,按排序后秩次记 z_i、z_j。
它们仅当区间 Z_ij 中首个枢轴是端点 z_i 或 z_j 时才比较;若先选中间元素,两者分到不同子问题。
每对元素最多比较一次;同值键不能直接套用。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第7章 快速排序 · 查看原书依据
During the execution of RANDOMIZED-QUICKSORT on an array of n distinct elements z1 < z2 < ⋯ < zn, an element zi is compared with an element zj, where i < j, if and only if one of them is chosen as a pivot before any other element in the set Zij. Moreover, no two elements are ever compared twice.
参考来源
- 位置:《算法导论(第4版)》第 7 章引理 7.2(`OEBPS/chapter007.xhtml`,文本字符 [25000, 28000);Art_P315–P321)。
- 结论依据:原文分三种首个枢轴情形证明比较条件与唯一性。
- 原始内容:During the execution of R ANDOMIZED -Q UICKSORT on an array of n distinct elements z 1 < z 2 < ⋯ < z n , an element z i is compared with an element z j , where i < j , if and only if one of them is chosen as a pivot before any other element in the set Z ij . Moreover, no two elements are ever compared twice.