劍指offer之歸并排序 2

5 總結

歸并排序，我們需要對數組裡面的幾個子數組元素進行對比然後移動下标操作，感覺非常複雜，這個時候我們應該借助輔助數組來實作，不就是對比2個數組裡面的資料嗎？我們把輔助數組的大小設定2個數組元素大小之和，然後搞2個首指針，對比，然後哪個資料小，就插入到輔助數組，然後移動相應的指針就行，然後有一個數組裡面的資料肯定都會插入到輔助數組，我們再把另外一個數組裡面剩餘的元素插入輔助數組，輔助數組就排序好了，然後我們再把輔助數組輔助給原數組就ok了。

1 、4 和 2 、3

輔助數組裡面的值變化

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

歸并排序用到了輔助數組和2首指針思想，等輔助數組排序好了再指派給原數組，打死也不要忘記。

這個問題的本質我們需要知道兩個排序的數組，如果能移動裡面的資料，確定兩個數組的資料依次是都是排序的，比如我們數組如下

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

現在我們把這個數組裡面的部分原始分割成2部分，列如第一個元素2和第二個元素6是一個子數組，第三個元素1和第四個元素4是一個子數組，每個子數組排序都好了，我們現在需要把這個2個子數組裡面的資料進行排序，也就是2個子數組的起始下标是0~1  2~3排序好了後把原數組變成

1 2 4 6 5 9 3 7 8

我們實作标準的通用代碼如下

#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個指針把指向的值進行對比，然後向右移動，這裡需要要求2個數組都是排序好的，
    while (i != j + 1 && k != h + 1)
    {
        if (datas[i] > datas[k])
        {
            copy[m++] = datas[k++];
        }
        else 
        {
            copy[m++] = datas[i++];
        }
    }
    //把剩餘的一個數組裡面的值指派給我們的copy數組
    while (i != j + 1)
         copy[m++] = datas[i++];
    while (k != h + 1)
         copy[m++] = datas[k++];   
     //把copy數組再指派給原數組
    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;
}
 
       

運作結果如下

現在如果我的2個子數組的起始下标不是0~1和2~3，是0~1和6~8，我們把上面的函數

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

我們再看運作結果

2 3 1 4 5 9 6 7 8

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

然後我們歸并排序裡面，隻不過我們的end1就是mid值，然後start2的值是mid + 1的值，兩個子數組是連續的，然後長度也是一緻，屬于上面的特殊情況。

歸并排序是穩定排序算法，适合子數組序列排好序。