算法、排序（10）

    　分配排序的基本思想&＃xff1a;排序过程无须比较关键字&＃xff0c;而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶&＃xff1a;O(n)。

箱排序(Bin Sort)

1、箱排序的基本思想
    　箱排序也称桶排序(Bucket Sort)&＃xff0c;其基本思想是&＃xff1a;设置若干个箱子&＃xff0c;依次扫描待排序的记录R[0]&＃xff0c;R[1]&＃xff0c;…&＃xff0c;R[n-1]&＃xff0c;把关键字等于k的记录全都装入到第k个箱子里 (分配)&＃xff0c;然后按序号依次将各非空的箱子首尾连接起来(收集)。
【例】要将一副混洗的52张扑克牌按点数A<2<…
2、箱排序中&＃xff0c;箱子的个数取决于关键字的取值范围。
    　若R[0..n-1]中关键字的取值范围是0到m-1的整数&＃xff0c;则必须设置m个箱子。因此箱排序要求关键字的类型是有限类型&＃xff0c;否则可能要无限个箱子。

3、箱子的类型应设计成链表为宜
   　 一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的&＃xff0c;故箱子的类型应设计成链表为宜。

4、为保证排序是稳定的&＃xff0c;分配过程中装箱及收集过程中的连接必须按先进先出原则进行。
&＃xff08;1&＃xff09; 实现方法一
    　每个箱子设为一个链队列。当一记录装入某箱子时&＃xff0c;应做人队操作将其插入该箱子尾部&＃xff1b;而收集过程则是对箱子做出队操作&＃xff0c;依次将出队的记录放到输出序列中。

&＃xff08;2&＃xff09; 实现方法二
    　若输入的待排序记录是以链表形式给出时&＃xff0c;出队操作可简化为是将整个箱子链表链接到输出链表的尾部。这只需要修改输出链表的尾结点中的指针域&＃xff0c;令其指向箱子链表的头&＃xff0c;然后修改输出链表的尾指针&＃xff0c;令其指向箱子链表的尾即可。

5、算法简析
    　分配过程的时间是O(n)&＃xff1b;收集过程的时间为O(m) &＃xff08;采用链表来存储输入的待排序记录&＃xff09;或O(m&＃43;n)。因此&＃xff0c;箱排序的时间为O(m&＃43;n)。若箱子个数m的数量级为O(n)&＃xff0c;则箱排序的时间是线性的&＃xff0c;即O(n)。
  注意&＃xff1a;
    　箱排序实用价值不大&＃xff0c;仅适用于作为基数排序(下节介绍)的一个中间步骤。

桶排序

    　箱排序的变种。为了区别于上述的箱排序&＃xff0c;姑且称它为桶排序(实际上箱排序和桶排序是同义词)。

1、桶排序基本思想
    　桶排序的思想是把[0&＃xff0c;1)划分为n个大小相同的子区间&＃xff0c;每一子区间是一个桶。然后将n个记录分配到各个桶中。因为关键字序列是均匀分布在[0&＃xff0c;1)上 的&＃xff0c;所以一般不会有很多个记录落入同一个桶中。由于同一桶中的记录其关键字不尽相同&＃xff0c;所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排 序&＃xff0c;然后依次将各非空桶中的记录连接(收集)起来即可。
  注意&＃xff1a;
    　这种排序思想基于以下假设&＃xff1a;假设输入的n个关键字序列是随机分布在区间[0&＃xff0c;1)之上。若关键字序列的取值范围不是该区间&＃xff0c;只要其取值均非负&＃xff0c;我们总能 将所有关键字除以某一合适的数&＃xff0c;将关键字映射到该区间上。但要保证映射后的关键字是均匀分布在[0&＃xff0c;1)上的。

2、桶排序算法
  伪代码算法为&＃xff1a;
  void BucketSon(R)
    { //对R[0..n-1]做桶排序&＃xff0c;其中0≤R[i].key<1(0≤i       for(i&＃61;0&＃xff0c;i         将R[i]插入到桶B[「n(R[i].key)」]中&＃xff1b; //可插入表头上
      for(i&＃61;0;i         当B[i]非空时用插人排序将B[i]中的记录排序&＃xff1b;
      for(i&＃61;0&＃xff0c;i         若B[i]非空&＃xff0c;则将B[i]中的记录依次输出到R中&＃xff1b;
     }

  注意&＃xff1a;
    　实现时需设置一个指针向量B[0..n-1]来表示n个桶。但因为任一记录R[i]的关键字满足&＃xff1a;0≤R[i].key<1(0≤i≤n-1)&＃xff0c; 所以必须将R[i].key映射到B的下标区间[0&＃xff0c;n-1)上才能使R[i]装入某个桶中&＃xff0c;这可通过└n*(R[i].key)┘来实现。

3、桶排序示例
　    R[0..9]中的关键字为 (0.78&＃xff0c;0.17&＃xff0c;0.39&＃xff0c;0.26&＃xff0c;0.72&＃xff0c;0.94&＃xff0c;0.21&＃xff0c; 0.12&＃xff0c;0.23&＃xff0c;0.68)&＃xff0c;用算法BucketSort排序的过程【参见动画演示】。
分析&＃xff1a;
    　这里n&＃61;10&＃xff0c;故B[0..9]这10个桶表示的子区间分别是[0&＃xff0c;0.1)&＃xff0c;[0.1&＃xff0c;0.2)&＃xff0c;…&＃xff0c;[0.9&＃xff0c;1)。
    　收集过程只要按B[0]&＃xff0c;B[1]&＃xff0c;…&＃xff0c;B[9]的次序将各非空桶首尾链接起来&＃xff0c;或将其输出到R[0..9)中即可。

4、桶排序算法分析
    　桶排序的平均时间复杂度是线性的&＃xff0c;即O(n)。但最坏情况仍有可能是O(n²)。
    　箱排序只适用于关键字取值范围较小的情况&＃xff0c;否则所需箱子的数目m太多导致浪费存储空间和计算时间。
　　【例】n&＃61;10&＃xff0c;被排序的记录关键字k_i取值范围是0到99之间的整数(36&＃xff0c;5&＃xff0c;16&＃xff0c;98&＃xff0c;95&＃xff0c;47, 32&＃xff0c;36&＃xff0c;48)时&＃xff0c;要用100个箱子来做一趟箱排序。&＃xff08;即若m&＃61;n²时&＃xff0c;箱排序的时间O(m&＃43;n)&＃61;O(n²)&＃xff09;。