C# 计数排序算法
最后修改于 2025 年 3 月 9 日
本教程介绍了 C# 中的计数排序算法。我们将定义它，展示排序数字和文本的示例，并将其与快速排序进行比较。
算法 是解决问题或执行任务的清晰、逐步的方法。它是程序处理和管理数据的基础。
排序 以特定顺序（例如升序或降序）排列数据。它在计算中对于组织和检索数据至关重要。
常用排序算法
以下是一些著名的排序算法
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 计数排序
计数排序算法
计数排序是一种非基于比较的排序方法。它计算每个元素在输入中出现的次数，然后使用此计数将元素放置在正确的排序位置。
对于小范围的整数，它速度很快，但需要额外的内存来存储计数数组。与基于比较的排序不同，它不会直接比较元素。
计数排序示例
这是一个使用顶级语句的 C# 整数计数排序实现。
CountingSort.cs
// CountingSort.cs
int[] CountingSort(int[] arr)
{
if (arr.Length == 0)
{
return arr;
}
int maxVal = arr.Max();
int[] count = new int[maxVal + 1];
foreach (int num in arr)
{
count[num]++;
}
List<int> sorted = [];
for (int i = 0; i < count.Length; i++)
{
while (count[i] > 0)
{
sorted.Add(i);
count[i]--;
}
}
return sorted.ToArray();
}
int[] arr = [4, 2, 2, 8, 3, 3, 1];
int[] sorted = CountingSort(arr);
Console.WriteLine("Sorted array: " + string.Join(" ", sorted));
此代码使用计数排序按升序对整数数组进行排序。
对文本数据进行排序
计数排序还可以对文本进行排序，例如字符串的字符。这是一个例子
CountingSortText.cs
// CountingSortText.cs
string CountingSortText(string text)
{
if (string.IsNullOrEmpty(text))
{
return text;
}
int maxVal = text.Max();
int[] count = new int[maxVal + 1];
foreach (char c in text)
{
count[c]++;
}
char[] sorted = new char[text.Length];
int index = 0;
for (int i = 0; i < count.Length; i++)
{
while (count[i] > 0)
{
sorted[index] = (char)i;
index++;
count[i]--;
}
}
return new string(sorted);
}
string text = "counting";
string sorted = CountingSortText(text);
Console.WriteLine("Sorted text: " + sorted);
这使用计数排序按升序对字符串的字符进行排序。
降序排序
要按降序排序，我们反转计数排序中的输出循环。
CountingSortDesc.cs
// CountingSortDesc.cs
int[] CountingSortDesc(int[] arr)
{
if (arr.Length == 0)
{
return arr;
}
int maxVal = arr.Max();
int[] count = new int[maxVal + 1];
foreach (int num in arr)
{
count[num]++;
}
List<int> sorted = [];
for (int i = count.Length - 1; i >= 0; i--)
{
while (count[i] > 0)
{
sorted.Add(i);
count[i]--;
}
}
return sorted.ToArray();
}
int[] arr = [4, 2, 2, 8, 3, 3, 1];
int[] sorted = CountingSortDesc(arr);
Console.WriteLine("Sorted array (descending): " + string.Join(" ", sorted));
这按降序对整数数组进行排序。
与快速排序的比较
计数排序在小整数范围内表现出色，以 O(n + k) 的时间运行，其中 k 是值的范围。快速排序是一种基于比较的方法，平均为 O(n log n)，并且可以更好地处理更大的数据集。
基准测试示例
此示例比较了计数排序和快速排序的性能。
Benchmark.cs
// Benchmark.cs
using System.Diagnostics;
int[] CountingSort(int[] arr)
{
if (arr.Length == 0)
{
return arr;
}
int maxVal = arr.Max();
int[] count = new int[maxVal + 1];
foreach (int num in arr)
{
count[num]++;
}
List<int> sorted = [];
for (int i = 0; i < count.Length; i++)
{
while (count[i] > 0)
{
sorted.Add(i);
count[i]--;
}
}
return sorted.ToArray();
}
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())];
}
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[] countingData = data.ToArray();
Stopwatch sw = Stopwatch.StartNew();
CountingSort(countingData);
double countingTime = sw.Elapsed.TotalSeconds;
int[] quickData = data.ToArray();
sw = Stopwatch.StartNew();
QuickSort(quickData);
double quickTime = sw.Elapsed.TotalSeconds;
Console.WriteLine($"Counting sort time: {countingTime:F6} seconds");
Console.WriteLine($"Quick sort time: {quickTime:F6} seconds");
这在 10,000 个随机整数上对两种算法进行基准测试。计数排序可能在小范围内获胜，但快速排序的扩展性更好。
来源
我们已经探讨了 C# 中的计数排序，并将其与快速排序进行了比较。
作者
列出所有 C# 教程。