严肃一点的排序算法（4） – 桶排序

其实这是一个很严肃的排序算法，在实际的编程当中，很有可能会用到。

这个算法就好比有11个桶，编号从0~10。每出现一个数，就将对应编号的桶中的放一个小旗子，最后只要数数每个桶中有几个小旗子就OK了。例如2号桶中有1个小旗子，表示2出现了一次；3号桶中有1个小旗子，表示3出现了一次；5号桶中有2个小旗子，表示5出现了两次；8号桶中有1个小旗子，表示8出现了一次。

现在你可以请尝试一下输入n个0~1000之间的整数，将他们从大到小排序。提醒一下如果需要对数据范围在0~1000之间的整数进行排序，我们需要1001个桶，来表示0~1000之间每一个数出现的次数，这一点一定要注意。另外此处的每一个桶a[i]的作用其实就是“标记”每个数出现的次数，因此我喜欢将之前的数组a换个更贴切的名字book（book这个单词有记录、标记的意思）。

最后来说下时间复杂度的问题。代码中第6行的循环一共循环了m次（m为桶的个数），第9行的代码循环了n次（n为待排序数的个数），第14和15行一共循环了m+n次。所以整个排序算法一共执行了m+n+m+n次。我们用大写字母O来表示时间复杂度，因此该算法的时间复杂度是O(m+n+m+n)即O(2*(m+n))。我们在说时间复杂度时候可以忽略较小的常数，最终桶排序的时间复杂度为O(m+n)。还有一点，在表示时间复杂度的时候，n和m通常用大写字母即O(M+N)。

最后通过代码来实践一下。

static void Main(string[] args)
{
    int[] nums = new[] { 1, 4, 7, 20, 14, 30, 124, 45 };
    List<int> bucket = new List<int>(); //很多很多的桶

    //初始化桶
    int max = GetMaxValue(nums);
    for (int i = 0; i < max + 1; i++)
    {
        bucket.Add(0);
    }
    //往桶里面倒水
    for (int i = 0; i < nums.Length; i++)
    {
        bucket[nums[i]]++;
    }
    //把桶搬出来
    for (int i = 0; i < bucket.Count; i++)
    {
        if (bucket[i] != 0)
        {
            for (int j = 0; j < bucket[i]; j++)
            {
                Console.Write(i + ",");
            }
        }
    }
    Console.WriteLine("rn");
    Console.ReadKey(false);
}

static int GetMaxValue(int[] nums)
{
    int max = nums[0];
    for (int i = 0; i < nums.Length; i++)
    {
        if (max < nums[i])
        {
            max = nums[i];
        }
    }
    return max;
}

其实简单来说，桶排序就是使用空间换取时间的一种排序算法。

摘抄来源：https://blog.csdn.net/YinhJiang/article/details/80397415