C#实现归并排序算法
以下是 C# 中的归并排序算法实现示例:
using System;
class MergeSortAlgorithm
{
// 合并两个子数组
static void Merge(int[] arr, int left, int mid, int right)
{
// 计算左子数组和右子数组的长度
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组来存储左右子数组
int[] L = new int[n1];
int[] R = new int[n2];
// 将数据复制到临时数组
for (int i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[mid + 1 + j];
// 合并临时数组到 arr
// 初始化合并过程的索引
int i_merge = 0, j_merge = 0;
int k = left;
while (i_merge < n1 && j_merge < n2)
{
if (L[i_merge] <= R[j_merge])
{
arr[k] = L[i_merge];
i_merge++;
}
else
{
arr[k] = R[j_merge];
j_merge++;
}
k++;
}
// 处理剩余的元素(如果有的话)
while (i_merge < n1)
{
arr[k] = L[i_merge];
i_merge++;
k++;
}
while (j_merge < n2)
{
arr[k] = R[j_merge];
j_merge++;
k++;
}
}
// 递归地对数组进行归并排序
static void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
// 找到中间点
int mid = left + (right - left) / 2;
// 对左子数组进行排序
MergeSort(arr, left, mid);
// 对右子数组进行排序
MergeSort(arr, mid + 1, right);
// 合并左右子数组
Merge(arr, left, mid, right);
}
}
// 打印数组
static void PrintArray(int[] arr)
{
foreach (int val in arr)
{
Console.Write(val + " ");
}
Console.WriteLine();
}
// 测试归并排序算法
public static void Main(string[] args)
{
int[] arr = { 12, 11, 13, 5, 6, 7 };
Console.WriteLine("原始数组:");
PrintArray(arr);
MergeSort(arr, 0, arr.Length - 1);
Console.WriteLine("/n排序后的数组:");
PrintArray(arr);
}
}
此示例实现了归并排序算法,包括对子数组的合并和递归排序。您可以通过在 Main
方法中设置不同的输入数组来测试算法。
编辑