7.箱子排序

说明一点，箱排序实用价值不大，在此仅适用于作为基数排序的一个中间步骤，所以有必要介绍一下。

我们先来看一个场景需求：

数据库中存储了学生的姓名年龄和成绩，要求将学生按照成绩排序。如果是前面的几种简单排序，所需要花费的时间均为N方，所以介绍一种更快的排序算法：箱子排序。

简单点说，箱子排序就是把待排序元素分成几类，然后设置若干个箱子，依次扫描待排序的记录，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。

对于实现箱子排序，需要能够：

1.从欲排序链表的首部开始，逐个删除每个节点，并把删除的节点放入合适的箱子中。

2.收集并链接每个箱子里的节点，产生一个排序的链表。

如果输入的链表是Chain类型，那么可以：

1.连续的删除链表的首元素，并将其插入到相应箱子链表首部。

2.逐个删除每个箱子中的元素（从最后一个箱子开始）并将其插入到一个初始为空的链表首部。

下面来总结一下箱子排序：

原理：将元素分装到各个有序的箱子中，并且将箱子按照顺序生成新的序列。

要点：先分类，再排序


8.基数排序：

基数排序可以说是对上面箱子排序的扩充。箱子排序存在一个非常大的问题：如果箱子跨度range为次方级，那么箱子排序的箱子数目将会非常多。为了解决这个弊端，我们将箱子排序进行扩充。

基数排序的原理是不直接对元素进行排序，而是先将其分解，然后对每一部分进行排序。

比如对十进制三位数排序。123拆解为1，2，3；456拆解为4，5，6。先比较个位数，排好序后再比较十位数，最后再比较百位数排序，这样便可以得到最后的排序结果。

简而言之就是每次按照每个数字的一位进行排序，先按照最个位，再按照十位，依次类推至最高位。其中每一位的排序必须是稳定排序才能保证算法的正确性。

基数排序的源码：

 

[cpp]  view plain copy
  1. #include     
  2. using namespace std;  
  3.   
  4. template <</span>class T>     
  5. void show(T arr,int n){    
  6.     for(int i =0;i
  7.         cout<<arr[i]<<",";    
  8.     }    
  9.     cout<<arr[n-1]<<endl;    
  10. }    
  11.   
  12.   
  13. int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen){      
  14.     //这里就不用说了，计数的排序。不过这里为了是排序稳定       
  15.     //在标准的方法上做了小修改。       
  16.     int* pnCount  = (int*)malloc(sizeof(int)* nMax);            //保存计数的个数       
  17.     int i = 0;      
  18.     for (i = 0; i < nMax; ++i){      
  19.         pnCount[i] = 0;      
  20.     }      
  21.     for (i = 0; i < nLen; ++i){                                  //初始化计数个数       
  22.         ++pnCount[npIndex[i]];      
  23.     }      
  24.       
  25.     for (i = 1; i < 10; ++i){                                    //确定不大于该位置的个数。       
  26.         pnCount[i] += pnCount[i - 1];      
  27.     }      
  28.       
  29.     int * pnSort  = (int*)malloc(sizeof(int) * nLen);           //存放零时的排序结果。       
  30.     //注意：这里i是从nLen-1到0的顺序排序的，是为了使排序稳定。       
  31.     for (i = nLen - 1; i >= 0; --i){      
  32.         --pnCount[npIndex[i]];              
  33.         pnSort[pnCount[npIndex[i]]] = npData[i];      
  34.     }    
  35.     for (i = 0; i < nLen; ++i){                                  //把排序结构输入到返回的数据中。         
  36.         npData[i] = pnSort[i];      
  37.     }      
  38.     free(pnSort);                                               //记得释放资源。       
  39.     free(pnCount);      
  40.     return 1;      
  41. }      
  42.   
  43. //基数排序       
  44. int RadixSort(int* nPData, int nLen){      
  45.     //申请存放基数的空间       
  46.     int* nDataRadix=(int*)malloc(sizeof(int) * nLen);     
  47.     int nRadixBase = 1;                                         //初始化倍数基数为1       
  48.     int nIsOk = 0;                                              //设置完成排序为0       
  49.       
  50.     //循环，知道排序完成       
  51.     while (!nIsOk){      
  52.         nIsOk = 1;      
  53.         nRadixBase *= 10;      
  54.         int i = 0;       
  55.         for (i = 0; i < nLen; ++i){      
  56.             nDataRadix[i] = nPData[i] % nRadixBase;      
  57.             nDataRadix[i] /= nRadixBase / 10;      
  58.             if (nDataRadix[i] > 0){      
  59.                 nIsOk = 0;      
  60.             }      
  61.                     show(nPData,nLen);  
  62.         }      
  63.         if (nIsOk){                                             //如果所有的基数都为0，认为排序完成，就是已经判断到最高位了。       
  64.             break;      
  65.         }      
  66.         RadixCountSort(nDataRadix, 10, nPData, nLen);     
  67.   
  68.     }      
  69.     free(nDataRadix);    
  70.     return 1;    
  71. }    
  72.   
  73.   
  74. void main()    
  75. {    
  76.     int inputNumber[]={212,127,425,159,681,914,326,153,558};    
  77.     int count = 9;   
  78.     cout<<"原始数组："<<endl;  
  79.     show(inputNumber,count);  
  80.     cout<<"排序过程："<<endl;  
  81.     RadixSort(inputNumber,count);   
  82.     cout<<"排序结果："<<endl;  
  83.     show(inputNumber,count);    
  84. }    

