經典排序算法 C 實現：直接插入排序與二分歸併排序深度解析

經典排序算法 C 實現：直接插入排序與二分歸併排序深度解析

排序是計算機科學基石。本文實現並分析兩種代表性算法：直接插入排序（簡單、穩定、小數據優）與 二分歸併排序（分治、穩定、大數據優）。

一、直接插入排序

思想：將數組分為「有序區」與「無序區」，初始有序區含首元素。每趟從無序區取首元素，在有序區中從後向前掃描找到插入位置，移動元素騰出空位插入。共 n-1 趟。

void move(int start, int end, int* s, int e) {
    for (int t = end; t >= start; t--) s[t+1] = s[t];
}
void InsertSort(int* s, int n) {
    for (int i = 1; i < n; i++) {
        int t = s[i];
        int j;
        for (j = i-1; j >= 0; j--)
            if (t >= s[j]) { move(j+1, i-1, s, t); s[j+1] = t; break; }
        if (j < 0) { move(0, i-1, s, t); s[0] = t; }
    }
}

特性：穩定、原地、最好 O(n)（已有序）、最壞/平均 O(n²)、空間 O(1)。適合小規模或近乎有序數據。

二、二分歸併排序

思想：分治法。遞歸將區間 [s, t] 二分至單元素，再合併兩個有序子區間。合併需輔助數組，雙指針比較歸併。

void Merge(int* s, int start, int mid, int end) {
    int* s1 = malloc(sizeof(int) * (end - start + 1));
    int t = 0, i = start, j = mid + 1;
    while (i <= mid && j <= end)
        s1[t++] = (s[i] > s[j]) ? s[j++] : s[i++];
    while (i <= mid) s1[t++] = s[i++];
    while (j <= end) s1[t++] = s[j++];
    for (int k = 0; k < t; k++) s[start++] = s1[k];
    free(s1);
}
void MergeSort(int* s, int start, int end) {
    if (end - start == 0) return;
    if (end - start == 1) {
        if (s[end] < s[start]) { int tmp = s[start]; s[start] = s[end]; s[end] = tmp; }
        return;
    }
    int mid = (end - start) / 2 + start;
    MergeSort(s, start, mid);
    MergeSort(s, mid + 1, end);
    Merge(s, start, mid, end);
}

特性：穩定、非原地（需 O(n) 輔助空間）、時間 O(n log n) 穩定、適合大規模、鏈表、外部排序。

測試樣例驗證

// 輸入: 10,4,6,3,8,2,5,7
// 插入排序輸出: 2 3 4 5 6 7 8 10
// 歸併排序輸出: 2 3 4 5 6 7 8 10

總結與選擇指南

理解算法的適用邊界，比死記代碼更重要。