素都是不大于k=6的正整数。
图1 计数排序算法演示

容 易理解，算法的第(l)行是对数组tmp初始化。第(2)行检查每个输入元素。如果输入元素的键值为i，则tmp[i]增1。因此，在第(2)行执行结束 后，tmp[i]中存放着值等于i的输入元素个数，i=1,2,..,k。算法的第(3)行，对每个i=1,2,..,i，统计值小于或等于i的输入元素 个数。最后在(4)-(8)行中，将每个元素L[j]存放到输出数组R中相应的最终位置上。如果所有n个元素的值都不相同，则共有tmp[L[j]]个元 素的键值小于或等于L[j]，而小于L[j]的元素有tmp[L[j]]-1个，因此tmp[L[j]]就是L[j]在输出数组R中的正确位置。当输入元 素有相同的值时，每将一个L[j]存放到数组R时，tmp[L[j]]就减1，使下
个值等于L[j]的元素存放在输出数组R中存放元素L[j]的前一个位置上。

计 数排序算法的计算时间复杂性很容易分析。其中，第(1)行需要O(k)时间；第(2)行需要O(n)时间，第(3)行需要O(k)时间；第(4)-(8) 行的for循环需要O(n)时间。这样，整个算法所需的计算间为O(n+k)。当k=O(n)时，算法的计算时间复杂性为O(n)。

我们 看到，计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置。因此，计数排序算法不是一个基于比较的排序算法，从而它的计 算时间下界不再是Ω(nlogn)。另一方面，计数排序算法之所以能取得线性计算时间的上界是因为对元素的取值范围作了一定限制，即k=O(n)。如果k =n2,n3,..，就得不到线性时间的上界。此外，我们还看到，由于算法第4行使用了downto语句，经计数排序，输出序列中值相同的元素之间的相对 次序与他们在输入序列中的相对次序相同，换句话说，计数排序算法是一个稳定的排序算法，但显然不是原地置换排序算法。

基数排序 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)比 较排序算法却是可以的。因此，当内存比较紧张时，一般来说选择快速排序更合适些。

桶排序 Bin Sort

平均情况下桶排序以线性时间运行。像计数排序一样，桶排序也对输入作了某种假设， 因而运行得很快。具体来说，计数排序假设输入是由一个小范围内的整数构成，而桶排序则 假设输入由一个随机过程产生，该过程将元素一致地分布在区间[0，1)上。

桶排序的思想就是把区间[0，1)划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数均匀分布在[0，1)上，所以一般不会有很多数落在 一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列 出来即可。

在桶排序算法的代码中，假设输入是个含n个元素的数组A，且每个元素满足0≤ A[i]<1。另外还需要一个辅助数组B[O..n-1]来存放链表实现的桶，并假设可以用某种机制来维护这些表。

桶排序的算法如下，其中floor(x)是地板函数，表示不超过x的最大整数。

procedure Bin_Sort(var A:List);

begin

1 n:=length(A);

2 for i:=1 to n do

3 将A[i]插到表B[floor(n*A[i])]中;

4 for i:=0 to n-1 do

5 用插入排序对表B[i]进行排序;

6 将表B[0],B[1],...,B[n-1]按顺序合并;

end;



图1 Bin_Sort的操作

图1 演示了桶排序作用于有10个数的输入数组上的操作过程。(a)输入数组A[1..10]。(b)在该算法的第5行后的有序表(桶)数组B[0..9]。桶 i中存放了区间[i/10，(i+1)/10]上的值。排序输出由表B[O]、B[1]、...、B[9]的按序并置构成。

要说明这 个算法能证确地工作，看两个元素A[i]和A[j]。如果它们落在同一个桶中，则它们在输出序列中有着正确的相对次序，因为它们所在的桶是采用插入排序 的。现假设它们落到不同的桶中，设分别为B[i']和B[j']。不失一般性，假设i'<j'。在算法的代码中，当第6行中将B中的表并置起来时， 桶B[i']中的元素先于桶B[j']中的元素，因而在输出序列中A[i]先于A[j]。现在要证鰽[i]≤A[j]。假设情况正好相反，我们有：

i'=floor(n*A[i])≥floor(n*A[j])=j'

得矛盾 (因为i'<j')，从而证明桶排序能正确地工作。

现在来分析算法的运行时间。除第5行外，所有各行在最坏情况的时间都是O(n)。第5行中检查所有桶的时间是O(n)。分析中唯一有趣的部分就在于第5行中插人排序所花的时间。

为分析插人排序的时间代价，设ni为表示桶B[i]中元素个数的随机变量。因为插入排序以二次时间运行，故为排序桶B[i]中元素的期望时间为E[O(ni2)]=O(E[ni2])，对各个桶中的所有元素排序的总期望时间为：

(1)

为 了求这个和式，要确定每个随机变量ni的分布。我们共有n个元素，n个桶。某个元素落到桶B[i]的概率为l/n，因为每个桶对应于区间[0，1)的 l/n。这种情况与投球的例子很类似：有n个球 (元素)和n个盒子 (桶)，每次投球都是独立的，且以概率p=1/n落到任一桶中。这样，ni=k的概率就服从二项分布B(k;n,p)，其期望值为E[ni]=np=1， 方差V[ni]=np(1-p)=1-1/n。对任意随机变量X，有:

　 (2)

将这个界用到(1)式上，得出桶排序中的插人排序的期望运行时间为O(n)。因而，整个桶排序的期望运行时间就是线性的。

下面的Java Applet程序演示了桶排序的基本思想。

在该演示程序中，线性表的元素类型为整型，桶的标号为整数，算法将值为i的元素放入标号为i的桶中，再按照桶的标号的顺序将元素依次取出，就得到了最终的排序结果。