字数 914，阅读大约需 5 分钟
C#实现归并排序与快速排序
以下是使用 C# 实现的归并排序和快速排序算法代码：
using System;
using System.Collections.Generic;
publicclassSortingAlgorithms
{
// 归并排序入口方法
public static void MergeSort<T>(T[] arr) where T : IComparable<T>
{
if (arr == || arr.Length <= 1)
return;
MergeSort(arr, 0, arr.Length - 1);
}
// 归并排序递归实现
private static void MergeSort<T>(T[] arr, int left, int right) where T : IComparable<T>
{
if (left < right)
{
int mid = left + (right - left) / 2;
MergeSort(arr, left, mid); // 排序左半部分
MergeSort(arr, mid + 1, right); // 排序右半部分
Merge(arr, left, mid, right); // 合并两个有序数组
}
}
// 合并两个有序子数组
private static void Merge<T>(T[] arr, int left, int mid, int right) where T : IComparable<T>
{
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
T[] L = new T[n1];
T[] R = new T[n2];
// 拷贝数据到临时数组
Array.Copy(arr, left, L, 0, n1);
Array.Copy(arr, mid + 1, R, 0, n2);
// 合并临时数组
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
if (L[i].CompareTo(R[j]) <= 0)
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// 拷贝剩余元素
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// 快速排序入口方法
public static void QuickSort<T>(T[] arr) where T : IComparable<T>
{
if (arr == || arr.Length <= 1)
return;
QuickSort(arr, 0, arr.Length - 1);
}
// 快速排序递归实现
private static void QuickSort<T>(T[] arr, int low, int high) where T : IComparable<T>
{
if (low < high)
{
int pi = Partition(arr, low, high); // 获取分区点
QuickSort(arr, low, pi - 1); // 排序左分区
QuickSort(arr, pi + 1, high); // 排序右分区
}
}
// Lomuto分区方案
private static int Partition<T>(T[] arr, int low, int high) where T : IComparable<T>
{
T pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1; // 较小元素的分界点
for (int j = low; j < high; j++)
{
if (arr[j].CompareTo(pivot) < 0)
{
i++;
Swap(arr, i, j); // 交换元素
}
}
Swap(arr, i + 1, high); // 将基准放到正确位置
return i + 1; // 返回基准索引
}
// 交换数组元素
private static void Swap<T>(T[] arr, int i, int j)
{
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 测试代码
public static void Main()
{
int[] numbers = { 12, 11, 13, 5, 6, 7 };
Console.WriteLine("Original array:");
PrintArray(numbers);
// 测试归并排序
MergeSort(numbers);
Console.WriteLine("\nSorted with MergeSort:");
PrintArray(numbers);
int[] numbers2 = { 10, 7, 8, 9, 1, 5 };
Console.WriteLine("\nNew array for QuickSort:");
PrintArray(numbers2);
// 测试快速排序
QuickSort(numbers2);
Console.WriteLine("\nSorted with QuickSort:");
PrintArray(numbers2);
}
// 辅助方法：打印数组
private static void PrintArray<T>(T[] arr)
{
foreach (T item in arr)
{
Console.Write(item + " ");
}
Console.WriteLine();
}
}算法说明：
归并排序（Merge Sort）
1. 分治策略：
o 将数组分成两半 o 递归排序左右子数组 o 合并两个有序子数组
o 最优/平均/最差：O(n log n) o 空间复杂度：O(n)（需要临时数组）
o 稳定排序 o 适合链表排序 o 需要额外空间
快速排序（Quick Sort）
1. 分治策略：
o 选择基准元素（pivot） o 分区：将小于基准的放在左侧，大于基准的放在右侧 o 递归排序左右分区
o 最优/平均：O(n log n) o 最差：O(n^2)（当数组已排序时） o 空间复杂度：O(log n)（递归栈）
o 不稳定排序 o 通常比归并排序快（常数因子更小） o 原地排序（不需要额外空间）
测试输出：
Original array:
12 11 13 5 6 7
Sorted with MergeSort:
5 6 7 11 12 13
New array for QuickSort:
10 7 8 9 1 5
Sorted with QuickSort:
1 5 7 8 9 10 这两个实现都使用了泛型，支持任何实现了 IComparable<T> 接口的数据类型，并通过 Lomuto 分区方案实现了快速排序。