字数 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. 1. 分治策略：

• o 将数组分成两半
• o 递归排序左右子数组
• o 合并两个有序子数组

• o 最优/平均/最差：O(n log n)
• o 空间复杂度：O(n)（需要临时数组）

• o 稳定排序
• o 适合链表排序
• o 需要额外空间

快速排序（Quick Sort）

1. 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 分区方案实现了快速排序。