基数排序

分配排序

分配排序（Distributive Sort）：排序过程无须比较关键字，而是通过“分配”和“收集”操作来实现排序，它们的时间复杂度可达到线性阶：O(n)，典型的计数排序、桶排序以及基数排序等。

计数排序（Counting Sort）

基本思想

计数排序于1954年由 Harold H. Seward 提出是一种，它是一种不基于比较的排序算法。元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的，排序过程中不存在元素之间的比较和交换操作。

具体地，由待排序列的最大值 max 与 最小值 min，开辟一个长度为 max-min+1 的额外空间，然后根据元素本身的值，统计每个元素的数量并记录到辅助空间中，最后对额外空间内数据进行计算，得出每一个元素的正确位置，按照相应位置把元素还原到到原序列中完成排序。

其空间复杂度和时间复杂度均为 O(n+k)，其中 k 是整数的范围；而基于比较的排序算法时间复杂度最小是 O(nlogn)的。

作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

重点在于开辟额外空间，统计每个元素的数量，即计数排序得名之源。

代码实现

基数排序过程中，是将待排序集合中的每个元素值本身大小作为下标，依次进行了存放，而记录的值是元素出现的次数。

void CountSort(int L[], int n)
{
    create B[n+1] = L, C[k+1] // 计数
    for i=0 to k // 初始化
        C[i] = 0
    for i=1 to n // 计数
        ++C[L[i]]

    for i=1 to k
        C[i] += C[i-1] // 计算排序后每一段的最大下标位置
    for i=n to 1 // 从后往前，保证稳定性
        L[ C[ B[i] ]-- ] = B[i]
}

归纳分析

1. 稳定排序（stable sort）

不会改变相同元素的相对顺序，因此计数排序是稳定排序。

2. 空间复杂度 （out-of-place 非原地算法，O(n+k)）

算法运行时需要额外空间 k 统计元素数量和一个与待排序集合大小相同的已排序空间计算元素最终位置，所以空间复杂度为 O(n+k)。

3. 时间复杂度

第一趟遍历统计每个元素的数量（分配），时间复杂度为 O(n)；
之后遍历辅助空间 k 计算确定元素最终位置（收集），时间复杂度为 O(k)。

计数排序的时间复杂度为 O(n+k)。

4. 初态影响

不是基于比较的排序，对初始状态不敏感，当然，原始序列最值之差越大，需要的辅助空间就越多，效率就会降低。

5. 适用性

计数排序适用于元素值较为集中的情况，若集合中最值元素的值相差甚远，元素分布不均匀，那么计数排序会浪费较大的开销、性能较差。

另外，额外空间存储元素信息是通过计算元素与最小元素值的差值作为下标来完成的，若待排序集合中存在元素值为浮点数形式或其他形式，则需要对元素值或元素差值做变换，以保证所有差值都是非负整数形式。

计数排序需要一定的定制，需要知道待排序列的一些大致分布情况，从而确定辅助技术空间的大小。

桶排序（Bucket Sort）

基本思想

桶排序也称为箱排序（Bin Sort），是计数排序的扩展改进，计数排序申请的额外空间跨度从最小元素值到最大元素值，即相当于划分了 max-min+1 个桶，每个桶只存储相同元素，若待排序集合中元素不是依次递增的，则必然有空间浪费情况；

而桶排序弱化了这种浪费情况，不再是为最小值到最大值之间的每个位置申请空间，而是为最小值到最大值之间每一个固定区域申请空间，尽量减少了元素值大小不连续情况下空间的浪费。

也就是说桶排序中每个桶存储的是一定范围的元素而非单一值域元素。它通过映射函数，将待排序数组中的元素映射到各个对应的桶中，从值域上看是处于有序状态的，对每个桶中的元素进行排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将非空桶中的元素逐个放回原序列。

由于桶排序利用了函数的映射关系，所以高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，往往需要做到两点：

（1）在额外空间充足的情况下，尽量增大桶的数量；
（2）使用的映射函数能够将输入的 N 个数据尽量均匀的分配到 K 个桶中。

另外，由于每个桶是存储了一定范围的元素，所以还需要随桶内元素进行排序，在桶内选择何种比较排序算法对于性能的影响也至关重要。

显然，排序中元素尽可能均匀分配到每一个桶中时，排序效率相对就高，运行时间为线性 Θ(n)；而当元素集中在同一个桶中时，桶排序失效，退化为桶内排序，效率最差。

桶排序不是基于比较排序，不受 O(nlogn) 下限的限制。

代码实现

桶排序的实现有两个关键点：

（1）桶的划分，即元素到桶的映射规则。映射规则要根据待排序集合的元素分布情况来选择。规则太粗糙宽泛，就会导致所有元素都映射到一个桶上，桶排序也就失效，变成基于比较的排序。规则太具体细致，又会导致每个元素值映射到一个单独的桶上，桶排序就退化成计数排序。

