歸并排序（分治算法）

之前分享過一道算法叫做：尋找一個序列中的最大子序列和，如果那個算法想通了，那麼歸并排序開起來會顯得比較簡單

歸并算法基本思路

将待排序序列R[0…n-1]看成是n個長度為1的有序序列，将相鄰的有序表成對歸并，得到n/2個長度為2的有序表；将這些有序序列再次歸并，得到n/4個長度為4的有序序列；如此反複進行下去，最後得到一個長度為n的有序序列。

綜上可知：

歸并排序其實要做兩件事：

（1）“分解”——将序列每次折半劃分。

（2）“合并”——将劃分後的序列段兩兩合并後排序。

我們先來考慮第二步，如何合并？

在每次合并過程中，都是對兩個有序的序列段進行合并，然後排序。

這兩個有序序列段分别為 data[low, center] 和 data[center, high]。

先将他們合并到一個局部的暫存數組p中，帶合并完成後再将p複制回data中。

為了友善描述，我們稱data[low, mid] 第一段，data[mid+1, high] 為第二段。

每次從兩個段中取出一個記錄進行關鍵字的比較，将較小者放入p中。最後将各段中餘下的部分直接複制到p中。

經過這樣的過程，p已經是一個有序的序列，再将其複制回data中，一次合并排序就完成了。

實作

合并兩個升序數組

void arrayMerge(int data[], int low, int center, int high){
    //建立一個臨時數組作為緩沖區用來臨時存儲兩個合并好的數組元素值
    int *p = (int*)malloc(sizeof(int)*(high - low));
    int i = low;
    int j = center;
    int k = ;//用來記錄臨時數組的下标
    while (i < center&&j < high){
        if (data[i] < data[j]){
            p[k++] = data[i++];
        }
        else{
            p[k++] = data[j++];
        }
    }
    //将剩餘的元素存入到數組中
    while(i<center){
        p[k++] = data[i++];
    }
    while (j < high){
        p[k++] = data[j++];
    }
    //将臨時數組中的元素複制到原數組中
    for (i = , j = low; j < high; j++){
        data[j] = p[i++];
    }
    //釋放臨時數組
    free(p);
}
           

歸并排序

void mergeSort(int data[], int low, int high){
    //如果目前序列中隻剩下一個元素，傳回
    if (high-low== ){
        return;
    }
    int center = (high + low) / ;
    //左二分排序
    mergeSort(data, low,center);
    //右二分排序
    mergeSort(data, center, high);
    //合并兩個升序數組
    arrayMerge(data, low, center, high);
}
           

測試

int main(void){
    int data[8] = { 3, 2, 5, 8, 4, 7, 6, 9 };
    mergeSort(data,0,8);
    for (int i = ; i < ; i++){
        printf("%d ",data[i]);
    }
    system("pause");
}
           

調試結果：