知识卡片
快排划分后只递归两侧
选一个基准,双向扫描寻找处在错误一侧的元素并交换,最后把基准放到分界。此后基准不再参与子问题,只需分别排序两侧区间。
划分保持的是相对基准的范围,不代表两侧内部已有序。终止必须让区间确实缩小,并正确处理重复值;跨区交换可能改变同键次序,原书实现不稳定。
排序问答指出:以最左项为基准的这一双向模板,先从右找小值,再从左找大值,才能保证最终交换到最左侧的是合法值。换扫描顺序需要重新证明分区不变量,不能孤立调换两行;全相等输入还可用小于/等于/大于三段处理,只递归两侧。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
将基准数交换至两个子数组的分界线。 第11 章 排序 hello‑algo.com 237 图11‑8 哨兵划分步骤 哨兵划分完成后,原数组被划分成三部分:左子数组、基准数、右子数组,且满足“左子数组任意元素 准数 右子
- · 查看原书依据
当我们以最左端元素为基准数时,必须先“从右往左查找”再“从左往右查找” 。这个结论有些反直觉, 我们来剖析一下原因。 哨兵划分partition() 的最后一步是交换nums[left] nums[i] 。完成交换后,基
参考来源
- 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[24558,24668))
- 结论依据:实际partition扫描/轴归位/quickSort排除pivot支持。
- 原始内容:将基准数交换至两个子数组的分界线。 第11 章 排序 hello‑algo.com 237 图11‑8 哨兵划分步骤 哨兵划分完成后,原数组被划分成三部分:左子数组、基准数、右子数组,且满足“左子数组任意元素 准数 右子
补充原书证据:spine 5 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;归一字符[9443,9553)。
- 结论依据:实际[0,0,0,0,1]反例和三路建议补充具体模板正确性,非所有partition都必须同一扫描方向。
- 原始内容:当我们以最左端元素为基准数时,必须先“从右往左查找”再“从左往右查找” 。这个结论有些反直觉, 我们来剖析一下原因。 哨兵划分partition() 的最后一步是交换nums[left] nums[i] 。完成交换后,基