动画：什么是基数排序？
基数排序
与基于比较的排序算法（归并排序、堆排序、快速排序、冒泡排序、插入排序等等）相比，基于比较的排序算法的时间复杂度最好也就是 ，而且不能比 更小了。
计数排序（Counting Sort）的时间复杂度为 量级，更准确的说，计数排序的时间复杂度为 ，其中 表示待排序元素的取值范围（最大与最小元素之差加 1 ）。
那么问题来了，当这个元素的的范围在 1 到 怎么办呢？
此时就不能用计数排序了奥，因为这种情况下，计数排序的时间复杂度达到了 量级。
比如对数组 [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]方便后续说明基数排序。
第一步：按数组当中元素的最低有效位，个位 [170 ,045 ,075 , 090 ,802 , 024 , 002 , 066 ]，进行计数排序：
第二步：按数组当中元素的次最低有效位，十位数 [170, 090, 802, 002, 024, 045, 075, 066] ，进行计数排序：
第三步：按数组当中元素的最高有效位，百位 [802, 002, 024, 045, 066, 170, 075, 090] ，进行计数排序：
这样我们就完成了基数排序，得到了一个有序数组 [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），又到打广告的时间了，推荐看一下 漫画：什么是计数排序？。
复杂度分析
时间复杂度
设 表示输入的数组当中最大值的位数（比如 802，3位， ），那么基数排序的时间复杂度就是 ，其中 表示数组的长度，而 则是表示一个数的基础，对十进制而言， ；
设 是一个计算机可表示的最大整数，那么 ；
则基数排序整个时间复杂度为 。
对于一个较大的数 ，计数排序的这个时间复杂度似乎比基于比较的排序算法都慢，但是事实未必，接着看。
假设 取一个最大整数，其中 是一个常量；
那么基数排序的时间复杂度就为 ，其中 和 都是常数，我们可以忽略不计，那么基数排序的时间复杂度就变成了 ，但是这依旧不比基于排序算法的最好时间复杂度 好呀？
可是当我们将这个 取足够大呢？ 取多少的时候基数排序的时间复杂度才能变成线性呢？
当 的时候， ，基数排序的时间复杂度就变成了 ，线性时间复杂度。
也就说，当数字用 进制表示的时候，我们就可以对 1 到 范围之内的数组进行线性排序。
对于元素的跨度（范围）比较大的数组而言，基数排序的运行时间可能比快速排序要好。但是对于基数排序而言，其渐近时间复杂度中隐含了更高的常量因子，并非完全的线性；而快速排序更有效地利用硬件缓存，提高其效率。此外，基数排序使用计数排序作为子过程，计数排序占用额外的空间来对数组进行排序。
但是基数排序解决我们最开始所提出的问题，当数据范围在 1 到 时，计数排序的复杂度将变为 量级，而基数排序依旧可以在线性时间进行排序！
空间复杂度
计数排序使用了额外的空间进行排序，空间复杂度为 。