C語言歸並排序算法原理與完整代碼實現

什麼是歸並排序？

歸並排序是一種基於分治策略的穩定排序算法，時間複雜度穩定為 O(n log n)，無論輸入數據分佈如何，性能表現一致。它是「分治法」的經典應用。

算法核心思想

1. 分解：將待排序序列遞歸拆分為兩半，直到每個子序列長度為 1
2. 解決：長度為 1 的序列天然有序
3. 合併：將兩個有序子序列合併為一個有序序列，層層向上合併，最終得到完整有序序列

詳細操作步驟

步驟 1：遞歸分解

設序列下標範圍為 first 到 last，中間點 mid = (first + last) / 2，分解為左半部 [first, mid] 和右半部 [mid+1, last]，遞歸分解直到區間長度為 1。

步驟 2：合併有序序列

合併兩個有序子序列 A[low..mid] 和 A[mid+1..high]：

• 申請臨時數組 tmp 存放合併結果
• 雙指針遍歷兩子序列，較小元素先放入 tmp
• 其中一序列耗盡後，將另一序列剩餘元素直接拷貝
• 將 tmp 拷貝回原數組對應區間

完整 C 語言代碼實現

#include <stdio.h>
#include <stdlib.h>

#define N 7

void merge(int arr[], int low, int mid, int high) {
    int *tmp = (int *)malloc((high - low + 1) * sizeof(int));
    int left_low = low, left_high = mid;
    int right_low = mid + 1, right_high = high;
    int k = 0;
    
    // 雙指針合併
    while (left_low <= left_high && right_low <= right_high) {
        if (arr[left_low] <= arr[right_low])
            tmp[k++] = arr[left_low++];
        else
            tmp[k++] = arr[right_low++];
    }
    // 處理剩餘元素
    while (left_low <= left_high) tmp[k++] = arr[left_low++];
    while (right_low <= right_high) tmp[k++] = arr[right_low++];
    
    // 拷貝回原數組
    for (int i = 0; i < high - low + 1; i++)
        arr[low + i] = tmp[i];
    free(tmp);
}

void mergeSort(int arr[], int first, int last) {
    if (first < last) {
        int mid = (first + last) / 2;
        mergeSort(arr, first, mid);
        mergeSort(arr, mid + 1, last);
        merge(arr, first, mid, last);
    }
}

int main() {
    int a[N] = {32, 12, 56, 78, 76, 45, 36};
    
    printf("排序前：\n");
    for (int i = 0; i < N; i++) printf("%d\t", a[i]);
    
    mergeSort(a, 0, N - 1);
    
    printf("\n排序後：\n");
    for (int i = 0; i < N; i++) printf("%d\t", a[i]);
    printf("\n");
    return 0;
}

運行結果

排序前：32 12 56 78 76 45 36
排序後：12 32 36 45 56 76 78

算法特性分析

圖解合併過程

以序列 [32, 12, 56, 78, 76, 45, 36] 為例：

1. 分解：[32,12,56,78] + [76,45,36] → 繼續分解至單元素
2. 合併：[32]+[12]→[12,32]，[56]+[78]→[56,78]
3. 再合併：[12,32]+[56,78]→[12,32,56,78]
4. 最終合併得到完整有序序列