线性时间排序算法——基数排序（Radix Sort）

基数排序是一种用在老式穿卡机上的算法。一张卡片有80列，每列可在12个位置中的任一处穿孔。排序器可被机械地"程序化" 以检查每一迭卡片中的某一列，再根据穿孔的位置将它们分放12个盒子里。这样，操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面，第二个 位置穿孔的其次，等等。 对十进制数字来说，每列中只用到10个位置(另两个位置用于编码非数值字符)。一个d位数占用d个列。因为卡片排序器一次只能查看一个列，要对n张片上的d位数进行排序就要有个排序算法。 直感上，大家可能觉得应该按最重要的一位排序，然后对每个盒子中的数递归地排序，最后把结果合并起来。不幸的是，为排序每一个盒子中的数，10个盒子中的9个必须先放在一边，这个过程产生了许多要加以记录的中间卡片堆。 与人们的直感相反，基数排序是首先按最不重要的一位数字排序来解决卡片排序问题的。同样，把各堆卡片收集成一迭，其中0号盒子中的在1号盒子中的前面，后者又在2号盒子中的前面，等等。然后对整个一迭卡片按次重要位排序，并把结果同样地合并起来。 重复这个过程，直到对所有的d位数字都进行了排序。所以，仅需要n遍就可将一迭卡片排好序。图1说明了基数排序作“一迭”7个三位数的过程。第一列为输入，其余各列示出了对各个数位进行逐次排序后表的情形。垂直向上的箭头指示了当前要被加以排序的数位。 图1 基数排序作用于一个由7个3位数组成的表上的过程 关于这个算法很重要的一点就是按位排序要稳定。由卡片排序器所故的排序是稳定的，但操作员在把卡片从盒子里拿出来时不能改变他们的次序，即使某一盒子中所有卡片在给定列上的穿孔位置都相同。 在一台典型的顺序随机存取计算机上，有时采用基数排序来对有多重域关键字的记录进行排序。例如，假设我们想根据三个关键字处、月和日来对日期排序。对这 个问题，可以用带有比较函数的排序算法来做。给定两个日期，先比较年份，如果相同，再比较月份，如果再相同，再比较日。这儿我们可以采用另一个方法，即用 一种稳定的排序方法对所给信息进行三次排序：先对日，其次对月，再对年。 基数排序的代码是很简单的、下面的过程假设长度为n的数组A中的每个元素都有d位数字，其中第1位是最低的，第d位是最高位。 procedure Radix_Sort(var L:List;d:integer); var i:integer; begin 1  for i:=1 to d do 2     使用一种稳定的排序方法来对数组L按数字i进行排序; end; 基数排序的正确性可以通过对正在被排序的列进行归纳而加以证明。对本算法时间代价的分析要取决于选择哪种稳定的中间排序算法。当每位数字都界于l到k之 间，且k不太大时，可以选择计数排序。对n个d位数的每一遍处理的时间为O(n+k)，共有d遍，故基数排序的总时间为θ(dn+kd)。当d为常 数，k=O(n)时，基数排序有线性运行时间。 某些计算机科学家倾向于把一个计算机字中所含位数看成是θ(lgn)。具体一点说，假 设共有dlgn位数字，d为正常数。这样，如果待排序的每个数恰能容于一个计算机字内，我们就可以把它视为一个以n为基数的d位数。看一个例子：对一百万 个64位数排序。通过把这些数当作是以216为基数的四位数，用基数排序四遍就可完成排序。 这与一个典型的O(nlgn)比较排序相 比要好得多，后者对每一个参加排序的数约要lgn=20次操作。但有一点不理想，即采用计数排序作为中间稳定排序算法的基数排序版本不能够进行原地置换排 序，而很多O(nlgn)比较排序算法却是可以的。因此，当内存比较紧张时，一般来说选择快速排序更合适些。