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