字数 914，阅读大约需 5 分钟

C#实现归并排序与快速排序

以下是使用 C# 实现的归并排序和快速排序算法代码：

using System;
using System.Collections.Generic;

publicclassSortingAlgorithms
{
// 归并排序入口方法
public static voidMergeSort<T>(T[] arr) where T : IComparable<T>
{
if (arr == || arr.Length <=1)
return;

MergeSort(arr,0, arr.Length -1);
}

// 归并排序递归实现
private static voidMergeSort<T>(T[] arr,intleft,intright) where T : IComparable<T>
{
if (left < right)
{
intmid = left + (right - left) /2;
MergeSort(arr, left, mid); // 排序左半部分
MergeSort(arr, mid +1, right); // 排序右半部分
Merge(arr, left, mid, right); // 合并两个有序数组
}
}

// 合并两个有序子数组
private static voidMerge<T>(T[] arr,intleft,intmid,intright) where T : IComparable<T>
{
intn1 = mid - left +1;
intn2 = 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);

// 合并临时数组
inti =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 voidQuickSort<T>(T[] arr) where T : IComparable<T>
{
if (arr == || arr.Length <=1)
return;

QuickSort(arr,0, arr.Length -1);
}

// 快速排序递归实现
private static voidQuickSort<T>(T[] arr,intlow,inthigh) where T : IComparable<T>
{
if (low < high)
{
intpi = Partition(arr, low, high); // 获取分区点
QuickSort(arr, low, pi -1); // 排序左分区
QuickSort(arr, pi +1, high); // 排序右分区
}
}

// Lomuto分区方案
private staticintPartition<T>(T[] arr,intlow,inthigh) where T : IComparable<T>
{
T pivot = arr[high]; // 选择最后一个元素作为基准
inti = low -1; // 较小元素的分界点

for (intj = 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 voidSwap<T>(T[] arr,inti,intj)
{
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

// 测试代码
public static voidMain
{
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 voidPrintArray<T>(T[] arr)
{
foreach (T item in arr)
{
Console.Write(item +" ");
}
Console.WriteLine;
}
}

算法说明：

归并排序（Merge Sort）

1. 分治策略：

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

2. 时间复杂度：

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

3. 特点：

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

快速排序（Quick Sort）

1. 分治策略：

o 选择基准元素（pivot）
o 分区：将小于基准的放在左侧，大于基准的放在右侧
o 递归排序左右分区

2. 时间复杂度：

o 最优/平均：O(n log n)
o 最差：O(n^2)（当数组已排序时）
o 空间复杂度：O(log n)（递归栈）

3. 特点：

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

七桃资源网

C#实现归并排序与快速排序_c# 排序算法

C#实现归并排序与快速排序

算法说明：

归并排序（Merge Sort）

快速排序（Quick Sort）

测试输出：