今天我們繼續來講排序算法，歸并排序，難度一般，但是效率也還不錯。

老規矩，先搞清楚原理，再寫代碼。

歸并排序分為兩個步驟，先是拆分，然后再合并。

我們先來看下合并。

假設有兩個有序的數組，一個是1、3、5，一個是2、4、6、8，把他們合并成一個有序的數組。

?

這個操作應該極其簡單。兩個下標，一塊新的內存。

1和2比較，1小，把1放在新的內存中，x向后走。

2和3比較，2小，把2放在內存中，y向后走。

下面依次把4和5放進去，最后x達到了末尾，y變成了6的下標，那就把y后面的數據全部放進去就行。

這個過程就是合并。

那么問題又來了，去哪找兩個有序的數組。

這個就需要對數組做拆分。

?

比如數組有8個元素，我們先從中間拆開，得到兩個數組，每個4個元素。

但是這兩個數組也不是有序的，于是對兩個數組繼續拆分。

左邊是兩個數組，每個數組兩個元素，右邊也一樣。

這樣還不夠，繼續拆分，最后得到的數組只有一個元素。

如果一個數組只有一個元素，那么它一定就是有序的。

這個過程就需要用到遞歸。

過程清楚了，下面就是用代碼來實現它。

#include 
#include 
#include 


#define SIZE     100000


void merge(int *a, int start, int mid, int end)
{
    int left_len = mid - start + 1;
    int right_len = end - mid;


    int *L = (int *)malloc(sizeof(int) * left_len);
    int *R = (int *)malloc(sizeof(int) * right_len);


    int i, k = start, j;
    for (i = 0; i < left_len; i++, k++)
    {
        L[i] = a[k];
    }


    for (i = 0; i < right_len; i++, k++)
    {
        R[i] = a[k];
    }


    for (i = 0, j = 0, k = start; i < left_len && j < right_len; k++)
    {
        if (L[i] > R[j])
        {
            a[k] = R[j++];
        }
        else
        {
            a[k] = L[i++];
        }
    }


    if (i < left_len)
    {
        for (; i < left_len; i++, k++)
        {
            a[k] = L[i];
        }
    }


    if (j < right_len)
    {
        for (; j < right_len; j++, k++)
        {
            a[k] = R[j];
        }
    }


    free(L);
    free(R);
}


void merge_sort(int *a, int start, int end)
{
    if (start >= end)
        return;


    int mid = (end + start) / 2;


    merge_sort(a, start, mid);
    merge_sort(a, mid + 1, end);


    merge(a, start, mid, end);
}


int main()
{
    int num, arr[SIZE] = {0}, i;


    //隨機產生數組
    srand(time(NULL));
    for (i = 0; i < SIZE; i++)
    {
        arr[i] = rand() % 100;
    }


    merge_sort(arr, 0, SIZE - 1);


    for (i = 0; i < SIZE; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("
");


    return 0;
}

審核編輯：劉清