基于比较的排序算法（合并排序、堆排序、快排等）的上限是 O(nLogn)，即它们不能比nLogn 做得更好。计数排序是一种线性时间排序算法，当元素在从 1 到 k 的范围内时，它在 O(n+k) 时间内排序。
但如果元素在1 到 n^2的范围内怎么办？
我们不能使用计数排序，因为计数排序需要 O(n^2)的时间，这比基于一些比较排序算法要更差。那么我们怎样才可以在线性时间内对这样的数组进行排序吗？
答案就是基数排序即Radix Sort。基数排序的思想是从数的最低有效位到最高有效位进行逐位排序，注意基数排序内部使用计数排序作为子程序进行排序。
基数排序的例子：
原始未排序列表：170、45、75、90、802、24、2、66
我们先按照每个元素的个位的数字的大小进行排序得到 17 0 , 9 0 , 80 2 , 2 , 2 4 , 4 5 , 7 5 , 6 6
注意我们将802排在2前面是因为在原数组中802在2之前，170和90，45和75也是如此
然后根据每个元素的十位的数字进行排序得到 8 0 2, 2, 2 4, 4 5, 6 6, 1 7 0, 7 5, 9 0
最后按照百位数字排序 2、24、45、66、75、90、1 70、8 02
小于100的数没有百分位所以我们将其看作0
假设输入的元素有d位数。基数排序需要 O(d*(n+b)) 时间，其中 b 是表示数字的基数，例如，对于十进制系统，b 是 10。d 的值是多少？如果 k 是数组中最大的数，则 d 将为 O(log b (k))。所以整体时间复杂度是 O((n+b) * log b (k))。如果k很大的话，基数排序似乎比基于比较的排序的时间复杂度要更高。因此我们需要限制k。让 k <= n^c其中 c 是一个常数。在这种情况下，复杂度变为 O(nLog b (n))。但它仍然无法击败基于比较的排序算法。
如果我们让 b 的值更大呢？使时间复杂度线性化的 b 值应该是多少？如果我们将 b 设置为 n，我们得到的时间复杂度为 O(n)。换句话说，如果数字以 n 为底表示（或者每个数字占用 log 2 (n) 位） ，我们可以对范围从 1 到 n^c的整数数组进行线性时间的排序。
基数排序比快速排序等基于比较的排序算法更可取吗？
假设每个数字有log 2 n 位，则 Radix 的运行时间似乎比快速排序对于大范围的输入数字要好。基数排序中隐藏在渐近符号中的常数因子更高，快速排序更有效地使用硬件缓存。此外，基数排序使用计数排序作为子程序，计数排序需要额外的空间来对数字进行排序。
基数排序的要点：
这里给出了一些关于基数排序的关键点
- 数据必须满足一些假设，例如数据必须在一系列元素之间。
- 输入数组必须具有相同基数和宽度的元素。
- 基数排序基于单个数字或字母位置进行排序。
- 我们必须从最右边的位置开始排序，并在每个位置使用稳定的算法。
- 基数排序不是就地算法，因为它使用临时计数数组。
代码演示：
主程序
计数排序作为子程序
复杂度表：
其他语言实现下载链接：
（包含各种语言：C语言、Python、Java、C++等均有示例）
免费资源下载：Radix Sort