劍指offer之歸并排序

1 問題

是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。歸并排序是一種穩(wěn)定的排序方法


 
2 分析過程

          1 4 3 2 6 8 7 5
     
       1 4 3 2      6 8 7 5
     
    1 4    3 2      6 8     7 5   
     
    1 4    2 3      6 8     5 7
     
       1 2 3 4      5 6 7 8
     
          1 2 3 4 5 6 7 8

這里最關(guān)鍵的就是我們需要分析比如我們分治后變成了1 、4 和 2 、3這2部分?jǐn)?shù)據(jù)，我們現(xiàn)在需要對這4個(gè)數(shù)排序，如果我們直接在這個(gè)數(shù)組里面操作下標(biāo)對比，感覺分析起來很復(fù)雜，那我們可以借助輔助數(shù)組來分析，這個(gè)輔助數(shù)組的大小也是4，然后分別在2個(gè)數(shù)組1、4里面搞一個(gè)首指針，在2、3里面搞一個(gè)首指針，然后分別進(jìn)行對比，然后小的數(shù)據(jù)放入輔助數(shù)組，哪個(gè)首指針插入輔助數(shù)組我么就向后移動，指導(dǎo)右一個(gè)手指針移動到尾巴，我們就結(jié)束比較，然后我們把右一個(gè)數(shù)組里面沒有到尾巴的首指針再次移到尾巴，賦值給輔助數(shù)組就可以，然后我們輔助數(shù)組是排序好的元素，我們再把輔助元素里面的數(shù)據(jù)賦值給原數(shù)組。

      1、           4                      2、       3
     
    i = start                           j = mid+1    end

對比數(shù)據(jù)時(shí)候循環(huán)終止條件

    while (i != mid + 1 && j != end + 1)
     
    {
     
    }
     


 
3 代碼實(shí)現(xiàn)

    #include <stdio.h>
     
    void merge(int* source, int* temp, int start, int mid, int end)
    {
        if (source == NULL || temp == NULL)
        {
            printf("merge source or temp is NULL\n");
            return;
        }
        int i = start, j = mid + 1, k = start;
        while (i != mid + 1 && j != end + 1)
        {
            if (source[i] > source[j])
                temp[k++] = source[j++];
            else
                temp[k++] = source[i++];
        }
        while (i != mid + 1)
            temp[k++] = source[i++];
        while (j != end + 1)
            temp[k++] = source[j++];
        for(int h = start; h <= end; ++h)
        {
            source[h] = temp[h];   
        }
    }
     
    void mergeSort(int* source, int* temp, int start, int end)
    {
        if (source == NULL || temp == NULL)
        {
            printf("mergeSort source or temp is NULL\n");
            return;
        }
        if (start < end)
        {
            int mid = start + (end - start) / 2;
            mergeSort(source, temp, start, mid);
            mergeSort(source, temp, mid + 1, end);
            merge(source, temp, start, mid, end);
        }
    }
     
    int main(void) {
        int source[] = {2, 3, 1, 5, 4, 9, 8, 6, 7};
        int length =  sizeof(source) / sizeof(int);
        int temp[9];
        mergeSort(source, temp, 0, length - 1);
        for (int i = 0; i < length; ++i)
        {
            printf("%d\t", temp[i]);
        }
        return 0;
    }

 

4 運(yùn)行結(jié)果

1    2    3    4    5    6    7    8    9   


 
5 總結(jié)

歸并排序，我們需要對數(shù)組里面的幾個(gè)子數(shù)組元素進(jìn)行對比然后移動下標(biāo)操作，感覺非常復(fù)雜，這個(gè)時(shí)候我們應(yīng)該借助輔助數(shù)組來實(shí)現(xiàn)，不就是對比2個(gè)數(shù)組里面的數(shù)據(jù)嗎？我們把輔助數(shù)組的大小設(shè)置2個(gè)數(shù)組元素大小之和，然后搞2個(gè)首指針，對比，然后哪個(gè)數(shù)據(jù)小，就插入到輔助數(shù)組，然后移動相應(yīng)的指針就行，然后有一個(gè)數(shù)組里面的數(shù)據(jù)肯定都會插入到輔助數(shù)組，我們再把另外一個(gè)數(shù)組里面剩余的元素插入輔助數(shù)組，輔助數(shù)組就排序好了，然后我們再把輔助數(shù)組輔助給原數(shù)組就ok了。

1 、4 和 2 、3

