桶排序

举个栗子，我们的任务是将 40 个 100 以内的数字排序。我们可以这么做：

将0~~20以内的数字放入第一个桶内

将21~~40以内的数字放入第二个桶内

依次反复直到将这40个数字放入 5 个桶内

利用某种排序方法(本文用的快速排序)将桶内元素排序

从桶内按照顺序将数字取出依次放入一个原数组

桶排序 (Bucket sort)或所谓的箱排序

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