（2）桶内排序的选择，各个桶内元素进行排序时，可以自主选择合适的排序算法，这样桶排序算法的复杂度和稳定性，都会随桶内排序算法的不同而变化。

void BucketSort(int L[], int n)
{
    create buckets B[m]
    for i=1 to n
        insert L[i] to B[f(L[i])]
    for i=1 to m
        sort B[i]
}

归纳分析

1. （不）稳定排序（(un)stable sort）

桶排序的稳定性取决于桶内排序使用的算法。

2. 空间复杂度 （out-of-place 非原地算法，O(n+m)）

算法运行时需要额外桶空间 m ，所以空间复杂度为 O(n+m)。

3. 时间复杂度

第一趟遍历待排序列，将元素移动到对应的桶中（分配过程），复杂度为 O(n)；第二趟遍历桶，对桶内元素进行排序，并移动回初始集合中（收集过程）。

设桶个数为 m，桶内采用 nlogn 级别的排序，平均每个桶中元素个数为 n/m，则时间复杂度为

O(n + m ∗ (n/m∗log(n/m))) = O(n+nlog(n/m))

当 m==n 时，桶排序退化为计数排序，桶内不再需要排序，复杂度为 O(n)。当 m==1 时，桶排序变成基于比较的排序，对桶内所有元素排序并将其移回初始集合，复杂度为 O(n+nlogn)。

4. 初态影响

原始序列会影响映射规则的选择，桶内是基于比较的排序，是否受初态影响跟排序算法选择有关。

5. 适用性

计数排序的升级版。

和计数排序一样，需要一定的定制，需要知道待排序列的一些大致分布情况，从而选择较为合理的映射规则。

问题

与快速排序区别

快速排序是将集合拆分为两个值域，相当于两个桶，再分别对两个桶进行排序，最终完成排序；桶排序则是将集合拆分为多个桶，对每个桶进行排序，则完成排序过程。

两者不同之处在于，快排是在集合本身上进行排序，属于原地排序方式，且对每个桶的排序方式也是快排；桶排序是提供了额外的操作空间，在额外空间上对桶进行排序，避免了构成桶过程的元素比较和交换操作，同时可以自主选择恰当的排序算法进行桶内排序。

基数排序（Radix Sort）

产生来源

基数排序在桶排序的基础上做了面向对象的优化改进，这种改进是让“桶排序”适合于更大的元素值集合情形，而不是提高性能。

桶排序需要选择适当的映射规则，来完成集合中元素到多个桶的映射，也可以称之为值域划分。但是当集合中元素跨度很大时，映射规则的设计比较困难，若规则设计的相对粗糙宽泛，桶的个数就较少，可以避免出现许多空桶的情况，但可能会存在元素分布不均的情形，那么桶排序就演变为基于比较的排序；若规则设计的相对精确细致则桶的个数较多，但又可能会存在大部分桶都是空桶的情况，造成较大空间的浪费。

桶排序之所以存在这些问题，原因在于算法中对待排序元素的属性选择所致。排序过程使用元素本身的 “大小” 属性，使得算法处理的元素集合就是这个 “大小” 的空间。例如，若待排序元素为整型，而整型数字在 “大小” 方面可以是无限大或者无限小的；若待排序元素为字符串，而字符串在 “长度” 方面是无限大的。而桶排序又是一种对元素总容量敏感的排序算法，所以存在使用限制。

基本思想

作为桶排序的改进，基数排序仍是一种非比较性质的排序，基本操作是“分配”和“收集”。

基数排序在桶排序的基础上优化划分值域的原则，不在直接用元素本身作为划分对象，而是将每个元素拆分为多个总容量空间较小的对象，对每个对象进行排序后，完成排序过程。因为将原来的一个排序关键字拆分成多个排序关键字，所以基数排序也称为多关键字；每个排序关键字的取值空间就是基数排序中的基数。

对于整型元素，是以每位数字作为排序对象；同理对于字符串型元素，是以每位字符作为对象。容易发现，排序对象的空间（基数）是有限的，所以在基数排序过程中，“分配”操作的空间得到了优化，能够对更大的元素集合进行桶排序。

由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序不是只能使用于整数。

根据多关键字从高到低或从低到高的排序顺序，基数排序分为：最高位优先（MSD）排序和最低位优先排序（LSD）。

三种分配排序小结：

三种排序都利用了桶的概念，但对桶的使用方法上有所区别：

计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；
基数排序：根据键值的每位数字来分配桶。

分类

最高位优先（Most Significant Digit first）排序，简称 MSD：

1）先按 k₁ 排序分组，将序列分成若干子序列，同一组序列的记录中，关键码 k₁ 相等；

2）再对各组按 k₂ 排序分成子组，依次对后面的关键码继续这样的排序分组，直到按最次位关键码 k_d 对各子组排序

3）最后将各组依次连接起来，便得到一个有序序列。