基数排序的过程：

 


下面来分析一下基数排序的复杂度：

时间效率：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))。

其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。


接下来是稳定性的讨论：

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。


基数排序的总结：

原理：将数字按位数划分出n个关键字，每次针对一个关键字进行排序，然后针对排序后的序列进行下一个关键字的排序，循环至所有关键字都使用过则排序完成。

要点：对关键字的选取，元素分配收集。


下面对前面讨论过的和未讨论的各种排序算法进行一下总结（注释：以下表格引用自明哥的博客）：

 

     名称

时间复杂度

原理

稳定性

举例(3,1,4,5,2)

名次排序

O(n2)

     先排出名次,再根据名次,将数据放入相应的

     数组排序

稳定

名次是(3,1,4,5,2)

排序是(1,2,3,4,5)

冒泡排序

O(n2)

     一次冒泡是从前面开始两两比较,如果前面

     大后面数小就互换,共冒n次泡

稳定

一次冒泡:1,3,4,2,5

二次冒泡:1,3,2,4,5

三次冒泡:1,2,3,4,5

四次冒泡:1,2,3,4,5

五次冒泡:1,2,3,4,5

插入排序

O(n2)

     第一个数据不动,将第二个与之比较,并插

     入,第三个与前两个比较并插入....直到n个

稳定

插入第二个:1,3,4,5,2

插入第三个:1,3,4,5,2

插入第四个:1,3,4,5,2

插入第五个:1,2,3,4,5

选择排序

O(n2)

     n个数中选择最大的放在最后,再在前n-1个

     选择最大的放在倒数第二个...直到第一个.

稳定

第一次:3,1,4,2,5

第二次:3,1,2,4,5

第三次:1,2,3,4,5

第四次:1,2,3,4,5

基数排序

O(n)

     按照基数r分为r个盒子,将符合条件的数据

     放入相应链表盒子里,直到排序完成

稳定

一次:1,2,3,4,5

堆排序

O(nlogn)

     利用最大堆排序,将数据初始化为最大堆,

     依次删除最大元素,直到删完,排序完成

不稳定

删除5,4,3,2,1

依次放入12345

拓扑排序

O(n2)

     在由任务建立的有向图中，边(i,j)表示在装配序列

    中任务i 在任务j  的前面，具有这种性质的序列称

    为拓扑序列根据任务的有向图建立拓扑序列的过程

稳定

无

快速排序

平均O(nlog2n) 

最坏O(n2)

     不断寻找一个序列的中点，然后对中点左右

     的序列递归的进行排序，直至全部序列排序

     完成，使用了分治的思想

稳定

第一次;1,3,4,5,2

第二次:1,3,4,2,5

第三次:1,2,3,4,5

归并排序

平均O(nlog2n)

最坏O(nlog2n)

     将原序列划分为有序的两个序列，然后利用

     归并算法进行合并，合并之后即为有序序列。

稳定

3,1  4,5,2

1,3  2,4,5

1, 2, 3 ,4, 5