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次,故时间复杂度为 。
未经允许不得转载:7.9 路归并排序★3◎4