知识卡片

普通读书笔记卡 · 5626.j.1

一轮无交换证明已无逆序

理解等级:中级

若完整扫描当前未排序区间的所有相邻对都不需要交换,区间已经有序,可以停止后续冒泡。标志只要记录本轮是否发生过交换,再在轮末判断。

必须完成这一轮覆盖后才得到证明,不能在单次比较相等或顺序正确时提前结束。优化让已排序输入达到线性比较,但不改变一般最坏平方成本。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      如果某轮“冒泡”中没有执行任何交换操作,说明数组已经完成排序,可直接返回结果。因此,可 以增加一个标志位flag 来监测这种情况,一旦出现就立即返回。 第11 章 排序 hello‑algo.com 经过优化,冒泡排序的

    参考来源

    - 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[21974,22084)) - 结论依据:实际flag初始化/交换后true/轮末break支持终止证据。 - 原始内容:如果某轮“冒泡”中没有执行任何交换操作,说明数组已经完成排序,可直接返回结果。因此,可 以增加一个标志位flag 来监测这种情况,一旦出现就立即返回。 第11 章 排序 hello‑algo.com 经过优化,冒泡排序的