C# 桶排序
最后修改于 2025 年 3 月 9 日
本教程深入探讨 C# 中的桶排序算法。我们将探索如何对数字和文本进行升序和降序排序，并使用基准测试将其与快速排序进行比较。
算法是解决问题或完成任务的一组结构化步骤。它是编程和计算机科学的基石。
排序将数据组织成特定的序列，例如升序或降序。它对于程序中高效的数据处理和分析至关重要。
常用排序算法
以下是一些流行的排序算法
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 桶排序
桶排序算法
桶排序是一种基于分配的排序方法。它将元素划分为“桶”，分别对每个桶进行排序，然后将它们组合起来。
当数据均匀分布在一定范围内时，它会发光。与基于比较的排序不同，它依赖于分配数据，使其对于均匀分布的数据非常快，但在其他情况下效果较差。
桶排序示例：数值数据
这是使用顶级语句的 C# 中用于数字升序排序的桶排序的实现。
BucketSortNumeric.cs
// BucketSortNumeric.cs
double[] BucketSort(double[] arr)
{
if (arr.Length == 0) return arr;
double maxVal = arr.Max();
double bucketSize = maxVal / arr.Length;
List<double>[] buckets = new List<double>[arr.Length];
for (int i = 0; i < buckets.Length; i++)
buckets[i] = [];
foreach (double num in arr)
{
int idx = (int)(num / bucketSize);
if (idx >= arr.Length) idx = arr.Length - 1;
buckets[idx].Add(num);
}
foreach (var bucket in buckets)
bucket.Sort();
return buckets.SelectMany(bucket => bucket).ToArray();
}
double[] arr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51];
double[] sorted = BucketSort(arr);
Console.WriteLine("Sorted array: " + string.Join(" ", sorted));
这使用桶排序对双精度数组进行排序。它使用 List 对每个桶进行排序。
桶排序示例：文本数据
这是一个使用桶排序按长度降序对字符串进行排序的示例。
BucketSortTextual.cs
// BucketSortTextual.cs
string[] BucketSortTextual(string[] arr)
{
if (arr.Length == 0) return arr;
int maxLen = arr.Max(s => s.Length);
List<string>[] buckets = new List<string>[maxLen + 1];
for (int i = 0; i < buckets.Length; i++)
buckets[i] = [];
foreach (string s in arr)
buckets[s.Length].Add(s);
foreach (var bucket in buckets)
bucket.Sort((a, b) => b.CompareTo(a));
List<string> result = [];
for (int i = buckets.Length - 1; i >= 0; i--)
result.AddRange(buckets[i]);
return result.ToArray();
}
string[] arr = ["apple", "banana", "kiwi", "mango", "pear"];
string[] sorted = BucketSortTextual(arr);
Console.WriteLine("Sorted array: " + string.Join(" ", sorted));
这按长度降序对字符串进行排序，并在每个桶内使用自定义比较进行字母反向排序。
桶排序与快速排序的比较
桶排序在均匀分布的数据中表现出色，运行时间为 O(n + k)，其中 k 是桶的数量。快速排序的平均时间复杂度为 O(n log n)，对于一般情况来说更通用。
基准测试示例
这将比较桶排序和快速排序在大型数据集上的性能。
Benchmark.cs
// Benchmark.cs
using System.Diagnostics;
double[] BucketSort(double[] arr)
{
if (arr.Length == 0) return arr;
double maxVal = arr.Max();
double bucketSize = maxVal / arr.Length;
List<double>[] buckets = new List<double>[arr.Length];
for (int i = 0; i < buckets.Length; i++)
buckets[i] = [];
foreach (double num in arr)
{
int idx = (int)(num / bucketSize);
if (idx >= arr.Length) idx = arr.Length - 1;
buckets[idx].Add(num);
}
foreach (var bucket in buckets)
bucket.Sort();
return buckets.SelectMany(bucket => bucket).ToArray();
}
double[] QuickSort(double[] arr)
{
if (arr.Length <= 1) return arr;
double pivot = arr[arr.Length / 2];
var left = new List<double>();
var middle = new List<double>();
var right = new List<double>();
foreach (double 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());
double[] arr = new double[10000];
for (int i = 0; i < arr.Length; i++)
arr[i] = rand.NextDouble() * 1000;
double[] bucketData = arr.ToArray();
Stopwatch sw = Stopwatch.StartNew();
BucketSort(bucketData);
double bucketTime = sw.Elapsed.TotalSeconds;
double[] quickData = arr.ToArray();
sw = Stopwatch.StartNew();
QuickSort(quickData);
double quickTime = sw.Elapsed.TotalSeconds;
Console.WriteLine($"Bucket Sort Time: {bucketTime:F6} seconds");
Console.WriteLine($"Quick Sort Time: {quickTime:F6} seconds");
这在 10,000 个随机双精度数上对两种算法进行基准测试。桶排序可能在均匀数据上略胜一筹，但快速排序总体上更一致。
来源
我们已经介绍了 C# 中的桶排序，并将其与快速排序进行了比较。它非常适合均匀数据，而快速排序是一个强大的通用选择。
作者
列出所有 C# 教程。