您现在的位置：程式碼之家 >> 編程語言 > >> .NET 網頁程式設計 >> C# >> 關於C#

C# 經典算法實現：自頂向下雙路歸並排序完整代碼與圖解

編輯：關於C#

算法原理

歸並排序採用分治策略：

分解：遞歸將陣列二分，直到單元素（有序）。
解決：單元素天然有序。
合併：將兩個有序子陣列合併為一個有序陣列。

時間複雜度 O(n log n)，空間複雜度 O(n)（需輔助陣列），穩定排序。

完整實現代碼


public static class MergeSort
{
    /// 
    /// 公開入口：排序整個陣列
    /// 
    public static void Sort(int[] array)
    {
        if (array == null || array.Length <= 1) return;
        int[] temp = new int[array.Length];
        SortRecursive(array, temp, 0, array.Length - 1);
    }

    /// 
    /// 遞歸分解 + 合併
    /// 
    private static void SortRecursive(int[] dest, int[] temp, int left, int right)
    {
        if (left >= right) return; // 基礎情況

        int mid = left + (right - left) / 2; // 防溢出
        SortRecursive(dest, temp, left, mid);       // 左半
        SortRecursive(dest, temp, mid + 1, right);  // 右半
        Merge(dest, temp, left, mid, right);        // 合併
    }

    /// 
    /// 合併兩個相鄰有序區間 [left, mid] 和 [mid+1, right]
    /// 
    private static void Merge(int[] dest, int[] temp, int left, int mid, int right)
    {
        // 1. 複製當前區間到暫存陣列
        Array.Copy(dest, left, temp, left, right - left + 1);

        int i = left;      // 左區間指標
        int j = mid + 1;   // 右區間指標
        int k = left;      // 目標陣列寫入指標

        // 2. 雙指標歸並
        while (i <= mid && j <= right)
        {
            if (temp[i] <= temp[j])
                dest[k++] = temp[i++];
            else
                dest[k++] = temp[j++];
        }

        // 3. 處理剩餘元素
        while (i <= mid) dest[k++] = temp[i++];
        while (j <= right) dest[k++] = temp[j++];
    }
}

關鍵細節解析

細節	處理方式
遞歸終止條件	`left >= right`（單元素或空區間）
中點計算	`left + (right - left) / 2` 避免整數溢出
暫存陣列	在入口處一次性分配 `new int[n]`，遞歸過程共用，避免重複分配
穩定性	`temp[i] <= temp[j]` 使用 `<=` 保證相等元素左側優先，維持穩定
邊界處理	三個 while 迴圈分別處理雙指標並進、左剩餘、右剩餘，邏輯清晰無漏洞

測試用例


int[] data = { 38, 27, 43, 3, 9, 82, 10 };
MergeSort.Sort(data);
Console.WriteLine(string.Join(", ", data)); 
// 輸出: 3, 9, 10, 27, 38, 43, 82

進階擴展：泛型版本支援任意類型


public static void Sort(T[] array, IComparer comparer = null)
{
    comparer ??= Comparer.Default;
    if (array.Length <= 1) return;
    T[] temp = new T[array.Length];
    SortRecursive(array, temp, 0, array.Length - 1, comparer);
}

private static void SortRecursive(T[] dest, T[] temp, int left, int right, IComparer cmp)
{
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    SortRecursive(dest, temp, left, mid, cmp);
    SortRecursive(dest, temp, mid + 1, right, cmp);
    Merge(dest, temp, left, mid, right, cmp);
}

private static void Merge(T[] dest, T[] temp, int left, int mid, int right, IComparer cmp)
{
    Array.Copy(dest, left, temp, left, right - left + 1);
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right)
        dest[k++] = cmp.Compare(temp[i], temp[j]) <= 0 ? temp[i++] : temp[j++];
    while (i <= mid) dest[k++] = temp[i++];
    while (j <= right) dest[k++] = temp[j++];
}