思想
桶排序是计数排序的推广。对于计数排序，每个整数值对应一个桶，而对于桶排序，一定范围内的数据对应着一个桶，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序（一般是快排），最后将非空桶中的元素逐个放入原序列中。
桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。
桶的个数一般有如下的计算公式：
其中$N$为元素的个数，
桶排序的稳定性取决于桶内排序使用的算法。
应用
对于海量数据，一般会利用桶排序的算法来降低比较次数。
比如一年的全国高考考生人数为500 万，分数使用标准分，最低100 ，最高900 ，没有小数，要求对这500 万元素的数组进行排序。
对500W数据排序，如果基于比较的先进排序，平均比较次数为O(5000000*log5000000)≈1.112亿。但是我们发现，这些数据都有特殊的条件： $100=<score<=900$。那么我们就可以考虑桶排序这样一个投机取巧的办法、让其在毫秒级别就完成500万排序。
创建801(900-100)个桶。将每个考生的分数丢进f(score)=score-100的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出，即可以得到一个有序的序列。而且可以很容易的得到100分有多少人，501分有多少人。
实际上，桶排序对数据的条件有特殊要求，如果上面的分数不是从100-900，而是从0-2亿，那么分配2亿个桶显然是不可能的。所以桶排序有其局限性，适合元素值集合并不大的情况。