知识卡片

结构图卡 · 1708.b.2.e · 生成模型:未记录

有序前缀逐个接纳新元素

理解等级:中级

插入排序维护已排好序的前缀,每轮取出紧接其后的key,把前缀中比key大的项逐一右移,再把key放入留下的位置。02696-02697的issort以字节大小esize定位元素,用compare判断次序。

结构图:

flowchart TD
 A[取下一项到临时key] --> B{左边仍有项且比key大}
 B -->|是| C[该项右移并继续向左]
 C --> B
 B -->|否| D[把key放入空位]
 D --> E{还有未处理项}
 E -->|有| A
 E -->|无| F[结束]

函数先malloc临时空间,失败返回-1;正常结束free后返回0。比较器与元素有效范围由调用方提供,代码没有通用参数检查;它只搬动esize字节,不深复制内部对象。

205已有序/未序并非一定两份独立存储,实际207用同一数组前缀与后缀分区,临时保存单个key即可移动现有项;没有额外结果数组不等于零临时空间。

207的02950初始[23,21,76,16,52,43]逐步变为[21,23,76,16,52,43]、再把16插到头,最终[16,21,23,43,52,76]。02951完整函数与第4章版本同一机制;只在compare>0时右移,等键不跨过先前等键,保留相对次序。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      在一个有序的数据集中查找放置新元素的位置,并将新元素插入进去。在第12章完整描述了插入排序算法。插入排序的代码如示例4-1所示。 首先要知道,哪行代码会受要排序的数据量影响。我们看到代码中有一个嵌套循环,外层的迭代数从i到size-1,内层的迭代数从j-1到所要插入的新元素的正确位置。其他代码的运行

    • · 查看原书依据

      扫描已排好序的数据集,并将它插入有序集合合适的位置上。虽然乍一看,插入排序需要独立为有序和无序的元素集合预留足够的存储空间,但实际上它是不需要额外的存储空间的。 插入排序是一种较为简单的算法,但是它在处理大型数据集时并不高效。因为很明显,在决定将元素插入哪个位置之前,需要将被插入元素和有序数据集中的

    • · 查看原书依据

      变量i来向后查找元素将要放置的位置。当向后查找数据时,每个处于位置i的元素都要向右移动一位,以保证预留出足够的空间来插入新元素。一旦j到达无序数据集的尾部,data就是一个有序数据集了(见图12-1)。 图 12-1 插入排序 插入排序的时间复杂度关键在于它的嵌套循环部分。考虑到这一点,外部循环运行

    参考来源

    - 位置:《算法精解:C语言描述》第4章《实例分析:插入排序》(spine1201;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1169.html;u044-ch04-006)。 - 结论依据:44全文和02696-02697完整issort签名/代码,外循环j、内循环i、临时key分配/归还及返回状态均已查看,流程按实际条件还原。 - 原始内容:在一个有序的数据集中查找放置新元素的位置,并将新元素插入进去。在第12章完整描述了插入排序算法。插入排序的代码如示例4-1所示。 首先要知道,哪行代码会受要排序的数据量影响。我们看到代码中有一个嵌套循环,外层的迭代数从i到size-1,内层的迭代数从j-1到所要插入的新元素的正确位置。其他代码的运行 - 位置:《算法精解:C语言描述》第12章《插入排序的描述》(spine1337;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1303_split_001.html;u205-ch04-006)。 - 结论依据:205已有序/未序并非一定两份独立存储,实际207用同一数组前缀与后缀分区,临时保存单个key即可移动现有项;没有额外结果数组不等于零临时空间。 - 原始内容:扫描已排好序的数据集,并将它插入有序集合合适的位置上。虽然乍一看,插入排序需要独立为有序和无序的元素集合预留足够的存储空间,但实际上它是不需要额外的存储空间的。 插入排序是一种较为简单的算法,但是它在处理大型数据集时并不高效。因为很明显,在决定将元素插入哪个位置之前,需要将被插入元素和有序数据集中的 - 位置:《算法精解:C语言描述》第12章《插入排序的实现与分析》(spine1339;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1305.html;u207-ch04-006)。 - 结论依据:207的02950初始[23,21,76,16,52,43]逐步变为[21,23,76,16,52,43]、再把16插到头,最终[16,21,23,43,52,76]。02951完整函数与第4章版本同一机制;只在compare>0时右移,等键不跨过先前等键,保留相对次序。 - 原始内容:变量i来向后查找元素将要放置的位置。当向后查找数据时,每个处于位置i的元素都要向右移动一位,以保证预留出足够的空间来插入新元素。一旦j到达无序数据集的尾部,data就是一个有序数据集了(见图12-1)。 图 12-1 插入排序 插入排序的时间复杂度关键在于它的嵌套循环部分。考虑到这一点,外部循环运行