輔助數(shù)組里面的值變化

    1    *      *      *
     
    1    2     *      *
     
    1    2     3     *
     
    1    2     3     4

歸并排序用到了輔助數(shù)組和2首指針?biāo)枷耄容o助數(shù)組排序好了再賦值給原數(shù)組，打死也不要忘記。

 

這個(gè)問題的本質(zhì)我們需要知道兩個(gè)排序的數(shù)組，如果能移動里面的數(shù)據(jù)，確保兩個(gè)數(shù)組的數(shù)據(jù)依次是都是排序的，比如我們數(shù)組如下

int source[] = {2, 6, 1, 4, 5, 9, 3, 7, 8};

 現(xiàn)在我們把這個(gè)數(shù)組里面的部分原始分割成2部分，列如第一個(gè)元素2和第二個(gè)元素6是一個(gè)子數(shù)組，第三個(gè)元素1和第四個(gè)元素4是一個(gè)子數(shù)組，每個(gè)子數(shù)組排序都好了，我們現(xiàn)在需要把這個(gè)2個(gè)子數(shù)組里面的數(shù)據(jù)進(jìn)行排序，也就是2個(gè)子數(shù)組的起始下標(biāo)是0~1  2~3排序好了后把原數(shù)組變成

1    2    4    6    5    9    3    7    8

我們實(shí)現(xiàn)標(biāo)準(zhǔn)的通用代碼如下

    #include <stdio.h>
     
    void printDatas(int* datas, int len)
    {
        for (int i = 0; i < len; ++i)
        {
            printf("%d\t", datas[i]);
        }
        printf("\n");
    }
     
    void sort(int* datas, int start1, int end1, int start2, int end2)
    {
        if (datas == NULL)
        {
            printf("datas is NULL\n");
            return;
        }
        if (start1 > end1 || start2 > end2)
        {
            printf("start1 > end1 || start2 > end2\n");
            return;
        }
        int length = end1 - start1 + end2 - start2 + 2;
        int copy[length];
        int i = start1, j = end1, k = start2, h = end2, m = 0, n = 0;
        //用2個(gè)指針把指向的值進(jìn)行對比，然后向右移動，這里需要要求2個(gè)數(shù)組都是排序好的，
        while (i != j + 1 && k != h + 1)
        {
            if (datas[i] > datas[k])
            {
                copy[m++] = datas[k++];
            }
            else
            {
                copy[m++] = datas[i++];
            }
        }
        //把剩余的一個(gè)數(shù)組里面的值賦值給我們的copy數(shù)組
        while (i != j + 1)
             copy[m++] = datas[i++];
        while (k != h + 1)
             copy[m++] = datas[k++];   
         //把copy數(shù)組再賦值給原數(shù)組
        printDatas(copy, length);
        i = start1;
        k = start2;
        for (; n <= end1 - start1; ++n)
        {
             datas[i++] = copy[n];
        }
        for (; n < length; ++n)
        {
            datas[k++] = copy[n];
        }
    }
     
    int main(void) {
        int source[] = {2, 6, 1, 4, 5, 9, 3, 7, 8};
        int length =  sizeof(source) / sizeof(int) ;
        printDatas(source, length);
        int temp[9];
        sort(source, 0, 1, 2, 3);
        printDatas(source, length);
        return 0;
    }
    

運(yùn)行結(jié)果如下

1    2    4    6    5    9    3    7    8

現(xiàn)在如果我的2個(gè)子數(shù)組的起始下標(biāo)不是0~1和2~3，是0~1和6~8，我們把上面的函數(shù)

    sort(source, 0, 1, 6, 8);

我們再看運(yùn)行結(jié)果

2    3    1    4    5    9    6    7    8

注意我們這這個(gè)sort函數(shù)（void sort(int* datas, int start1, int end1, int start2, int end2)），不滿足兩個(gè)子數(shù)組數(shù)據(jù)有交叉的情況，但是對于兩個(gè)數(shù)組的長度沒有限制（在合法情況），而且這個(gè)兩個(gè)數(shù)組可以不連續(xù)， 原始的5個(gè)數(shù)組是1 2 3 7 8 現(xiàn)在變成了2 3 6 7 8，說明沒毛病

 
    然后我們歸并排序里面，只不過我們的end1就是mid值，然后start2的值是mid + 1的值，兩個(gè)子數(shù)組是連續(xù)的，然后長度也是一致，屬于上面的特殊情況。

 
歸并排序是穩(wěn)定排序算法，適合子數(shù)組序列排好序。



作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)