知识卡片
分区不变量维护四段
对待分区子数组 A[p:r],取末元素 x=A[r] 为枢轴。扫描指针 j 从左向右移动,边界 i 记录“已确认不大于枢轴”区域的末端,循环开始时维护四段:A[p:i]≤x,A[i+1:j−1]>x,A[j:r−1] 尚未处理,A[r]=x。
扫描到 A[j]≤x 时,先扩张左段再把 A[j] 换入;扫描结束后把枢轴放到 i+1。这个不变量同时证明原地分区正确和线性扫描成本。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第7章 快速排序 · 查看原书依据
At the beginning of each iteration of the loop of lines 3–6, for any array index k, the following conditions hold: if p ≤ k ≤ i, then A[k] ≤ x (the tan region of Figure 7.2); if i + 1 ≤ k ≤ j – 1, then A[k] > x (the blue region); if k = r, then A[k] = x (the yellow region).
参考来源
- 位置:《算法导论(第4版)》第 7 章 7.1–7.3 节(`OEBPS/chapter007.xhtml`,文本字符 [0, 10000);图 7.1–7.5)。
- 结论依据:7.1 节 PARTITION 的循环不变量明确低段≤x、高段>x、扫描段未处理及末位枢轴 x;循环结束后将枢轴与 i+1 交换。
- 原始内容:At the beginning of each iteration of the loop of lines 3–6, for any array index k , the following conditions hold: if p ≤ k ≤ i , then A [ k ] ≤ x (the tan region of Figure 7.2 ); if i + 1 ≤ k ≤ j – 1, then A [ k ] > x (the blue region); if k = r , then A [ k ] = x (the yellow region).