【数据结构】归并排序之一种基于二路归并的归并排序

前言

  归并排序适用于向量和列表通用;使用的是分而治之的策略;
  归:递归。首先将列表一分为二,并不断递归一分为二;
  并:合并,将当前的两个子序列(已有序)合并的算法;

下面是通用的归并排序的模板代码:

    template < typename T >
    void Vector :: mergeSort(Rank lo, Rank hi) {
    if(hi - lo<2)return;//一直递归到子序列是单元素,单元素区间自然有序,否则…
    int mi =(lo + hi)>>1;//以中点mi为界
    mergeSort(lo, mi);//对前子序列递归调用本函数mergeSort,对前半段排序
    mergeSort(mi, hi);//对后子序列递归调用本函数mergeSort,对后半段排序
    merge(lo, mi, hi);//归并,将当前的两个子序列(已有序)合并的算法

  由上述代码可知,二路归并排序的计算成本T(n) = 2*T(n/2) + O(n);其中O(n)为函数merge的计算成本;

merge(lo, mi, hi)的基本实现:

merge( )的运行时间主要消耗于for循环,共有两个控制变量j和k

  初始:j=0,k=0
  最终:j=lb,k=lc
  亦即:j+k = lb+lc = hi-lo = n

  所以for循环共迭代n次,即merge( )总体迭代不过O(n)次,故二路归并排序的计算成本T(n) = 2 * T(n/2) + O(n)成立。通过计算,二路归并算法复杂度为O(n * logn)。计算思路:T(n)到T(1)共有logn层,每层包含一个复杂度为n的算法(merge( )),所以总的时间复杂度为O(n*logn)。

  对于规模为n的向量,归并排序的最优、最坏时间复杂度均为Θ(nlog2n) 。

  注意,若两个待归并子序列不等长甚至相差很悬殊,merge( )的复杂度仍为O(n)。

————————— 本文结束 感谢您的阅读 —————————
谢谢你请我喝咖啡ლↂ‿‿ↂლ(支付宝扫一扫即可领红包, 消费时可抵现! 你省钱, 我赚钱, 多谢支持~)