知识卡片

普通读书笔记卡 · 3615.d.1.a

枢轴决定元素是否比较

理解等级:高级

在元素互异的前提下,按排序后秩次记 z_i、z_j。

它们仅当区间 Z_ij 中首个枢轴是端点 z_i 或 z_j 时才比较;若先选中间元素,两者分到不同子问题。

每对元素最多比较一次;同值键不能直接套用。

这张卡片看不懂?

已有反馈 · 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.