知识卡片
一轮无交换证明已无逆序
若完整扫描当前未排序区间的所有相邻对都不需要交换,区间已经有序,可以停止后续冒泡。标志只要记录本轮是否发生过交换,再在轮末判断。
必须完成这一轮覆盖后才得到证明,不能在单次比较相等或顺序正确时提前结束。优化让已排序输入达到线性比较,但不改变一般最坏平方成本。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 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 经过优化,冒泡排序的