分配排序 桶排序与基数排序

基本演化顺序是：分配排序——桶排序——基数排序

分配排序是最基本的为所有可能都分配一个存储位置的方法

桶排序是在分配排序的基础上为相同元素或在同一个范围内的元素分配同一个桶，因此每个桶可以看做一个变长的链表

基数排序是将元素分等级从最次级到最高级不断进行递进的排序过程

 

 

桶排序（在这里与分配排序一致：因为不存在重复元素且不划分范围）

这是迄今为止最快的一种排序法，其时间复杂度仅为Ο(n)，也就是线性复杂度！但它是有条件的。

举个例子：一年的全国高考考生人数为500万，分数使用标准分，最低100，最高900，没有小数，你把这500万元素的数组排个序。我们抓住了这么个非常特殊的条件，就能在毫秒级内完成这500万的排序，那就是：最低100，最高900，没有小数，那一共可出现的分数可能有多少种呢？一共有900-100+1=801，那么多种，想想看，有没有什么“投机取巧”的办法？方法就是创建801个“桶”，从头到尾遍历一次数组，对不同的分数给不同的“桶”加料.

比如有个考生考了500分，那么就给500分的那个桶（下标为500-100）加1，完成后遍历一下这个桶数组，按照桶值，填充原数组，100分的有1000人，于是从0填到999，都填1000，101分的有1200人，于是从1000到2019，都填入101.于是经过这次遍历之后所有记录都是有序的了。

很显然，如果分数不是从100到900的整数，而是从0到2亿，那就要分配2亿个桶了，这是不可能的，所以桶排序有其局限性，适合元素值集合并不大的情况。

 

 

在上面的基础上就有了基数排序

基数排序是对桶排序的一种改进，这种改进是让“桶排序”适合于更大的元素值集合的情况，而不是提高性能。

 

我们先看看扑克牌的例子。一张牌有两个关键字组成：花色(桃<心<梅<方)+面值(2<3<4<...<A)。假如一张牌的大小首先被花色决定，同花色的牌有数字决定的话。我们就有两种算法来解决这个问题。

(1) 首先按照花色对所有牌进行稳定排序，这样就可以将所有牌分成4组。然后同组的牌(同花色)再按照面值进行排序。

(2) 首先按照面值对所有牌进行稳定排序，然后按照花色再次对所有牌进行稳定排序。

在这里的第二种方法就是基数排序！————也就是从最次的关键字开始排序，再从第二次的关键字排序，过程中参考第一次排序后元素间的相对顺序，以此类推直到最高关键字参考了次高关键的顺序而排序完成，排序结束。

 

 

比如字符串“abcd” “aesc” "dwsc" "rews"就可以把每个字符看成一个关键字。另外还有整数 425、321、235、432也可以每个位上的数字为一个关键字。

 

基数排序的思想就是将待排数据中的每组关键字依次进行桶分配。比如下面的待排序列：

                 278、109、063、930、589、184、505、269、008、083

我们将每个数值的个位，十位，百位分成三个关键字： 278 -> k1(个位)=8  ，k2(十位)=7 ，k3=(百位)=2。

然后从最低位个位开始(从最次关键字开始)，对所有数据的k1关键字进行桶分配(因为，每个数字都是 0-9的，因此桶大小为10)，再依次输出桶中的数据得到下面的序列。

       930、063、083、184、505、278、008、109、589、269（从最次关键字开始排序）

再对上面的序列接着进行针对k2的桶分配，输出序列为：

       505、008、109、930、063、269、278、083、184、589（参考最次关键字来排序第二次关键字）

最后针对k3的桶分配，输出序列为：

       008、063、083、109、184、269、278、505、589、930（参考第二次关键字来排序最高关键字）

 

很明显，基数排序的性能比桶排序要略差。每一次关键字的桶分配都需要O(N)的时间复杂度，而且分配之后得到新的关键字序列又需要O(N)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2N) ，当然d要远远小于N，因此基本上还是线性级别的。但是，对比桶排序，基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作，而桶排序在桶相对较少的情况下，桶内多个数据必须进行基于比较操作的排序。

 

经典排序算法 - 基数排序Radix sort

原理类似桶排序,这里总是需要10个桶,多次使用

首先以个位数的值进行装桶,即个位数为1则放入1号桶,为9则放入9号桶,暂时忽视十位数

例如

待排序数组[62,14,59,88,16]简单点五个数字

分配10个桶,桶编号为0-9,以个位数数字为桶编号依次入桶,变成下边这样

|  0  |  0  | 62 |  0  | 14 |  0  | 16 |  0  |  88 | 59 |

|  0  |  1  |  2  |  3  |  4 |  5  |  6  |  7  |  8  |  9  |桶编号

将桶里的数字顺序取出来,

输出结果:[62,14,16,88,59]

再次入桶,不过这次以十位数的数字为准,进入相应的桶,变成下边这样:

由于前边做了个位数的排序,所以当十位数相等时,个位数字是由小到大的顺序入桶的,就是说,入完桶还是有序

|  0  | 14,16 |  0  |  0  |  0  | 59 | 62  | 0  | 88  |  0  |

|  0  |  1      |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |桶编号

 

因为没有大过100的数字,没有百位数,所以到这排序完毕,顺序取出即可

最后输出结果:[14,16,59,62,88]