知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.2.a.6 · 生成模型:未记录

插入排序维护有序前缀

理解等级:中级

初始时单个元素构成有序前缀;每轮暂存下一个元素,将前缀中比它大的元素右移,再将暂存值放入空位。前缀扩展一位后仍有序,循环结束得到完整排序。

03187示意把7插入1、4、8、9、11、15之间;03188展示16个元素各轮变化,书中统计60次移动。原文称前缀“严格有序”不适合含重复键的输入,这里应理解为非递减。相等元素不被右移时,稳定性得以保留。

68指出近有序输入通常需要较少移动,小数据也可能受益;具体阈值需按机器、语言、比较与搬移成本测量,不能将一个固定n视为普遍边界。

71以16项例子的60次移动说明工作量;有序输入每轮仍需检查但不右移,互异逆序输入每个新元素需跨过此前全部元素。近有序的具体成本取决于逆序对和比较方式,不能仅凭口头“接近”给出固定次数。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      有序区域A[0,pos](这个区域被用粗体竖线隔开)的正确位置,最后A成为一个有序序列。灰色的元素被移到右边确保为即将插入的元素腾出位置,总体来说,插入排序执行了60次移位(一次将一个元素移动一个位置)。 图 4-6 插入排序详解 图 4-7 插入排序在小数据集上的执行过程

    • · 查看原书依据

      小规模数据需要排序,并且初始数据几乎是有序的,这个时候可以使用插入排序。什么样的数据集是小规模的,这个根据编程语言和机器的不同而存在不同的答案。事实上,元素的类型也是很重要的。

    • · 查看原书依据

      逆序有序的时候,那么很显然是最坏的情况。如果这个数组是已经几乎有序,插入排序将会做得很好,因为只需要移动很少的元素。

    参考来源

    - 位置:《算法技术手册》第4章《插入排序》(spine1497;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1460.html;u067-ch04-007)。 - 结论依据:67全文、03187伪代码及03188全部状态行实读。 - 原始内容:有序区域A[0,pos](这个区域被用粗体竖线隔开)的正确位置,最后A成为一个有序序列。灰色的元素被移到右边确保为即将插入的元素腾出位置,总体来说,插入排序执行了60次移位(一次将一个元素移动一个位置)。 图 4-6 插入排序详解 图 4-7 插入排序在小数据集上的执行过程 - 位置:《算法技术手册》第4章《使用环境》(spine1497;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1460.html;u068-ch04-007)。 - 结论依据:68指出近有序输入通常需要较少移动,小数据也可能受益;具体阈值需按机器、语言、比较与搬移成本测量,不能将一个固定n视为普遍边界。 - 原始内容:小规模数据需要排序,并且初始数据几乎是有序的,这个时候可以使用插入排序。什么样的数据集是小规模的,这个根据编程语言和机器的不同而存在不同的答案。事实上,元素的类型也是很重要的。 - 位置:《算法技术手册》第4章《结论》(spine1500;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1463.html;u071-ch04-007)。 - 结论依据:71以16项例子的60次移动说明工作量;有序输入每轮仍需检查但不右移,互异逆序输入每个新元素需跨过此前全部元素。近有序的具体成本取决于逆序对和比较方式,不能仅凭口头“接近”给出固定次数。 - 原始内容:逆序有序的时候,那么很显然是最坏的情况。如果这个数组是已经几乎有序,插入排序将会做得很好,因为只需要移动很少的元素。