知识卡片
Hoare分区返回边界
Hoare 分区从两端向内扫描并交换放错侧的元素,返回两段之间的边界 j。
与本章主算法把枢轴放在最终位置不同,枢轴会留在其中一段;正确的递归区间是 [p,j] 和 [j+1,r],且两段非空。
不能把返回值误当枢轴最终下标。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第7章 快速排序 · 查看原书依据
Since p ≤ j < r, neither partition is empty.
参考来源
- 位置:《算法导论(第4版)》第 7 章问题 7-1(`OEBPS/chapter007.xhtml`,文本字符 [31000, 34000))。
- 结论依据:题目给出 Hoare 伪代码,并直接说明返回边界及两段性质;证明被留作练习。
- 原始内容:Since p ≤ j < r , neither partition is empty.