C#归并排序算法实现与原理详解

归并排序的核心思想

归并排序（Merge Sort）主要依赖递归和分而治之（Divide and Conquer）的技术。其逻辑是将数据序列划分为越来越小的子表，对这些子表分别进行排序，最后再通过递归步骤将排好序的子表合并为更大的有序序列。整个流程可以概括为两个关键阶段：

1. 划分子表：不断将序列对半拆分，直到子序列仅包含一个元素（天然有序）。
2. 合并半子表：将相邻的有序子序列比较并合并为一个更大的有序序列。

第一步：理解合并算法（Merge）

在讨论整体排序前，先解析最核心的合并操作。假设有一个向量，其索引范围是 [first, last]，且该向量已经由两个排好序的子表构成，以 mid 为分界点。例如序列：

7, 10, 19, 25 | 12, 17, 21, 30, 48

其中左子表为 7, 10, 19, 25，右子表为 12, 17, 21, 30, 48。合并过程如下图所示：

合并的具体执行步骤如下：

第一步： 比较左指针 indexA 指向的元素 v[indexA]=7 和右指针 indexB 指向的元素 v[indexB]=12。取出较小者 7 放入临时向量 tempArray，并将 indexA 加 1。

第二步： 比较当前 v[indexA]=10 和 v[indexB]=12。将较小的 10 存入 tempArray，然后 indexA++。

第三步： 比较 v[indexA]=19 与 v[indexB]=12。此时右侧元素更小，将 12 存入 tempArray，然后 indexB++。

第四步至第七步： 遵循上述规则持续比对和存储，直到其中一个子表的元素全部处理完毕。结果状态如下所示：

最后一步： 若某一方还有剩余元素（如本例中左子表剩余项），直接将剩余项追加到 tempArray 末尾：

最终，将临时变量 tempArray 中的值按顺序拷贝回原向量 v，即完成了一次归并操作。

C# Merge 函数实现

以下是合并逻辑的 C# 代码实现。使用队列 Queue<int> 作为临时存储空间，通过双指针扫描两个子表。

public void Merger(int[] v, int first, int mid, int last)
{
 Queue<int> tempV = new Queue<int>();
 int indexA, indexB;
 
 // 设置起始索引，分别指向两个有序子表的开头
 indexA = first;
 indexB = mid;
 
 // 当两个子表都未遍历完时，比较元素并放入临时队列
 while (indexA < mid && indexB < last)
 {
 if (v[indexA] < v[indexB])
 { tempV.Enqueue(v[indexA]); indexA++; }
 else
 { tempV.Enqueue(v[indexB]); indexB++; }
 }
 
 // 如果左子表有剩余，直接加入临时队列
 while (indexA < mid)
 { tempV.Enqueue(v[indexA]); indexA++; }
 
 // 如果右子表有剩余，直接加入临时队列
 while (indexB < last)
 { tempV.Enqueue(v[indexB]); indexB++; }
 
 // 将排序后的元素写回原数组
 int index = 0;
 while (tempV.Count > 0)
 { v[first + index] = tempV.Dequeue(); index++; }
}

第二步：构建递归排序（MergeSort）

归并排序的完整实现需要递归调用。对于初始数据序列（例如：25, 10, 7, 19, 3, 48, 12, 17, 56, 30, 21），算法首先将其不断二分，直到不可再分，然后层层回溯进行合并。整体分割与合并的树状结构如下图所示：

C# MergeSort 递归函数

递归函数的基本逻辑是：如果区间长度大于 1，则计算中间点 mid，递归调用自身处理左右两半，最后调用 Merger 进行合并。

public void MergerSort(int[] v, int first, int last)
{
 if (first + 1 < last)
 {
 int mid = (first + last) / 2;
 MergerSort(v, first, mid);   // 排序左半部分
 MergerSort(v, mid, last);    // 排序右半部分
 Merger(v, first, mid, last); // 合并两个有序部分
 }
}

性能分析与总结

归并排序将划分子表和归并子表的过程与原数据序列的原始次序无关。这意味着无论数据是正序、逆序还是随机分布，其分解深度和合并次数都是固定的。因此，归并排序的最坏情况、最好情况和平均情况时间复杂度均为 O(n log n)，具有良好的稳定性。

完整的递归调用流程图展示了算法如何展开又收敛：

以上就是 C# 递归算法实现归并排序的详细内容，更多关于 C# 排序算法优化的资料请关注本站其它相关文章！