最低位优先（Least Significant Digit first）排序，简称 LSD：

1. 先从 k_d 开始排序，再对 k_d-1 进行排序，依次重复，直到按 k₁ 排序即可得到一个有序的序列。

容易发现，MSD 和 LSD 只约定按照怎样的“关键字次序”排序，没有规定单关键字如何排序；

单关键字排序时，如果划分每个桶的宽度（值域跨度）为 1，那就是计数排序，将待排序列中元素移动到各个桶上之后，不需要再对每个桶进行排序；如果划分的宽度（值域跨度）大于 1，那就是桶排序，将待排序列中元素移动到各个桶上之后，还需要进行桶内比较排序。

此外，两种方法在实现上有很大区别，复杂程度不一样，

MSD 需要将序列逐层分割成子序列，然后对各子序列继续排序；所以要使用 MSD 的话，在进行低位排序前需要更多的空间来保存高位的排序结果，否则，低位的排序将会覆盖高位的排序，而这必将导致排序错误，因为高位关键字的影响范围要比低位关键字广；

而 LSD 不需要分成子序列，每个单关键字排序都是整个序列参与分配排序，但是对 除最低位外的高位关键字 k_i（0≤i≤d≤-2）排序 时 必须采用稳定 排序，否则排序会出现错误。

例如 12、13，个位排序后的顺序是 12、13，现在进行十位的排序，十位均为 1，正常情况下，十位稳定排序后，当前的顺序不变，仍为 12、13，十位相同就需要看个位，而个位的顺序已确定（未被高位排序覆盖），如此就确定了大小顺序；

但是，如果十位排序不稳定，即排序结果为 13、12，因为高位关键字影响范围大于低位，这样就将直接覆盖低位的排序，而事实上这是错误的。

LSD 比 MSD 在算法实现上更简单，所用空间更少，依次通常讨论基数排序时默认为 LSD。

这就是排序算法稳定性对基数排序的重要影响。

代码实现

void RadixSort(int L[], int n)
{

}

归纳分析

1. 稳定排序（stable sort）

（LSD）为保证排序正确性，高位的排序要求必须使用稳定排序，而最低位默认也使用稳定排序，因此基数排序是一种稳定排序。

2. 空间复杂度 （out-of-place 非原地算法，O®）

算法运行时需要额外桶空间 r ，所以空间复杂度为 O®。

3. 时间复杂度

设 d 为元素最大位数，也是迭代分配的次数，r 为每位关键字的取值范围（基数）；
每一次迭代，先将元素分配到当前关键字划分的桶中，时间复杂度为 O(n)，然后按顺序从桶中收集元素放回原序列，完成一位关键字排序，时间复杂度为 O®；

基数排序的时间复杂度为 O(d(n+r))。

其中基数 r 是有限的，即为常数，元素位数一般也是常数，所以复杂度为 O(n)。

看起来，基数排序所要做的只是把原始数据项从数组复制到链表，然后再复制回去。如果有 10 个数据项，则有 20 次复制，对每一位重复一次这个过程。假设对 5 位的数字排序，就需要 20 * 5=100 次复制；如果有 100 个数据项，那么就有 200 * 5=1000 次复制。复制的次数与数据项的个数成正比，即 O(n)，相比于元素数量，关键字位数 d 和取值 r 可以忽略，和分析结果结果一致。

但是，随着数据项增多，就需要更长的关键字，算式中的位数 d 不可被忽视。以整数元素为例，如果数据项增加 10 倍，那么关键字必须增加一位（多一轮排序）。复制的次数和数据项的个数与关键字长度成正比，可以认为关键字长度是 n 的对数。因此在大多数情况下，基数排序的执行效率倒退为O(n*logn)，和快速排序差不多。

当然基数排序中不一定按照每一位进行排序，可以几位组合在一起，按照组合为单位进行排序。同时排序算法也不一定是桶排序方式，可以用其他排序算法，也可以给不同位用不同的排序算法。

总之基数排序提供了一个针对复杂元素类型的排序思路，可以针对元素中不同部分，选择不同的排序方式。

4. 初态影响

不影响

5. 过程特征

一趟排序无法确定一个元素的最终位置，不会产生有序子序列。

6. 适用性

元素数量很大，而元素的关键字位数较少且可分解时，使用基数排序较好。

计数/桶排序的升级版。

扩展

引理：假设 n 个 d 位数，将 d 位数分为多个单元，且每个单元为 r 位，那么基数排序的效率为 O[(d/r)(n+10^r)]。

迭代次数：d/r
每次迭代：分配 n ；收集：10^r-1 （基数）

当 d=O(nlgn)，r=lgn 时，基数排序效率 O(n)

如何在 O(n) 时间内，对 0~n^2-1 之间的 n 个整数排序？
答案：将这些数化为2进制，位数为 d=lg(n^2)=2lgn=O(lgn)，设 r=lgn，则基数排序可以在 O(n) 内排序。