【8.2】内排序--插入排序 ( Shell 排序)

一、直接插入排序

算法分析:

  • 稳定
  • 空间代价:Θ(1)
  • 时间代价:

二、Shell 排序

  • 直接插入排序的两个性质:
    • 在最好情况(序列本身已是有序的)下时间代价为 Θ(n)
    • 对于短序列,直接插入排序比较有效
  • Shell 排序有效地利用了直接插入排序的 这两个性质

Shell排序算法思想:

  • 先将序列转化为若干小序列,在这些小序列内 进行插入排序
  • 逐渐增加小序列的规模,而减少小序列个数, 使得待排序序列逐渐处于更有序的状态
  • 最后对整个序列进行扫尾直接插入排序,从而 完成排序

“增量每次除以2递减”的Shell 排序:

针对增量而修改的插入排序算法:

算法分析:

  • 不稳定
  • 空间代价:Θ(1)
  • 时间代价
    • 增量每次除以2递减,Θ(n2)
  • 选择适当的增量序列
    • 可以使得时间代价接近 Θ(n)

Shell 排序选择增量序列:

Hibbard 增量序列

  • Hibbard 增量序列
    • {2^k -1,2^(k-1)-1,…,7,3,1}
  • Shell(3) 和 Hibbard 增量序列的 Shell 排序的效率可以达到 Θ(n32)
  • 选取其他增量序列还可以更进一步减 少时间代价

Shell最好的代价:

  • 呈 2p3q 形式的一系列整数: 1,2,3,4,6,8,9,12
  • Θ(n log2n)

三、思考

  1. 插入排序的变种

    • 发现逆序对直接交换
    • 查找待插入位置时,采用二分法
  2. Shell 排序中增量作用是什么?增量为2和增量 为3的序列,哪个更好?为什么?

  3. Shell 排序的每一轮子序列排序 可以用其他方法吗?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学