【排序(C++實作)】：二分歸并排序

一、僞代碼

1.      MergeSort(A,l,r)

2.      Merge(A,l,m,r) 

二、C/C++代碼 

/******************************************************************* 

Function:Merge
Description:将兩個有序的數組A[l,m]和A[m+1,r]合并為一個有序的數組
Input:數組A及下标l，m，r
Output:有序數組A
********************************************************************/
void Merge(int A[],int l,int m,int r){
    int x = m-l+1,y=r-m;//x表示數組A[l...m]的長度，y表示數組A[m+1,r]的長度
    int *B = new int[x];
    int *C = new int[y];
    for(int i=0,j=l;i<x;i++,j++)//将A[l,m]複制到B中
        B[i]=A[j];
    for(int i=0,j=m+1;i<y;i++,j++)//将A[m+1,r]複制到C中
        C[i]=A[j];
    int i=0,j=0,k=l;//i是數組B的遊标，j是數組C的遊标，k是數組A的遊标
    while(i<x&&j<y){
        if(B[i]<=C[j])
            A[k++]=B[i++];
        else
            A[k++]=C[j++];
    }
    //如果B或者C中還有剩餘的數字，則全部複制到A中
    if(i>=x)
        while(j<y)A[k++]=C[j++];
    else
        while(i<x)A[k++]=B[i++];
}
/************************************************
Function:MergeSort
Description:對數組A[l,r]進行二分歸并排序
Input:數組A及其下标l,r
Output:有序數組A
*************************************************/
void MergeSort(int A[],int l,int r){
    if(l<r){
        int m = (l+r)/2;
        MergeSort(A,l,m);
        MergeSort(A,m+1,r);
        Merge(A,l,m,r);
    }
}
           

三、時間複雜度

由分治的思想知，對一個數組排序可以轉換為将原數組一分為二，各種排序後在合并的過程。設該算法的最壞時間複雜度為W(n)，則遞推公式如下：

其中n-1是将兩個有序數組合并成一個有序數組的時間複雜度。

解法一：

解法二：

利用https://blog.csdn.net/bqw18744018044/article/details/79596014中介紹的主定理。