基数排序
与基于比较的排序算法（归并排序、堆排序、快速排序、冒泡排序、插入排序等等）相比，基于比较的排序算法的时间复杂度最好也就是\(O(nlogn)\) ，而且不能比\(O(nlogn)\)更小了。
计数排序（Counting Sort）的时间复杂度为\(O(n)\)量级，更准确的说，计数排序的时间复杂度为\(O(n+k)\) ，其中 k 表示待排序元素的取值范围（最大与最小元素之差加 1 ）。
那么问题来了，当这个元素的的范围在 1 到 \(n^2\) 怎么办呢？
此时就不能用计数排 序了奥，因为这种情况下，计数排序的时间复杂度达到了\(O(n^2)\)量级。
比如对数组 [170, 45, 75, 90, 802, 24, 2, 66] 这个而言，数组总共包含 8 个元素，而数组中的最大值和最小值之差为 802 - 2 = 800 ，这种情况下，计数排序就 ”失灵了“ 。
那么有没有那种排序算法可以在线性时间对这个数组进行排序呢？
答案就是今天要讲的 基数排序（Radix Sorting） 。基数排序的总体思想就是从待排序数组当中，元素的最低有效位到最高有效位 逐位 进行比较排序；此外，基数排序使用计数排序作为一个排序的子过程。
下面我们就以数组 [170, 45, 75, 90, 802, 24, 2, 66] ，快乐学习基数排序！
数组当中的最大值 802 为三位数，所以我们在不足三位的数字前面补 0 ，即[170, 045, 075, 090, 802, 024, 002, 066]方便后续说明基数排序。
第一步：按数组当中元素的最低有效位，个位 [17**0**** ,04****5**** ,07****5**** , 09****0**** ,80****2**** , 02****4**** , 00****2**** , 06****6**** ]**，进行计数排序：
第二步：按数组当中元素的次最低有效位，十位数 [1**70, 090, 802, 002, 024, 045, 075, 066****]** ，进行计数排序：
第三步：按数组当中元素的最高有效位，百位 **[****8**02, **0**02, **0**24, **0**45, **0**66, **1**70, **0**75, **0**90] ，进行计数排序：
这样我们就完成了基数排序，得到了一个有序数组 [2, 24, 45, 66, 75, 90, 170, 802] .
高清视频动画
实现代码
import java.io.*;
import java.util.*;
class Radix {
// 获取数组中的最大值
static int getMax(int arr[], int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
max = arr[i];
return max;
}
// 计数排序
static void countSort(int arr[], int n, int exp)
{
int output[] = new int[n]; //输出数组
int i;
int count[] = new int[10];
Arrays.fill(count,0);
// 统计数组中元素第 exp 位的数目
for (i = 0; i < n; i++){
count[(arr[i]/exp)%10]++;
}
// 对 count[] 数组进行转
for (i = 1; i < 10; i++){
count[i] += count[i - 1];
}
// 进行计数排序
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
// 输出到数组arr[]中
for (i = 0; i < n; i++){
arr[i] = output[i];
}
}
// 基数排序
static void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// 对数组当中的数字按照每一个有效位进行一趟计数排序。
for (int exp = 1; m/exp > 0; exp *= 10){
countSort(arr, n, exp);
}
}
// 进行输出
static void print(int arr[], int n)
{
for (int i=0; i<n; i++)
System.out.print(arr[i]+" ");
}
/*Driver function to check for above function*/
public static void main (String[] args)
{
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = arr.length;
radixsort(arr, n);
print(arr, n);
}
}实现当中有一个细节需要解释一下，那就是如何从最低位到最高位取每一个数字的该位的值。答案很简单了，就是除 10 取余。
比如 802 ，要取最低位，802 % 10 = 2 ，就取到了个位；紧接着除 10 取商数 802 / 10 = 80 ，然后对商数 80 进行除 10 取余数，就可以得到十位了，80 % 10 = 0 ；最后再对 80 除 10 取商数 80 / 10 = 8 ， 然后对商数 8 进行除 10 取余数，8 % 10 = 8 就可以得到百位数。
代码中的 (arr[i] / exp) % 10 就可以轻松理解啦， exp 就相当于控制位数，而取余操作就相当于取出第 exp 位的值。
当然彻底搞懂基数排序，前提是你要清楚计数排序（Counting Sort），又到打广告的时间了，推荐看一下 漫画：什么是计数排序？。
复杂度分析
时间复杂度
设 \(d\) 表示输入的数组当中最大值的位数（比如 802，3位，\(d=3\)），那么基数排序的时间复杂度就是\(O(d\times (n+b))\) ，其中\(n\)表示数组的长度，而\(b\)则是表示一个数的基础，对十进制而言, \(b=10\) ；
设\(K\)是一个计算机可表示的最大整数，那么\(d=log_bK\)；
则基数排序整个时间复杂度为\(O((n+b)\times log_bK)\) 。
对于一个较大的数\(K\)，计数排序的这个时间复杂度似乎比基于比较的排序算法都慢，但是事实未必，接着看。
假设\(K\le n^c\) 取一个最大整数，其中\(c\)是一个常量；
那么基数排序的时间复杂度就为\(O(c\times (n+b)\times log_bn)\) ，其中\(b\)和\(c\)都是常数，我们可以忽略不计，那么基数排序的时间复杂度就变成了\(O(nlog_bn)\) ，但是这依旧不比基于排序算法的最好时间复杂度\(O(nlogn)\) 好呀？
可是当我们将这个\(b\)取足够大呢？ 取多少的时候基数排序的时间复杂度才能变成线性呢？
当\(b=n\)的时候，\(log_nn=1\)，基数排序的时间复杂度就变成了\(O(n)\)，线性时间复杂度。
也就说，当数字用\(n\)进制表示的时候，我们就可以对 1 到 \(n^c\)范围之内的数组进行线性排序。
对于元素的跨度（范围）比较大的数组而言，基数排序的运行时间可能比快速排序要好。但是对于基数排序而言，其渐近时间复杂度中隐含了更高的常量因子，并非完全的线性；而快速排序更有效地利用硬件缓存，提高其效率。此外，基数排序使用计数排序作为子过程，计数排序占用额外的空间来对数组进行排序。
但是基数排序解决我们最开始所提出的问题，当数据范围在 1 到 \(n^2\)时，计数排序的复杂度将变为\(O(n^2)\) 量级，而基数排序依旧可以在线性时间进行排序！
空间复杂度
计数排序使用了额外的空间进行排序，空间复杂度为 \(O(n)\) 。