桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

1. 求出待排序列表中的最大值和最小值，得到数据的范围。

2. 根据数据的范围，选择一个适合的值构建有限数量的桶，确定每个桶的数据范围。如数据范围是[0,100)，将数据分成10个桶，第一个桶为[0,10)，第二个桶为[10,20)，以此类推。

3. 将待排序列表中的数据分配到对应的桶中。

4. 对每一个桶内的数据进行排序，这里可以采用任意一种排序算法，建议采用时间复杂度小的排序算法。

5. 将所有桶中的数据依次取出，添加到一个新的有序序列中，列表排序完成。

        桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

        当输入的数据可以均匀的分配到每一个桶中。

        当输入的数据被分配到了同一个桶中。

桶排序动态图演示：

 排序过程如下：

        以 [11,9,2,8,12,1,6,7,4,3,10,5] 为例，代码如下：

运行结果：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

        在桶排序中，需要走访待排序列表中的每一个元素，进行分桶，列表长度为 n ，然后需要对每一个桶进行桶内排序，单个桶内排序的最坏时间复杂度是 O(ni^2)，ni 表示第 i 个桶内有 ni 个数据，一共有 k 个桶，时间复杂度为n加每一个桶内排序的时间复杂度，最坏情况下所有数据全被分到了一个桶内，ni=n，时间复杂度为T(n)=n+n^2，再乘分桶和排序的步骤数(常数，不影响大O记法)，所以桶排序的时间复杂度为 O(n^2) 。

        桶排序的最优情况是将数据均匀地分配到每一个桶中，此时有k个桶，每个桶内有n/k个数据，每个桶内排序的平均时间复杂度为O(n/k*logn/k)，整个桶排序的时间复杂度为T(n)=n+k*n/k*logn/k，而当k=n时，即每个桶内只有一个元素(不需要进行桶内排序)，时间复杂度为O(n)。

        根据桶排序的排序原理，会将待排序列表进行分桶、桶内排序和合并。在对每一个桶进行桶内排序时，可以采用不同的排序算法，有些排序算法是稳定的，有些排序算法是不稳定，这会影响到桶排序的稳定性。所以桶排序的稳定性取决于桶内排序算法的稳定性。