【愚公系列】2021年11月 C#版 数据结构与算法解析(桶排序)

1、桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

1.1 算法描述

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

1.2 图片演示

1.3 代码实现

/// <summary>
/// 桶排序
/// </summary>
public class Program {

    public static void Main(string[] args) {
        double[] array = { 0.43, 0.69, 0.11, 0.72, 0.28, 0.21, 0.56, 0.80, 0.48, 0.94, 0.32, 0.08 };

        BucketSort(array, 10);
        ShowSord(array);

        Console.ReadKey();
    }

    private static void ShowSord(double[] array) {
        foreach (var num in array) {
            Console.Write($"{num} ");
        }
        Console.WriteLine();
    }

    public static void BucketSort(double[] array, int bucketNum) {
        //创建bucket时，在二维中增加一组标识位，其中bucket[x, 0]表示这一维所包含的数字的个数
        //通过这样的技巧可以少写很多代码
        double[,] bucket = new double[bucketNum, array.Length + 1];
        foreach (var num in array) {
            int bit = (int)(10 * num);
            bucket[bit, (int)++bucket[bit, 0]] = num;
        }
        //为桶里的每一行使用插入排序
        for (int j = 0; j < bucketNum; j++) {
            //为桶里的行创建新的数组后使用插入排序
            double[] insertion = new double[(int)bucket[j, 0]];
            for (int k = 0; k < insertion.Length; k++) {
                insertion[k] = bucket[j, k + 1];
            }
            //插入排序
            StraightInsertionSort(insertion);
            //把排好序的结果回写到桶里
            for (int k = 0; k < insertion.Length; k++) {
                bucket[j, k + 1] = insertion[k];
            }
        }
        //将所有桶里的数据回写到原数组中
        for (int count = 0, j = 0; j < bucketNum; j++) {
            for (int k = 1; k <= bucket[j, 0]; k++) {
                array[count++] = bucket[j, k];
            }
        }
    }

    public static void StraightInsertionSort(double[] array) {
        //插入排序
        for (int i = 1; i < array.Length; i++) {
            double sentinel = array[i];
            int j = i - 1;
            while (j >= 0 && sentinel < array[j]) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = sentinel;
        }
    }

}

1.4 算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。