知识卡片

普通读书笔记卡 · 5626.f

把新元素插入有序部分

理解等级:中级

整理扑克牌时,保留左侧已排好的部分,从未整理部分取下一张,移到它在有序部分中的位置。每处理一张,有序部分增加一个元素,直到覆盖全部输入。

这是插入排序的核心不变量:每轮开始时前缀已有序。插入仍可能移动很多元素,因此“小数据常用”的用途描述不能推出任意输入都比其他排序快。

排序章把扑克直觉落实为保存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 。尽管插入排序 的时间复杂度更高,但