数据结构与算法-归并排序

原理：

分解过程 ： 存在序列A[1...n]，将这个序列分解成俩个序列(↓(n/2)向下取整为m)，一边含m个数元素序列A[1...m]，一边n-m个数元素序列A[m+1...n]；

合并过程 ： 针对俩个序列A的俩个子序列A[p...q]，A[q+1...s]，而且A[p...q]，A[q+1...s]都是各自排序好的序列，现在合并得到一个A[p...s]排序好的子序列;

停止分解 ： 序列中只有一个元素时，那么这个序列就是有序序列，可以停止分解过程；

归并排序 ： 递归分解、合并过程(递归结束判断就是序列中元素只有一个)；

合并过程的伪代码：

合并序列A的俩个子序列A[p...q]，A[q+1...s]且都是已经排序好的子序列

设置∞为元素的最大值

MERGE(A ， p ， q ， s) {

      // 为了方便表示给A[p...q]，A[q+1...s]赋值L和R序列

     L[1...q-p+1] = A[p,q];

     R[1...s-q]= A[q+1,s] ;

     // 分别给L和R序列设置一个最大值

     L[q-p] = ∞;

     R[s+1] = ∞;

    // 定义俩个变量存储L和R中元素的位置

    i = 1; j = 1;

    for(k = p; k<= s; k++) {

         if(L[i] <= R[j]){

            A[k] = L[i]

            i++;

        } else {

           A[k] = R[j];

           j++;

       }

     }

}

合并过程时间复杂度

影响因素 ： 要合并的项数 即代码(s-p)的个数

合并过程时间复杂度 ： Θ(n) (要合并项数)

归并排序的伪代码

MERGE-SORT(A  ,  p ,  s) {

       if(p < s) {

          // 对(s-p)/2向下取整

          q = ↓[(s-p)/2]

          MERGE-SORT(A  ,  p  ,  q);

          MERGE-SORT(A  ,  q+1  ,  s);

          MERGE(A ， p ， q ， s);

      }

}

归并排序时间复杂度

影响因素 : 排序项数n；

注：排序项数会影响分解次数，同时也就调用合并次数；

分解次数为↑lg(n) 以2为底数求n的对数向上取整数；

合并次数为n-1

时间复杂Θ(nlgn) 

数据结构与算法-归并排序

原文：https://www.cnblogs.com/zhang-feng/p/11950647.html