考研帮 > 数学 > 每日一练

7.9 路归并排序★3◎4

7.9 二路归并排序★3◎4

  二路归并排序的基本思想:将两个有序表合并为一个有序表。
  1个元素的表总是有序的,所以对n个元素的待排序列,每个元素可看成1个有序子表。对子表两两合并生成 个子表,所得子表除最后一个子表长度可能为1外,其余子表长度均为2。再进行两两合并,直到生成n个元素按关键码有序的表。
  设r[u…t]由两个有序子表r[u,…,v-1]和r[v,…,t]组成,两个子表长度分别为v-u、t-v+1。合并方法为:

  

  对序列{39,80,76,41,13,29,50,78,30,11,100,7}进行二路归并排序的过程如下:
  初始序列:39,80,76,41,13,29,50,78,30,11,100,7
  第一趟归并:[39, 80],[41,76],[13,29],[50,78],[11,30],[7,100]
  第二趟归并:[39,41,76,80], [13,29,50,78], [7,11,30,100]
  第三趟归并:[13,29,39,41,50,76,78,80], [7,11,30,100]
  第四趟归并:[7, 11, 13, 29, 30, 39, 41, 50, 76, 78, 80, 100]
  【效率分析】
  需要一个与表等长的辅助元素数组空间,所以空间复杂度为O(n)。
  对n个元素的表,将这n个元素看做叶结点,若将两两归并生成的子表看做它们的父结点,则归并过程对应由叶向根生成一棵二叉树的过程。所以归并趟数约等于二叉树的高度减去1,即 ;每趟归并需移动记录n次,故时间复杂度为 。

关于"最后阶段,真题的正确打开方式_备考经验_考研帮"15名研友在考研帮APP发表了观点

扫我下载考研帮

考研帮地方站更多

你可能会关心:

来考研帮提升效率

× 关闭