移动次直接改进的二分冒泡改进选择 总代价直接改进的二分法冒泡改进的选择 插入插入排法插排序的冒排序 插入插入排插入排排序冒泡排排序 排序序 泡排 排序序 最佳情e(m)e(n) e(nlog叫me(n2e(mn)e(m 最佳情 e(n)e(n)0 e(n) 均情e(n2)e(m2)e(m3)e(m2e(m3)e( 平均情emne(m)e(n)e(n)e(n)e(m) 最差情e(m2)6(n2)e(m2)e(m2e(mn)e(m 最差情e(m)e(n2)e(m2)e(m2)emn)e(n) A上 聊脑张写 叔新有,命邮 原因 7.3Shel1排序 ■一个长度为n序列平均有n(n-1)/4 ■直接插入排序的两个性质: 对逆置 在最好情况(序列本身已是有序 任何一种只对相邻记录进行比较 的)下时间代价为e(n) 的排序算法的平均时间代价都是 对于短序列,直接插入排序比较 有效 e(n2) She排序有效地利用了直接插 入排序的这两个性质 北真大脆张写 版叔斯有就即究 叔新有,量究 Shel1排序 算法思想 先将序列转化为若干小序列,在这些 序列内进行插入排序 221125a78,62 ■逐渐扩大小序列的规模,而减少 列个数,使得待排序序列逐渐处 有序的状态 d122123453178,6 最后对整个序列进行扫尾直接插入排 序,从而完成排序 1229323434456478 北真大学张铭编写8 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 43 Θ(n Θ(n) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 最差情 ) 况 Θ(n Θ(n) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 平均情 ) 况 最佳情 0 Θ(n) Θ(n) 0 0 Θ(n) 况 选择 排序 改进 的冒 泡排 序 冒泡 排序 二分 法插 入排 序 改进的 插入排 序 直接 插入 排序 移动次 数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 44 Θ(n2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 最差情 ) 况 Θ(n2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 平均情 ) 况 Θ(n2 Θ(n Θ(n) ) 2 最佳情 Θ(n) Θ(n) Θ(nlog n) ) 况 选择 排序 改进的 冒泡排 序 冒泡 排序 二分法 插入排 序 改进的 插入排 序 直接 插入 排序 总代价 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 45 原因 „ 一个长度为n序列平均有 n(n-1)/4 对逆置 „ 任何一种只对相邻记录进行比较 的排序算法的平均时间代价都是 Θ(n2) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 46 7.3 Shell排序 „ 直接插入排序的两个性质： „ 在最好情况（序列本身已是有序 的）下时间代价为Θ(n) „ 对于短序列，直接插入排序比较 有效 „ Shell排序有效地利用了直接插 入排序的这两个性质 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 47 Shell排序 „ 算法思想： „ 先将序列转化为若干小序列，在这些 小序列内进行插入排序 „ 逐渐扩大小序列的规模，而减少小序 列个数，使得待排序序列逐渐处于更 有序的状态 „ 最后对整个序列进行扫尾直接插入排 序，从而完成排序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 48 d=4 45 34 78 12 34 32 29 64 d=2 34 32 29 12 45 34 78 64 d=1 29 12 34 32 45 34 78 64 12 29 32 34 34 45 64 78