歸並排序 C語言實現：分治法與歸並操作詳解

算法原理

歸並排序採用分治策略：

1. 分解：將數組不斷二分，直到單元素（有序）。
2. 解決：遞歸排序左右子數組。
3. 合併：將兩個有序子數組歸並為一個有序數組。

歸並操作步驟

1. 申請臨時數組，大小 = 兩有序序列長度之和。
2. 雙指針分別指向兩序列起始。
3. 比較指針元素，較小者放入臨時數組，推進指針。
4. 某序列耗盡後，將另一序列剩餘元素直接複製。

完整代碼

#include <stdlib.h>
#include <malloc.h>

void merge(int src[], int des[], int low, int high, int mid) {
    int i = low, j = mid + 1, k = low;
    while (i <= mid && j <= high) {
        des[k++] = (src[i] < src[j]) ? src[i++] : src[j++];
    }
    while (i <= mid) des[k++] = src[i++];
    while (j <= high) des[k++] = src[j++];
}

void MSort(int src[], int des[], int low, int high, int max_size) {
    if (low == high) {
        des[low] = src[low];
    } else {
        int mid = (low + high) / 2;
        int* tmp = (int*)malloc(sizeof(int) * max_size);
        if (tmp) {
            MSort(src, tmp, low, mid, max_size);
            MSort(src, tmp, mid + 1, high, max_size);
            merge(tmp, des, low, high, mid);
            free(tmp);
        }
    }
}

void Merge_Sort(int arr[], int low, int high, int len) {
    MSort(arr, arr, low, high, len);
}

int main(void) {
    int arr[10];
    for (int i = 0; i < 10; i++) arr[i] = rand() % 100;
    printf("Before: "); for (int i = 0; i < 10; i++) printf("%d ", arr[i]);
    Merge_Sort(arr, 0, 9, 10);
    printf("\nAfter:  "); for (int i = 0; i < 10; i++) printf("%d ", arr[i]);
    return 0;
}

運行結果

Before: 41 67 34 0 69 24 78 58 62 64
After:  0 24 34 41 58 62 64 67 69 78

複雜度與特性

• 時間：O(n log n) 穩定。
• 空間：O(n) 輔助數組。
• 穩定排序：相等元素相對順序不變。