目录
概述
算法分析
参考文献
概述
基数排序(radixsort)是一种用在老式穿卡机上的算法。一张卡片有80列，每列可在12个位置中的任一处穿孔。排序器可被机械地"程序化"以检查每一迭卡片中的某一列，再根据穿孔的位置将它们分放12个盒子里。这样，操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面，第二个位置穿孔的其次，等等。对十进制数字来说，每列中只用到10个位置(另两个位置用于编码非数值字符)。一个d位数占用d个列。因为卡片排序器一次只能查看一个列，要对n张片上的d位数进行排序就要有个排序算法。
直觉上，大家可能觉得应该按最重要的一位排序，然后对每个盒子中的数递归地排序，最后把结果合并起来。不幸的是，为排序每一个盒子中的数，10个盒子中的9个必须先放在一边，这个过程产生了许多要加以记录的中间卡片堆。
与人们的直觉相反，基数排序是首先按最低有效位数字进行排序，以解决卡片排序问题。同样，把各堆卡片收集成一迭，其中0号盒子中的在1号盒子中的前面，后者又在2号盒子中的前面，等等。然后对整个一迭卡片按次重要位排序，并把结果同样地合并起来。重复这个过程，直到对所有的d位数字都进行了排序。所以，仅需要n遍就可将一迭卡片排好序。图1说明了基数排序作“一迭”7个三位数的过程。第一列为输入，其余各列示出了对各个数位进行逐次排序后表的情形。垂直向上的箭头指示了当前要被加以排序的数位。
data/attachment/portal/201111/06/143034vha4rzklhvk9c7hk.gif基数排序作用于一个由7个3位数
关于这个算法很重要的一点就是按位排序要稳定。由卡片排序器所故的排序是稳定的，但操作员在把卡片从盒子里拿出来时不能改变他们的次序，即使某一盒子中所有卡片在给定列上的穿孔位置都相同。
在一台典型的顺序随机存取计算机上，有时采用基数排序来对有多重域关键字的记录进行排序。例如，假设我们想根据三个关键字处、月和日来对日期排序。对这个问题，可以用带有比较函数的排序算法来做。给定两个日期，先比较年份，如果相同，再比较月份，如果再相同，再比较日。这儿我们可以采用另一个方法，即用一种稳定的排序方法对所给信息进行三次排序：先对日，其次对月，再对年。
基数排序的代码是很简单的、下面的过程假设长度为n的数组A中的每个元素都有d位数字，其中第1位是最低的，第d位是最高位。
RADIX-SORT(A,d)
1fori=1tod
2使用一种稳定排序算法对A中元素的第i位进行排序
算法分析
基数排序是否要比基于比较的排序算法（比如快速排序）更好呢？如果根据常见的情况有b=O（lgn），并选择r≈lgn，则基数排序的运行时间为O（n），这看上去要比快速排序的平均情况时间O（nlgn）更好些。然而，在这两个时间中隐含在O记号中的常数因子是不同的。对于要处理的n个关键字，尽管基数排序执行的遍数可能要比快速排序要少，但每一遍所需的时间都要长得多。哪一个排序算法更好取决于底层机器的实现特性（例如，快速排序通常可以比基数排序更为有效的利用硬件缓存），同时还取决于输入的数据。此外，利用计数排序作为中间稳定排序的基数排序不是原地排序，而很多O（nlgn）时间的比较排序算法则可以做到原地排序。因此当内存容量比较宝贵时，像快速排序这样的原地排序算法可能是更为可取的。
参考文献
【1】《算法导论》第二版作者ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein译者潘金贵李成法等机械工业出版社