深入理解C#归并排序（为什么它是稳定排序的典范）

为什么归并排序是稳定的？

关键在于合并过程！

当比较左右两个子数组的元素时，如果左边元素 ≤ 右边元素，我们就先取左边的。这个“≤”中的“等于”情况，保证了相同值的元素中，原本在左边（即原数组中靠前）的元素会先被放入结果数组，从而保留了原始顺序。

C# 实现归并排序（完整代码）

下面是一个完整的、带有详细注释的 C# 归并排序实现：

using System;public class MergeSortExample{    // 主函数：启动归并排序    public static void MergeSort(int[] arr)    {        if (arr == null || arr.Length <= 1) return;        int[] temp = new int[arr.Length];        MergeSortHelper(arr, temp, 0, arr.Length - 1);    }    // 递归分治    private static void MergeSortHelper(int[] arr, int[] temp, int left, int right)    {        if (left < right)        {            int mid = left + (right - left) / 2;            MergeSortHelper(arr, temp, left, mid);      // 排序左半部分            MergeSortHelper(arr, temp, mid + 1, right); // 排序右半部分            Merge(arr, temp, left, mid, right);         // 合并两部分        }    }    // 合并两个已排序的子数组 [left..mid] 和 [mid+1..right]    private static void Merge(int[] arr, int[] temp, int left, int mid, int right)    {        // 将原数组复制到临时数组        for (int i = left; i <= right; i++)        {            temp[i] = arr[i];        }        int i = left;     // 左子数组起始索引        int j = mid + 1;  // 右子数组起始索引        int k = left;     // 合并后数组的当前索引        // 合并过程：关键在 <= 判断，保证稳定性！        while (i <= mid && j <= right)        {            if (temp[i] <= temp[j]) // 注意这里是 <=，不是 <            {                arr[k++] = temp[i++];            }            else            {                arr[k++] = temp[j++];            }        }        // 复制左子数组剩余元素（如果有）        while (i <= mid)        {            arr[k++] = temp[i++];        }        // 右子数组剩余元素已在正确位置，无需额外操作    }    // 测试示例    public static void Main()    {        int[] data = { 38, 27, 43, 3, 9, 82, 10 };        Console.WriteLine("排序前: " + string.Join(", ", data));        MergeSort(data);        Console.WriteLine("排序后: " + string.Join(", ", data));    }}  

验证稳定性的小实验

为了验证归并排序的稳定性，我们可以对包含重复值的对象进行排序。例如，定义一个 Person 类，按年龄排序，但希望同龄人的原始顺序不变：

// 简化版测试（使用元组模拟）var people = new (string name, int age)[]{    ("Alice", 25),    ("Bob", 30),    ("Charlie", 25),    ("David", 30)};// 使用归并排序按 age 排序（需自定义比较逻辑）// 结果应为：Alice(25), Charlie(25), Bob(30), David(30)// Alice 在 Charlie 前面，Bob 在 David 前面 —— 顺序保留！  

总结

通过本文，你已经掌握了：

• 什么是稳定排序及其重要性；
• C#归并排序的核心思想和实现细节；
• 为什么归并排序能保证稳定性（关键在合并时的 ≤ 判断）；
• 如何编写可读性强、结构清晰的归并排序代码。

无论你是初学者还是有一定经验的开发者，理解C#排序教程中的归并排序，都能帮助你在面试或实际项目中更自信地处理数据排序问题。记住，归并排序稳定性是它区别于快速排序等不稳定算法的重要优势之一，尤其在需要保留原始顺序的场景（如数据库多字段排序）中非常有用。

掌握稳定排序，让你的代码更可靠、更专业！