C# 快速排序
最后修改于 2025年3月8日
本教程探讨了 C# 中的快速排序算法，展示了如何按升序和降序对数值和文本数据进行排序。
算法 是一个结构化的步骤序列，旨在高效地解决问题或执行任务。 它是编程的基石，指导着计算逻辑。
排序 是指将数据组织成特定的顺序，例如升序（从小到大）或降序（从大到小）。 它对于数据检索和呈现等任务至关重要。
常用排序算法
以下是一些著名的排序算法
- 快速排序
- 归并排序
- 气泡排序
- 插入排序
- 选择排序
快速排序算法
快速排序是一种分而治之的算法，它选择一个枢轴元素并围绕它对数组进行分区。 小于枢轴的元素放在左边，较大的元素放在右边。
子数组被递归地排序，从而得到一个完全排序的数组。 平均时间复杂度为 O(n log n)，对于大多数数据集来说是高效的，但最坏的情况是 O(n²)。
快速排序示例
以下是使用顶层语句的 C# 数字和字符串快速排序实现。
QuickSort.cs
// QuickSort.cs
int[] QuickSort(int[] arr)
{
if (arr.Length <= 1)
{
return arr;
}
int pivot = arr[arr.Length / 2];
var left = new List<int>();
var middle = new List<int>();
var right = new List<int>();
foreach (int x in arr)
{
if (x < pivot)
{
left.Add(x);
}
else if (x == pivot)
{
middle.Add(x);
}
else
{
right.Add(x);
}
}
return [.. QuickSort(left.ToArray()), .. middle, .. QuickSort(right.ToArray())];
}
string[] QuickSortStrings(string[] arr)
{
if (arr.Length <= 1)
{
return arr;
}
string pivot = arr[arr.Length / 2];
var left = new List<string>();
var middle = new List<string>();
var right = new List<string>();
foreach (string x in arr)
{
if (string.Compare(x, pivot) < 0)
{
left.Add(x);
}
else if (string.Compare(x, pivot) == 0)
{
middle.Add(x);
}
else
{
right.Add(x);
}
}
return [.. QuickSortStrings(left.ToArray()), .. middle, .. QuickSortStrings(right.ToArray())];
}
int[] numbers = [3, 6, 8, 10, 1, 2, 1];
int[] sortedNumbers = QuickSort(numbers);
Console.WriteLine("Sorted numbers: " + string.Join(" ", sortedNumbers));
string[] words = ["banana", "apple", "cherry", "date"];
string[] sortedWords = QuickSortStrings(words);
Console.WriteLine("Sorted words: " + string.Join(" ", sortedWords));
QuickSort 方法对整数进行排序，而 QuickSortStrings 处理字符串。两者都使用中间枢轴并递归地对数据进行分区。
结果是一个新的升序排序数组。 这种方法利用了 C# 的类型系统，确保了不同数据类型的灵活性，而且方式简洁。
降序排序
以下是如何在 C# 中调整快速排序以实现降序排序。
QuickSortDesc.cs
// QuickSortDesc.cs
int[] QuickSortDesc(int[] arr)
{
if (arr.Length <= 1)
{
return arr;
}
int pivot = arr[arr.Length / 2];
var left = new List<int>();
var middle = new List<int>();
var right = new List<int>();
foreach (int x in arr)
{
if (x > pivot)
{
left.Add(x);
}
else if (x == pivot)
{
middle.Add(x);
}
else
{
right.Add(x);
}
}
return [.. QuickSortDesc(left.ToArray()), .. middle, .. QuickSortDesc(right.ToArray())];
}
string[] QuickSortStringsDesc(string[] arr)
{
if (arr.Length <= 1)
{
return arr;
}
string pivot = arr[arr.Length / 2];
var left = new List<string>();
var middle = new List<string>();
var right = new List<string>();
foreach (string x in arr)
{
if (string.Compare(x, pivot) > 0)
{
left.Add(x);
}
else if (string.Compare(x, pivot) == 0)
{
middle.Add(x);
}
else
{
right.Add(x);
}
}
return [.. QuickSortStringsDesc(left.ToArray()), .. middle, .. QuickSortStringsDesc(right.ToArray())];
}
int[] numbers = [3, 6, 8, 10, 1, 2, 1];
int[] sortedNumbersDesc = QuickSortDesc(numbers);
Console.WriteLine("Sorted numbers (descending): " + string.Join(" ", sortedNumbersDesc));
string[] words = ["banana", "apple", "cherry", "date"];
string[] sortedWordsDesc = QuickSortStringsDesc(words);
Console.WriteLine("Sorted words (descending): " + string.Join(" ", sortedWordsDesc));
QuickSortDesc 和 QuickSortStringsDesc 方法颠倒了分区逻辑 - 较大的元素放在左边，较小的元素放在右边 - 从而产生降序。
这种调整对于诸如将项目从最高到最低进行排名（例如分数）或 C# 应用程序中按字母顺序反转的列表之类的场景非常有用。
将快速排序与插入排序进行比较
快速排序的平均 O(n log n) 性能优于插入排序的 O(n²)，尤其是在大型数据集的情况下。 C# 中的这个基准说明了这种差异。
Benchmark.cs
// Benchmark.cs
using System.Diagnostics;
int[] QuickSort(int[] arr)
{
if (arr.Length <= 1)
{
return arr;
}
int pivot = arr[arr.Length / 2];
var left = new List<int>();
var middle = new List<int>();
var right = new List<int>();
foreach (int x in arr)
{
if (x < pivot)
{
left.Add(x);
}
else if (x == pivot)
{
middle.Add(x);
}
else
{
right.Add(x);
}
}
return [.. QuickSort(left.ToArray()), .. middle, .. QuickSort(right.ToArray())];
}
int[] InsertionSort(int[] arr)
{
int[] result = arr.ToArray();
for (int i = 1; i < result.Length; i++)
{
int key = result[i];
int j = i - 1;
for (; j >= 0 && key < result[j]; j--)
{
result[j + 1] = result[j];
}
result[j + 1] = key;
}
return result;
}
Random rand = new(Random.Shared.Next());
int[] data = new int[10000];
for (int i = 0; i < data.Length; i++)
{
data[i] = rand.Next(1000);
}
int[] quickData = data.ToArray();
Stopwatch sw = Stopwatch.StartNew();
QuickSort(quickData);
double quickTime = sw.Elapsed.TotalSeconds;
int[] insertData = data.ToArray();
sw = Stopwatch.StartNew();
InsertionSort(insertData);
double insertTime = sw.Elapsed.TotalSeconds;
Console.WriteLine($"Quick Sort time: {quickTime:F6} seconds");
Console.WriteLine($"Insertion Sort time: {insertTime:F6} seconds");
此代码生成 10000 个随机整数并对两种算法进行计时。 快速排序使用递归和分区，而插入排序则逐个移动元素。
由于其对数缩放，快速排序通常完成得更快 - 通常快一个数量级。 插入排序虽然更简单，但在处理大型数据时会遇到困难，因此在这里不太实用。
此类比较有助于开发人员根据 C# 项目中的数据集大小和性能需求选择算法。
来源
本教程解释了 C# 中的快速排序，其中包含升序和降序排序的示例，以及针对插入排序的基准。
作者
到目前为止，我已经撰写了超过 1400 篇文章和 8 本电子书。 我拥有八年以上的编程教学经验。
列出所有 C# 教程。