c++集計ソートの実装

0紹介
集計ソートは一般的なソートアルゴリズムであり,時間複雑度o(nl o g n)o(nlogn)o(nlogn)である.それは経典の分治アルゴリズムの応用で、このアルゴリズムを勉強して、順序そのものを学ぶだけではなくて、更に重要なのは分治思想を体得します.具体的なアルゴリズム手順について説明します.
1 2つの配列を結合
集計ソートアルゴリズムを紹介する前に,2つの秩序配列をどのように結合するかを考慮してみてはいかがでしょうか.この問題はLeetcode 88問題にもあるので、まず手を練習してから帰ってきてください.この問題は難しくないが,集計される2つの配列が同じ配列numsにあると仮定し,1番目の配列の左右の境界はleftとrightEdge−1であり,2番目の配列の左右の境界はrightEdgeとrightである.tempは連結を補助する配列でありnums値と初期は同じである.では、2つのポインタi,jをそれぞれ2つの配列の左境界から比較し、ある配列の値が遍歴されるまで小さい数をtempに書き込み、残りの値をtempに書き込み続け、最後にtempの値をnumsに書き込むだけでよい.実装コードは次のとおりです.

void mergeArray(vector<int>&nums,vector<int>&temp,int left,int rightEdge,int right)
{
    int leftEdge = rightEdge - 1;
    int cur = left,i,j;
    for(i = left,j = rightEdge; i <= leftEdge && j <= right; ++cur)
    {
        if(nums[i] <= nums[j])
            temp[cur] = nums[i++];
        else
            temp[cur] = nums[j++];
    }
    if(i <= leftEdge)
    {
        for(; i <= leftEdge;i++)
            temp[cur++] = nums[i];
    }
    else
    {
        for(; j <= rightEdge; j++)
            temp[cur++] = nums[j];
    }
    for(int k = left; k <= right; ++k)//  nums
        nums[k] = temp[k];
}

2集計ソートの実装
2つの秩序配列を統合する操作を完全に理解し、独立してコードを書くことができて、前のleetcode問題を通過した場合は、集計ソートを把握するまで遠くないことをおめでとうございます.集計操作を実現するには再帰を用い,ソート対象配列を2部に分けてそれぞれ再帰的にソートし,最後に左右の配列を並べ替えてマージすればよいという考え方である.コードはわずか数行しかないが,再帰関数に慣れていない友人でもよく考えるのは難しい.配列{5,2}のような小さな配列から考えてみてください.mergeSortを使用すると実際に{2,5}に直接マージされます.配列{5,2,7,3}については,まず再帰的なソート{5,2},{7,3}であり,結果を遡って{2,5},{3,7}をマージする.大きな配列に対しても同様に類推できる.コードは次のように実装されます.

void mergeSort(vector<int>& nums,vector<int>&temp,int left,int right)
{
    if(left < right)
    {
        int mid = (left + right) / 2;
        mergeSort(nums,temp,left,mid);
        mergeSort(nums,temp,mid+1,right);
        mergeArray(nums,temp,left,mid+1,right);
    }
}