C#桶排序详解（从分桶到合并的完整实现指南）

桶排序的核心步骤

1. 确定桶的数量和范围：根据数据的最大值、最小值和期望的桶数量，计算每个桶能容纳的数据区间。
2. 分桶（Distribution）：遍历原始数组，将每个元素放入对应的桶中。
3. 桶内排序：对每个非空桶中的元素进行排序（常用插入排序）。
4. 合并（Concatenation）：按桶的顺序依次取出元素，合并成最终的有序数组。

C# 实现桶排序

下面是一个完整的 C# 桶排序实现，适用于 double 类型且值在 [0, 1) 区间内的数组：

using System;using System.Collections.Generic;using System.Linq;class BucketSortExample{    public static void BucketSort(double[] arr)    {        if (arr.Length <= 1) return;        int bucketCount = arr.Length;        List<List<double>> buckets = new List<List<double>>(bucketCount);        // 初始化桶        for (int i = 0; i < bucketCount; i++)        {            buckets.Add(new List<double>());        }        // 分桶：将元素分配到对应桶中        foreach (double value in arr)        {            int bucketIndex = (int)(value * bucketCount);            // 防止 value == 1.0 时越界            if (bucketIndex >= bucketCount) bucketIndex = bucketCount - 1;            buckets[bucketIndex].Add(value);        }        // 对每个桶进行排序（这里使用内置排序）        for (int i = 0; i < bucketCount; i++)        {            buckets[i].Sort();        }        // 合并：按顺序将桶中元素放回原数组        int index = 0;        foreach (var bucket in buckets)        {            foreach (double value in bucket)            {                arr[index++] = value;            }        }    }    // 测试示例    static void Main()    {        double[] data = { 0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51 };        Console.WriteLine("排序前: " + string.Join(", ", data));        BucketSort(data);        Console.WriteLine("排序后: " + string.Join(", ", data));    }}  

关键逻辑解析

1. 分桶逻辑

在上述代码中，分桶的关键在于这一行：

int bucketIndex = (int)(value * bucketCount);  

由于我们假设所有数值都在 [0, 1) 区间，乘以桶数量后取整，就能得到该值应归属的桶索引。例如，0.42 × 7 ≈ 2.94 → 索引为 2，放入第 3 个桶（从 0 开始计数）。

2. 合并逻辑

合并非常直观：从第 0 个桶开始，依次将每个桶中的已排序元素按顺序写回原数组。这一步保证了整体的有序性，因为桶本身是按数值区间顺序排列的。

适用场景与复杂度

• 时间复杂度：平均 O(n + k)，其中 n 是元素个数，k 是桶数量。最坏情况（所有元素落入一个桶）退化为 O(n²)。
• 空间复杂度：O(n + k)
• 适用条件：数据分布相对均匀，且知道数据的大致范围。

总结

通过本文，你已经掌握了 C#桶排序 的完整实现流程，尤其是 桶排序分桶逻辑 和 桶排序合并步骤 这两个核心环节。桶排序虽然不适用于所有场景，但在特定条件下（如均匀分布的小数）效率极高。

希望这篇教程能帮助你理解这一经典算法。动手试试吧！修改数据范围、尝试整数版本，甚至结合插入排序优化桶内排序，都是不错的练习方向。

关键词回顾：C#桶排序、桶排序分桶逻辑、C#排序算法、桶排序合并步骤