分配排序的基本思想：排序过程无须比较关键字，而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶：O(n)。
本节介绍第一种分配排序方法：箱排序。
1、箱排序的基本思想
箱排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录 R[0]，R[1]，…，R[n-1]，把关键字等于 k 的记录全都装入到第 k 个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。
【例】要将一副混洗的 52 张扑克牌按点数 A<2<…<J<Q<K 排序，需设置 13 个"箱子"，排序时依次将每张牌按点数放入相应的箱子里，然后依次将这些箱子首尾相接，就得到了按点数递增序排列的一副牌。
2、箱排序中，箱子的个数取决于关键字的取值范围。
若 R[0..n-1]中关键字的取值范围是0到m-1的整数，则必须设置 m 个箱子。因此箱排序要求关键字的类型是有限类型，否则可能要无限个箱子。
3、箱子的类型应设计成链表为宜
一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的，故箱子的类型应设计成链表为宜。
4、为保证排序是稳定的，分配过程中装箱及收集过程中的连接必须按先进先出原则进行。
（1）实现方法一
每个箱子设为一个链队列。当一记录装入某箱子时，应做人队操作将其插入该箱子尾部；而收集过程则是对箱子做出队操作，依次将出队的记录放到输出序列中。
（2）实现方法二
若输入的待排序记录是以链表形式给出时，出队操作可简化为是将整个箱子链表链接到输出链表的尾部。这只需要修改输出链表的尾结点中的指针域，令其指向箱子链表的头，然后修改输出链表的尾指针，令其指向箱子链表的尾即可。
5、算法简析
分配过程的时间是 O(n)；收集过程的时间为 O(m) （采用链表来存储输入的待排序记录）或 O(m+n)。因此，箱排序的时间为 O(m+n)。若箱子个数m的数量级为 O(n)，则箱排序的时间是线性的，即 O(n)。
注意： 箱排序实用价值不大，仅适用于作为基数排序(下节介绍)的一个中间步骤。
箱排序的变种。为了区别于上述的箱排序，姑且称它为桶排序(实际上箱排序和桶排序是同义词)。
1、桶排序基本思想
桶排序的思想是把[0，1)划分为n个大小相同的子区间，每一子区间是一个桶。然后将n个记录分配到各个桶中。因为关键字序列是均匀分布在[0，1)上的，所以一般不会有很多个记录落入同一个桶中。由于同一桶中的记录其关键字不尽相同，所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排序，然后依次将各非空桶中的记录连接(收集)起来即可。
注意： 这种排序思想基于以下假设：假设输入的 n 个关键字序列是随机分布在区间[0，1)之上。若关键字序列的取值范围不是该区间，只要其取值均非负，我们总能将所有关键字除以某一合适的数，将关键字映射到该区间上。但要保证映射后的关键字是均匀分布在[0，1)上的。
2、桶排序算法
伪代码算法为：
void BucketSon(R)
{ //对R[0..n-1]做桶排序，其中0≤R[i].key<1(0≤i<n)
for(i=0，i<n;i++) //分配过程．
将R[i]插入到桶B[「n(R[i].key)」]中； //可插入表头上
for(i=0;i<n;i++) //排序过程
当B[i]非空时用插人排序将B[i]中的记录排序；
for(i=0，i<n；i++) //收集过程
若B[i]非空，则将B[i]中的记录依次输出到R中；
}
注意： 实现时需设置一个指针向量 B[0..n-1]来表示 n 个桶。但因为任一记录 R[i]的关键字满足：0≤R[i].key<1(0≤i≤n-1)，所以必须将 R[i].key映射到 B 的下标区间[0，n-1)上才能使 R[i]装入某个桶中，这可通过
└n*(R[i].key)┘来实现。
R[0..9]中的关键字为 (0.78，0.17，0.39，0.26，0.72，0.94，0.21， 0.12，0.23，0.68)，用算法BucketSort排序的过程。
分析： 这里 n=10，故 B[0..9]这 10 个桶表示的子区间分别是[0，0.1)，[0.1，0.2)，…，[0.9，1)。 收集过程只要按 B[0]，B[1]，…，B[9]的次序将各非空桶首尾链接起来，或将其输出到 R[0..9)中即可。
桶排序的平均时间复杂度是线性的，即 O(n)。但最坏情况仍有可能是 O(n2)。
箱排序只适用于关键字取值范围较小的情况，否则所需箱子的数目 m 太多导致浪费存储空间和计算时间。
【例】n=10，被排序的记录关键字 ki 取值范围是 0 到 99 之间的整数(36，5，16，98，95，47, 32，36，48)时，要用 100 个箱子来做一趟箱排序。（即若 m=n2 时，箱排序的时间 O(m+n)=O(n2)）。
