5.3插入排序与希尔排序算法及分析（Python进阶-数据结构与算法）课件

插入排序算法及分析 数据结构与算法（Python版） ❖ 插入排序时间复杂度仍然是O(n2) ， 但算 法思路与冒泡排序、 选择排序不同 ❖ 插入排序维持一个已排好序的子列表 ， 其 位置始终在列表的前部 ， 然后逐步扩大这 个子列表直到全表 数据结构与算法（Python版） 插入排序Insertion Sort 0 ❖ 第1趟 ， 子列表仅包含第1个数据项 ， 将第 2个数据项作为 “新项 ”插入到子列表的 合适位置中 ， 这样已排序的子列表就包含 了2个数据项 ❖ 第2趟 ， 再继续将第3个数据项跟前2个数 据项比对 ， 并移动比自身大的数据项 ， 空 出位置来 ， 以便加入到子列表中 ❖ 经过n- 1趟比对和插入 ， 子列表扩展到全 表 ， 排序完成 数据结构与算法（Python版） 插入排序Insertion Sort 0 ❖ 插入排序的比对主要用来寻找“新项 ”的 插入位置 ❖ 最差情况是每趟都与子列表中所有项进行 比对 ， 总比对次数与冒泡排序相同 ， 数量 级仍是O(n2) ❖ 最好情况 ， 列表已经排好序的时候 ， 每趟 仅需1次比对 ， 总次数是O(n) 数据结构与算法（Python版） 插入排序Insertion Sort 0 数据结构与算法（Python版） 0 比对，移动所有 比“新项”大的数据项 数据结构与算法（Python版） 插入排序：思路 0 由于移动操作仅包含1次赋值，是交换操作 的1/3，所以插入排序性能会较好一些。 比对、移动 插入新项 数据结构与算法（Python版） 插入排序：代码 新项/插入项 0 ❖ 我们注意到插入排序的比对次数 ，在最好的情况 下是O(n) ，这种情况发生在列表已是有序的情况 下 ， 实际上 ，列表越接近有序 ，插入排序的比对 次数就越少 ❖ 从这个情况入手 ，谢尔排序以插入排序作为基础 , 对无序表进行“ 间隔 ”划分子列表 ，每个子列 表都执行插入排序 数据结构与算法（Python版） 谢尔排序Shell Sort 0 ❖ 随着子列表的数量越来越少 ， 无序表的整 体越来越接近有序 ， 从而减少整体排序的 比对次数 ❖ 间隔为3的子列表 ， 子列表分别插入排序 后的整体状况更接近有序 数据结构与算法（Python版） 谢尔排序Shell Sort 0 ❖ 最后一趟是标准的插入排序 ， 但由于前面 几趟已经将列表处理到接近有序 ， 这一趟 仅需少数几次移动即可完成 数据结构与算法（Python版） 谢尔排序：思路 0 ❖ 子列表的间隔一般从n/2开始 ， 每趟倍增 ： n/4, n/8 ……直到1 数据结构与算法（Python版） 谢尔排序：思路 0 数据结构与算法（Python版） 谢尔排序：代码 间隔缩小 0 间隔设定 ❖ 粗看上去 ， 谢尔排序以插入排序为基础， 可能并不会比插入排序好 ❖ 但由于每趟都使得列表更加接近有序 ， 这 过程会减少很多原先需要的“无效”比对 对谢尔排序的详尽分析比较复杂，大致说是介于 O(n)和O(n2)之间 ❖ 如果将间隔保持在2k-1(1、 3、 5、 7、 15 、 31等等） ， 谢尔排序的时间复杂度约为 O（ n3/2) 数据结构与算法（Python版） 谢尔排序：算法分析 0 $$