快捷導(dǎo)航

C++歸并排序代碼實(shí)現(xiàn)示例代碼

更新時(shí)間：2025年08月09日 11:52:13 作者：乾坤未定的黑馬

歸并排序?qū)⒋判驍?shù)組分成兩個(gè)子數(shù)組,分別對(duì)這兩個(gè)子數(shù)組進(jìn)行排序,然后將排序好的子數(shù)組合并,得到排序后的數(shù)組,這篇文章主要介紹了C++歸并排序代碼實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下

1 算法核心思想

歸并排序是一種高效的排序方式，需要用到遞歸來實(shí)現(xiàn)，我們先來看一下動(dòng)圖演示：

算法核心思想如下：

1.將數(shù)組盡量平均分成兩段。

2.將這兩段都變得有序（使用遞歸實(shí)現(xiàn)）。

3.將兩段合并。

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

首先，我們先定義一個(gè)歸并排序的函數(shù)，里面接受三個(gè)參數(shù)：

void MergeSort(int arr[], int left, int right) {
    
}

arr代表需要進(jìn)行排序的數(shù)組，left表示數(shù)組arr的最左端點(diǎn)，right表示數(shù)組arr的最右端點(diǎn)。

首先我們需要把數(shù)組分成兩段，我們可以用二分的方法：

int mid = (left + right) >> 1;

這里右移（>>為右移運(yùn)算符）1為和除以2含義相同。

也可以用防溢出，因?yàn)閘eft+right的值可能會(huì)爆int，導(dǎo)致結(jié)果錯(cuò)誤：

int mid = left + (right - left) >> 1;

然后對(duì)兩段分別進(jìn)行遞歸，第一段是[1, mid]，第二段是[mid+1, right]：

MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);

由于我們需要對(duì)數(shù)組進(jìn)行操作，但是直接在arr操作可能會(huì)導(dǎo)致原始數(shù)據(jù)丟失，但是如果再創(chuàng)建一個(gè)數(shù)組會(huì)占用內(nèi)存，所以我們可以向電腦“租借”right-left+1個(gè)空間，用關(guān)鍵字new來完成：

int* tmp = new int[right - left + 1];

注意要以指針的形式定義。

由于我們要把數(shù)組變得有序，而我們歸并排序的思想就是分而治之，然后再依次變得有序，需要用到分治的思想。那么我們先定義一些變量：

int cur = 0, cur1 = left, cur2 = mid + 1;

cur為tmp數(shù)組的元素下標(biāo)，cur1為第一段的最左端點(diǎn)，cur2為第二段的最左端點(diǎn)。

然后我們對(duì)tmp數(shù)組和arr數(shù)組進(jìn)行循環(huán)操作，這里可以用while循環(huán)，循環(huán)條件是cur1<=mid&&cur2<=right。

如果arr[cur1]比arr[cur2]更大，那么就先把a(bǔ)rr[cur2]放回tmp，否則放arr[cur1]。

代碼：

while(cur1 <= mid && cur2 <= right)
{
    if(arr[cur1] < arr[cur2])
        tmp[cur++] = arr[cur1++];
    else
        tmp[cur++] = arr[cur2++];
}

然后處理可能有的數(shù)組殘余未處理的部分：

while(cur1 <= mid)
    tmp[cur++] = arr[cur1++];
while(cur2 <= right)
    tmp[cur++] = arr[cur2++];

然后合并數(shù)組，方法跟處理時(shí)差不多的：

for(int i = 0; i < right - left + 1; i++)
    arr[left + i] = tmp[i];

就是把tmp的元素依次賦值給arr。

最有我們需要把tmp的空間還給內(nèi)存，所以我們delete一下：

delete[] tmp;

然后我們的arr就變的有序了。

但是，如果這樣寫，程序就成功被我們干崩了，因?yàn)槲覀兺泴戇f歸出口了，補(bǔ)一個(gè)遞歸出口：

if(left == right)
    return;

我們合并一下整段代碼：

void MergeSort(int arr[], int left, int right) {
    if(left == right)
        return;
    int mid = (left + right) >> 1;
    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);
    int* tmp = new int[right - left + 1];
    int cur = 0, cur1 = left, cur2 = mid + 1;
    while(cur1 <= mid && cur2 <= right)
    {
        if(arr[cur1] < arr[cur2])
            tmp[cur++] = arr[cur1++];
        else
            tmp[cur++] = arr[cur2++];
    }
    while(cur1 <= mid)
        tmp[cur++] = arr[cur1++];
    while(cur2 <= right)
        tmp[cur++] = arr[cur2++];
    for(int i = 0; i < right - left + 1; i++)
        arr[left + i] = tmp[i];
    delete[] tmp;
}