知识卡片
把新元素插入有序部分
整理扑克牌时,保留左侧已排好的部分,从未整理部分取下一张,移到它在有序部分中的位置。每处理一张,有序部分增加一个元素,直到覆盖全部输入。
这是插入排序的核心不变量:每轮开始时前缀已有序。插入仍可能移动很多元素,因此“小数据常用”的用途描述不能推出任意输入都比其他排序快。
排序章把扑克直觉落实为保存base、从前向后缀反向比较并右移、最后写入空位。仅移动严格大于base的元素,可把新值放在同键之后而保持稳定;近有序时移动少,最坏逆序仍平方。EPUB Go代码括号和j作用域扁平化不完整,不能原样照抄。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
将扑克牌划分为“有序”和“无序”两部分,并假设初始状态下最左1 张扑克牌已经有序。 2. 在无序部分抽出一张扑克牌,插入至有序部分的正确位置;完成后最左2 张扑克已经有序。 3. 不断循环步骤2. ,每一轮将一张扑克牌从
- · 查看原书依据
在插入操作过程中,我们会将元素插入到相等元素的右侧,不会改变它们的顺序。 11.4.3 插入排序的优势 插入排序的时间复杂度为 2) ,而我们即将学习的快速排序的时间复杂度为 log 。尽管插入排序 的时间复杂度更高,但
参考来源
- 位置:《Hello 算法--Go版本》第01章《初识算法》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[14802,14912))
- 结论依据:实际三步扑克示例展开有序前缀逐步扩张机制。
- 原始内容:将扑克牌划分为“有序”和“无序”两部分,并假设初始状态下最左1 张扑克牌已经有序。 2. 在无序部分抽出一张扑克牌,插入至有序部分的正确位置;完成后最左2 张扑克已经有序。 3. 不断循环步骤2. ,每一轮将一张扑克牌从
补充原书证据:spine 4 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;归一字符[23687,23797)。
- 结论依据:实际插入流程/条件及稳定说明补充第一章类比。
- 原始内容:在插入操作过程中,我们会将元素插入到相等元素的右侧,不会改变它们的顺序。 11.4.3 插入排序的优势 插入排序的时间复杂度为 2) ,而我们即将学习的快速排序的时间复杂度为 log 。尽管插入排序 的时间复杂度更高,但