知识卡片

普通读书笔记卡 · 5626.k

快排划分后只递归两侧

理解等级:中级

选一个基准,双向扫描寻找处在错误一侧的元素并交换,最后把基准放到分界。此后基准不再参与子问题,只需分别排序两侧区间。

划分保持的是相对基准的范围,不代表两侧内部已有序。终止必须让区间确实缩小,并正确处理重复值;跨区交换可能改变同键次序,原书实现不稳定。

排序问答指出:以最左项为基准的这一双向模板,先从右找小值,再从左找大值,才能保证最终交换到最左侧的是合法值。换扫描顺序需要重新证明分区不变量,不能孤立调换两行;全相等输入还可用小于/等于/大于三段处理,只递归两侧。

这张卡片看不懂?

已有反馈 · 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] 。完成交换后,基