算法導論之——自然歸并排序

• • 一、百度百科→自然合并排序：
  • 二、原理圖
  • 三、C++實作自然歸并（合并）排序

一、百度百科→自然合并排序：

自然合并排序是合并排序算法的一種改進.
自然合并排序:  對于初始給定的數組,通常存在多個長度大于1的已自然排好序的子數組段.
例如,若數組a中元素為{4,8,3,7,1,5,6,2},則自然排好序的子數組段有{4,8},{3,7},{1,5,6},{2}.
構成更大的排好序的子數組段({3,4,7,8},{1,2,5,6}).繼續合并相鄰排好序的子數組段,直至整個數組已排好序.
           

二、原理圖

三、C++實作自然歸并（合并）排序

P.S. 原理挺好了解的，實作的代碼反而有點繞。

//程式名：自然歸并（合并）排序
//測試資料：arrayA[] = {1, 5, 2, 3, 6, 0, 7, 4, 8};
//step: 表示程式的運作順序
//1th： 表示下一行的語句/函數，第一次運作/調用時的實際内容/解釋，以友善了解程式。

#include <iostream>
using namespace std;
void print(int arrayA[], int n)
{
    for (int i=; i<n; ++i) {
        cout << arrayA[i] << " ";
    }
    cout << endl;
}

//GetIndex函數功能： 從arrayA_index[1]開始記錄第二個自然分組以及之後每個自然分組的 "開始下标" 
void GetIndex(int arrayA[], int arrayA_index[], int arrayA_Length, int &numOfNatureGroupings)
{
    int j = ;
    arrayA_index[j++] = ;  //第一個自然分組開始下标預設為0
    for(int i = ; i < arrayA_Length-; i++) {
        if(arrayA[i+] < arrayA[i]) {
            arrayA_index[j++] = i+;
            cout<<i+<<endl;
        }
    }
    //numOfNatureGroupings為自然分組的個數, 此次值為4，即分為四組，{1, 5}, {2, 3, 6}, {0, 7}, {4, 8}
    numOfNatureGroupings = j;   
    cout<<"j = "<<j<<endl;
}

//Merge函數功能： 合并src[left:middle]和src[middle+1:right]到dst[[left:right]
// 1th: l=第一個自然分組第一位下标; m=第一個自然分組最後一位下标; r=第二個自然分組最後一位下标;   
// 即第一次調用合并分組一、二        {1, 5}, {2, 3, 6},

// 2th: l=第三個自然分組第一位下标; m=第三個自然分組最後一位下标; r=arrayA最後一位下标;            
// 即第二次調用合并分組三、四        {0, 7}, {4, 8}
void Merge(int src[], int dst[], int left, int middle, int right)
{

    int i = left, j = middle + , k = left;
    while (i <= middle && j <= right) {
        if (src[i] <= src[j]) {
            dst[k++] = src[i++];
        } else {
            dst[k++] = src[j++];
        }
    }
    if (i > middle) {
        for (int q = j; q <= right; q++) {
            dst[k++] = src[q];
        }
    } else {
        for (int q = i; q <= middle; q++) {
            dst[k++] = src[q];
        }
    }
}

//MergePass函數功能：合并自然分組後相鄰的子數組，
//例如: roundNum=1時分别合并自然分組一、二和自然分組三、四。
//例如: roundNum=2時分别合并，已經合并了一次的{一+二}和{三+四}。
void MergePass(int left[], int right[], int arrayA_index[], int roundNum, int arrayA_Length,
 int numOfNatureGroupings)
{
    int i = ;
    //while功能：當自然分組後的子數組個數為偶數時, r = arrayA_Length, 表示恰好兩兩合并
    //1th: roundNum=1; 0<=4-2*1=2  循環兩次
    while(i <= numOfNatureGroupings -  * roundNum) {
        //1th: 0+2*1<4      r=arrayA_index[0+2*1]=arrayA_index[2]
        //2th: 2+2*1>=4     r=arrayA_Length
        int r=((i+*roundNum)<numOfNatureGroupings) ? arrayA_index[i+*roundNum]:arrayA_Length;

        //1th：left, right, arrayA_index[0], arrayA_index[1]-1, arrayA_index[2]-1
        //2th: left, right, arrayA_index[2], arrayA_index[3]-1, arrayA_Length-1
        Merge(left, right, arrayA_index[i], arrayA_index[i+roundNum]-, r-);

        //1th: i=2;
        //2th: i=4;
        i = i +  * roundNum;
    }
    //1th: 4+1>4; 4>=4; 
    if(i + roundNum < numOfNatureGroupings) {   
        Merge(left, right, arrayA_index[i], arrayA_index[i+roundNum]-, arrayA_Length-);

    } 
    else if (i < numOfNatureGroupings) {
        // 剩餘元素直接複制 
        for(int j = arrayA_index[i]; j <= arrayA_Length - ; j++) {
            right[j] = left[j];
        }
    }
}

void MergeSort(int arrayA[], int arrayA_index[], int arrayA_Length, int numOfNatureGroupings)
{
    int *arrayB = new int[arrayA_Length];
    int roundNum = ;   //roundNum表示目前是第幾輪合并

    //while功能：數組A合并到數組B，數組B再合并到數組A，一直合并到完全合并，充分利用數組空間。
    while (roundNum < numOfNatureGroupings) {
        //1th: 第一輪，合并四個自然分組
        //合并到數組B
        MergePass(arrayA, arrayB, arrayA_index, roundNum, arrayA_Length, numOfNatureGroupings);

        //1th: arrayB = {1 2 3 5 6} {0 4 7 8}       
        cout<<"arrayB = ";print(arrayB,arrayA_Length);

        //1th: roundNum=2;
        roundNum += roundNum;

        //1th: 第二輪，合并，已經合并了一次的{一+二}和{三+四}。
        //合并到數組A
        MergePass(arrayB, arrayA, arrayA_index, roundNum, arrayA_Length, numOfNatureGroupings);

        //1th: arrayA = 0 1 2 3 4 5 6 7 8 
        cout<<"arrayA = ";print(arrayA,arrayA_Length);

        //1th: roundNum=4 >= numOfNatureGroupings=4;    while函數隻運作了一遍
        roundNum += roundNum;
    }
    delete[] arrayB;
}

int main(int argc, char *argv[])
{
    int arrayA[] = {, , , , , , , , };
    int arrayA_Length = sizeof(arrayA) / sizeof(int);
    int *arrayA_index = new int[arrayA_Length];
    int numOfNatureGroupings;        // 記錄自然分組個數
    GetIndex (arrayA, arrayA_index, arrayA_Length, numOfNatureGroupings);
    MergeSort(arrayA, arrayA_index, arrayA_Length, numOfNatureGroupings);
    print(arrayA, arrayA_Length);
    delete[] arrayA_index;
    return ;
}