知识卡片

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

Hoare分区返回边界

理解等级:高级

Hoare 分区从两端向内扫描并交换放错侧的元素,返回两段之间的边界 j。

与本章主算法把枢轴放在最终位置不同,枢轴会留在其中一段;正确的递归区间是 [p,j] 和 [j+1,r],且两段非空。

不能把返回值误当枢轴最终下标。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 7 章问题 7-1(`OEBPS/chapter007.xhtml`,文本字符 [31000, 34000))。 - 结论依据:题目给出 Hoare 伪代码,并直接说明返回边界及两段性质;证明被留作练习。 - 原始内容:Since p ≤ j < r , neither partition is empty.