挑战程序设计竞赛选读-归并排序

高等排序

归并排序

之前介绍的排序算法，如插入排序、选择排序具有高达$O(N^2)$级的复杂度，使它们在面对大规模输入时无能为力。归并排序利用分治思想，可将排序复杂度降低到$O(nlogn)$量级，大大加快了排序速度。

基本原理：将一未排序序列归分为两个子序列，对子序列排序后，将他们按顺序合并，并对子序列递归进行上述过程。如何正确的合并两个已排序序列是归并排序的核心。

复杂度：划分到最后一层时，可得$N$个单独元素，因此最多可划分至$lo{g}_{2}N$层，每层总的元素均为$N$，每层进行合并操作时，共需进行$N$次比较，由此完成整个合并（排序完毕）共需$Nlo{g}_{2}N$次比较，即归并排序的时间复杂度为$NlogN$级。

排序图解：

C++实现：

void merge(vector<int> &a, int left,int mid,int right)
{
    int n1 = mid - left; //两个序列长度
    int n2 = right - mid;

    vector<int> L;
    vector<int> R;

    for(int i = 0;i < n1;i++) L.push_back(a[left+i]);
    for(int i = 0;i < n2;i++) R.push_back(a[mid+i]) ; 
    L.push_back(INT32_MAX); //两个序列后插入足大的数
    R.push_back(INT32_MAX);

    int i = 0; 
    int j = 0;
    for(int k = left;k<right;k++) //
    {
        if(L[i]<=R[j])
        {
        //取左右两个首元素小者，放入已排序列，并将此首元素后移,且待i或j增加到INT32_MAX时，它注定不会再被放到已排序列了
            a[k] = L[i++]; 
        }else
        {
            a[k] = R[j++];
        }
    }
}

void mergeSort(vector<int> &a,int left,int right)
{
    if(left + 1 < right)
    {
        int mid = (left + right)/2;
        mergeSort(a,left,mid); //左
        mergeSort(a,mid,right); //右
        merge(a,left,mid,right); //合并
    }
}

rust实现（待更新）：