廢話不多說先上代碼

void mergeSort(int arr[], int start, int end) {
    if(start >= end)
        return;

    int middle = start + ((end - start) >> 1);

    mergeSort(arr, start, middle);
    mergeSort(arr, middle + 1, end);

    _merge(arr, start, middle, middle + 1, end);

    return;
}

void _merge(int arr[], int start1, int end1, int start2, int end2) {
    int temp[end2 - start1 + 1];
    int index = 0;
    int s1 = start1;
    int s2 = start2;

    while(s1 <= end1 && s2 <= end2) {
        if (arr[s1] < arr[s2])
        {
            temp[index++] = arr[s1++];
        } else {
            temp[index++] = arr[s2++];
        }
    }

    while(s1 <= end1)
        temp[index++] = arr[s1++];
    
    while(s2 <= end2)
        temp[index++] = arr[s2++];

    for (int i = 0; i <= end2 - start1; ++i)
    {
        arr[start1 + i] = temp[i];
    }

    return;
}
//代碼看著比較長(zhǎng)，沒有特別的東西

時(shí)間復(fù)雜度

O(n * log n) 這個(gè)時(shí)間復(fù)雜度不會(huì)變化淑履，無(wú)論是完全逆序還是已經(jīng)有序

空間復(fù)雜度

O(n) 不是原地排序

穩(wěn)定排序

是穩(wěn)定排序

算法核心思想

最經(jīng)典的分而治之的思想

圖片.png

將待排序數(shù)組從中間分為兩個(gè)待排序數(shù)組隶垮。
對(duì)兩個(gè)數(shù)組分別排序，再將兩個(gè)有序數(shù)組合并秘噪。

一步一步實(shí)現(xiàn)歸并排序

分

終止條件
數(shù)組只有一個(gè)元素就不可再分解狸吞。

void mergeSort(int arr[], int start, int end) {
    if(start >= end)
        return;
}

拆分?jǐn)?shù)組

void mergeSort(int arr[], int start, int end) {
    if(start >= end)
        return;
    //計(jì)算中間元素
    int middle = start + ((end - start) >> 1);
    //對(duì)拆分后的數(shù)組再次進(jìn)行拆分
    mergeSort(arr, start, middle);
    mergeSort(arr, middle + 1, end);
}

執(zhí)行合并
數(shù)組拆分到最小單位后進(jìn)行合并

void mergeSort(int arr[], int start, int end) {
    if(start >= end)
        return;
    //計(jì)算中間元素
    int middle = start + ((end - start) >> 1);
    //對(duì)拆分后的數(shù)組再次進(jìn)行拆分
    mergeSort(arr, start, middle);
    mergeSort(arr, middle + 1, end);
    //合并函數(shù)
    _merge(arr, start, middle, middle + 1, end);
}

治

合并兩個(gè)有序數(shù)組

void mergeSort(int arr[], int start, int end) {
    if(start >= end)
        return;
    //計(jì)算中間元素
    int middle = start + ((end - start) >> 1);
    //對(duì)拆分后的數(shù)組再次進(jìn)行拆分
    mergeSort(arr, start, middle);
    mergeSort(arr, middle + 1, end);
    //合并函數(shù)
    _merge(arr, start, middle, middle + 1, end);
}

//合并函數(shù) 
//start1、end1 是第一個(gè)數(shù)組的起始下標(biāo)
//start2指煎、end2 是第二個(gè)數(shù)組的起始下標(biāo)
void _merge(int arr[], int start1, int end1, int start2, int end2) {
    //申請(qǐng)一個(gè)臨時(shí)數(shù)組蹋偏，存儲(chǔ)合并的元素
    int temp[end2 - start1 + 1];
    int index = 0;
    //用來(lái)表示要比較的元素
    int s1 = start1;
    int s2 = start2;

    //合并兩個(gè)有序數(shù)組
    while(s1 <= end1 && s2 <= end2) {
        if(arr[s1] < arr[s2]) {
            temp[index++] = arr[s1++];
        } else {
            temp[index++] = arr[s2++];
        }
    }
    
    //將剩下的元素添加到臨時(shí)數(shù)組
    while(s1 <= end1)
        temp[index++] = arr[s1++];
    while(s2 <= end2)
        temp[index++] = arr[s2++];
    
    //將臨時(shí)數(shù)組中的變量賦值給原數(shù)組
    for(int i = 0; i <= end2 - start1; ++i) {
        arr[i + start1] = temp[i];
    }

    return;
}
//歸并排序結(jié)束

歸并排序結(jié)束了

應(yīng)該還是比較好理解，就是代碼比較復(fù)雜至壤，小心點(diǎn)別寫錯(cuò)了就可以暖侨。

都看到這里了，點(diǎn)個(gè)贊再走啊~