【8.5】归并排序

归并排序思想:

  • 划分为两个子序列
  • 分别对每个子序列归并排序
  • 有序子序列合并

两路归并排序:

归并函数:

归并算法优化:

  • 同优化的快速排序一样,对基本已排序序 列直接插入排序
  • R.Sedgewick 优化:归并时从两端开始 处理,向中间推进,简化边界判断

R.Sedgewick优化归并思想:

优化的归并排序(阈值28):

优化的归并函数:

算法复杂度分析

  • 空间代价:Θ(n)
  • 划分时间、排序时间、归并时间
    • T(n) = 2T (n / 2) + cn
  • T(1) = 1
  • 归并排序总时间代价也为
    • Θ(nlog n)
  • 不依赖于原始数组的输入情况,最大、最小以及平均时间代价均为 Θ(nlog n)

思考

  • 普通归并和 Sedgewick 算法都是稳定的吗?
  • 两个归并算法哪个更优?
    • 二者的比较次数和赋值次数
    • 归并时子序列下标是否需要边界判断

参考资料

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

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

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