您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

二路歸並排序算法實現：完整 C 語言程式碼詳解

編輯：關於C語言

二路歸並排序算法實現：完整 C 語言程式碼詳解

歸並排序是分治法思想的經典應用，具有穩定、時間複雜度固定為 O(n log n) 的特點。本文將詳細講解二路歸並排序的核心邏輯，並提供完整的 C 語言實現程式碼，幫助你徹底掌握這一基礎排序算法。

算法核心思想

歸並排序遵循「分治」策略，主要包含三個步驟：

分解：將長度為 n 的序列分成兩個長度為 n/2 的子序列。
解決：遞歸地對兩個子序列進行歸並排序（直到子序列長度為 1，自然有序）。
合併：將兩個已排序的子序列合併成一個有序序列（即「二路歸並」）。

二路歸並合併邏輯

合併兩個有序序列時，設置兩個指針分別指向兩序列的起始位置，比較指針所指元素，將較小者放入臨時數組，並移動相應指針。重複此過程直到某一序列耗盡，最後將另一序列剩餘元素直接複製到臨時數組尾部。最終將臨時數組內容複製回原數組對應區間。

完整 C 語言實現

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>

using namespace std;

// 生成隨機數組
void Random(int a[], int n) {
    int i = 0;
    srand((unsigned)time(NULL));
    while (i < n) {
        a[i++] = rand();
    }
}

// 歸並操作：合併兩個有序子數組 a[low..mid] 和 a[mid+1..high]
void merge(int *a, int low, int mid, int high) {
    int k = 0;
    int begin1 = low, end1 = mid;
    int begin2 = mid + 1, end2 = high;
    // 申請臨時空間
    int *temp = (int *)malloc((high - low + 1) * sizeof(int));

    // 雙指針合併
    while (begin1 <= end1 && begin2 <= end2) {
        if (a[begin1] <= a[begin2])
            temp[k++] = a[begin1++];
        else
            temp[k++] = a[begin2++];
    }
    // 處理剩餘元素
    if (begin1 <= end1)
        memcpy(temp + k, a + begin1, (end1 - begin1 + 1) * sizeof(int));
    else
        memcpy(temp + k, a + begin2, (end2 - begin2 + 1) * sizeof(int));

    // 複製回原數組
    memcpy(a + low, temp, (high - low + 1) * sizeof(int));
    free(temp); // 釋放臨時空間
}

// 歸並排序遞歸函數
void merge_sort(int *a, unsigned int begin, unsigned int end) {
    if (begin < end) {
        int mid = begin + ((end - begin) >> 1); // 防止溢出
        merge_sort(a, begin, mid);       // 排序左半部
        merge_sort(a, mid + 1, end);     // 排序右半部
        merge(a, begin, mid, end);       // 合併
    }
}

int main() {
    int a[20];
    Random(a, 20);
    cout << "排序前: ";
    for (int i = 0; i < 20; i++) cout << a[i] << " ";
    cout << endl;

    merge_sort(a, 0, 19);

    cout << "排序後: ";
    for (int i = 0; i < 20; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}