今天我們繼續(xù)來(lái)講排序算法，歸并排序，難度一般，但是效率也還不錯(cuò)。

老規(guī)矩，先搞清楚原理，再寫(xiě)代碼。

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

我們先來(lái)看下合并。

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

?

這個(gè)操作應(yīng)該極其簡(jiǎn)單。兩個(gè)下標(biāo)，一塊新的內(nèi)存。

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

2和3比較，2小，把2放在內(nèi)存中，y向后走。

下面依次把4和5放進(jìn)去，最后x達(dá)到了末尾，y變成了6的下標(biāo)，那就把y后面的數(shù)據(jù)全部放進(jìn)去就行。

這個(gè)過(guò)程就是合并。

那么問(wèn)題又來(lái)了，去哪找兩個(gè)有序的數(shù)組。

這個(gè)就需要對(duì)數(shù)組做拆分。

?

比如數(shù)組有8個(gè)元素，我們先從中間拆開(kāi)，得到兩個(gè)數(shù)組，每個(gè)4個(gè)元素。

但是這兩個(gè)數(shù)組也不是有序的，于是對(duì)兩個(gè)數(shù)組繼續(xù)拆分。

左邊是兩個(gè)數(shù)組，每個(gè)數(shù)組兩個(gè)元素，右邊也一樣。

這樣還不夠，繼續(xù)拆分，最后得到的數(shù)組只有一個(gè)元素。

如果一個(gè)數(shù)組只有一個(gè)元素，那么它一定就是有序的。

這個(gè)過(guò)程就需要用到遞歸。

過(guò)程清楚了，下面就是用代碼來(lái)實(shí)現(xiàn)它。

#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;


    //隨機(jī)產(chǎn)生數(shù)組
    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;
}

審核編輯：劉清