分配排序

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

箱排序(Bin Sort)

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)┘来实现。

3、桶排序示例
　    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)中即可。

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

 

基数排序

     　基数排序(Radix Sort)是对箱排序的改进和推广。

1、单关键字和多关键字
     　文件中任一记录R[i]的关键字均由d个分量
                      构成。
若这d个分量中每个分量都是一个独立的关键字，则文件是多关键字的(如扑克牌有两个关键字：点数和花色)；否则文件是单关键字的，
                (0≤j<d)只不过是关键字中其中的一位(如字符串、十进制整数等)。
     多关键字中的每个关键字的取值范围一般不同。如扑克牌的花色取值只有4种，而点数则有13种。单关键字中的每位一般取值范围相同。

2、基数
     　　设单关键字的每个分量的取值范围均是：
       C₀≤k_j≤C_rd-1(0≤j<d)
可能的取值个数rd称为基数。
     　基数的选择和关键字的分解因关键宇的类型而异:
(1) 若关键字是十进制整数，则按个、十等位进行分解，基数rd=10，C₀=0，C₉=9，d为最长整数的位数；
(2) 若关键字是小写的英文字符串，则rd=26，C_o='a'，C₂₅='z'，d为字符串的最大长度。

3、基数排序的基本思想
     　基数排序的基本思想是：从低位到高位依次对K^j(j=d-1，d-2，…，0)进行箱排序。在d趟箱排序中，所需的箱子数就是基数rd，这就是"基数排序"名称的由来。

4、基数排序的排序过程
     　要排序的记录关键字取值范围是0到99之间的整数(36，5，16，98，95，47， 32，36，48)。对这些关键字进行基数排序的过程【参见动画演示】。

5、基数排序的类型说明和算法描述
     　要保证基数排序是正确的，就必须保证除第一趟外各趟箱排序是稳定的。相应的类型说明及算法描述【参见教材】。

6、算法分析
     　若排序文件不是以数组R形式给出，而是以单链表形式给出(此时称为链式的基数排序)，则可通过修改出队和人队函数使表示箱子的链队列无须分配结点空间，而使用原链表的结点空间。人队出队操作亦无需移动记录而仅需修改指针。虽然这样一来节省了一定的时间和空间，但算法要复杂得多，且时空复杂度就其数量级而言并未得到改观。 有关链式的基数排序可【阅读参考书目[12]】。
     　基数排序的时间是线性的(即O(n))。
     　基数排序所需的辅助存储空间为O(n+rd)。
     　基数排序是稳定的。
按平均时间将排序分为四类：

（1）平方阶(O(n²))排序
     　一般称为简单排序，例如直接插入、直接选择和冒泡排序；

（2）线性对数阶(O(nlgn))排序
     　如快速、堆和归并排序；

（3）O(n^1+￡)阶排序
     　￡是介于0和1之间的常数，即0<￡<1，如希尔排序；

（4）线性阶(O(n))排序
     　如桶、箱和基数排序。

各种排序方法比较

      简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。

影响排序效果的因素

     　因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：
　　①待排序的记录数目n；
　　②记录的大小(规模)；
　　③关键字的结构及其初始状态；
　　④对稳定性的要求；
　　⑤语言工具的条件；
　　⑥存储结构；
　　⑦时间和辅助空间复杂度等。

不同条件下，排序方法的选择

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
     　当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
     　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
     　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
     　若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的   排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

(4)在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。
     　当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlgn)的时间。
     　箱排序和基数排序只需一步就会引起m种可能的转移，即把一个记录装入m个箱子之一，因此在一般情况下，箱排序和基数排序可能在O(n)时间内完成对n个记录的排序。但是，箱排序和基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合(例如实数型关键字)时，无法使用箱排序和基数排序，这时只有借助于"比较"的方法来排序。
     　若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。虽然桶排序对关键字的结构无要求，但它也只有在关键字是随机分布时才能使平均时间达到线性阶，否则为平方阶。同时要注意，箱、桶、基数这三种分配排序均假定了关键字若为数字时，则其值均是非负的，否则将其映射到箱(桶)号时，又要增加相应的时间。
(5)有的语言(如Fortran，Cobol或Basic等)没有提供指针及递归，导致实现归并、快速(它们用递归实现较简单)和基数(使用了指针)等排序算法变得复杂。此时可考虑用其它排序。
(6)本章给出的排序算法，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大量的时间去移动记录，可以用链表作为存储结构。譬如插入排序、归并排序、基数排序都易于在链表上实现，使之减少记录的移动次数。但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下，可以提取关键字建立索引表，然后对索引表进行排序。然而更为简单的方法是：引人一个整型向量t作为辅助表，排序前令t[i]=i(0≤i<n)，若排序算法中要求交换R[i]和R[j]，则只需交换t[i]和t[j]即可；排序结束后，向量t就指示了记录之间的顺序关系：
         R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
   若要求最终结果是：
        R[0].key≤R[1].key≤…≤R[n-1].key
则可以在排序结束后，再按辅助表所规定的次序重排各记录，完成这种重排的时间是O(n)。