基数排序

基数排序和计数排序一样，是非基于比较的排序算法，它借助“分配”和“收集”两种操作对单逻辑关键字进行排序（基于箱/桶排序），它的排序速度很快，时间复杂度为线性，但由于需要的辅助空间太大（n(radix+1)），因此长期无法应用。直到1954年有人提出用“计数”代替“分配”才得以使它能在计算机上实现。此后，又有人提出用链表作为存储数据的结构，这样又能减少一些辅助空间，这也是一种比较好的实现方法（只是算法要较复杂）。

基数排序分为MSD（最高位优先）基数排序和LSD（最低位优先）基数排序，MSD从左到右处理关键字的位数，首先处理最重要的数字。它比较符合常规的思维，所需处理的信息量也较少。但按MSD进行排序，必须将序列逐层分割成若干个子序列，然后对各子序列分别进行排序；而LSD则从右到左先处理最不重要的数字，这样虽然可能花费了一些时间来处理不会影响结果的信息，但它不用分子序列，对每个关键字都是整个序列参加排序，而且对具体的应用还可以对其进行改进。因此在很多排序应用中都选择这种方法。

基数排序（LSD/用计数排序）的C/C++代码实现：

这是以16进制方式对整数进行基数排序，若用十进制方式，则抽取关键字当中某位数字时（即a[j]>>4*i&0xf处）会稍显复杂，效率也稍低。

基数排序的时间复杂度如上面所说是线性的O(n)，由于是非比较排序，所以可以突破比较排序O(n㏒ⁿ)的时间复杂度下限。因此通常来说比所有的比较排序都快。但由于计数排序的内部循环中的操作数目比快速排序或归并排序内部循环要多的多，因此这里的线性运行时间可能并不比快速排序的运行时间少很多。

基数排序还有一个问题是它的应用范围并不如比较排序应用的广泛，这主要是因为基数排序基于的关键字抽取算法没有比较排序的比较操作那么普遍。

基数排序是稳定的排序方法。