《数据结构》课件第9章(内排序)

排序：设含有n个记录的文件{R1,R2,…，Rn

},其相应的关键字为{K1,K2,…，Kn

}，需确定一种排列P(1),P(2),…,P(n),使其相应的关键字满足如下的递增(或递减)关系：

KP(1)

≤KP(2)≤KP(3)≤…≤KP(n)

即，使上述文件成为一个按其关键字线性有序的文件{RP(1),RP(2),

…，RP(n)},这样一种运算称为排序。★基本概念排序的稳定性：如果在排序期间具有相同关键字的记录的相对位置不变，则称此方法是稳定的。即，1)K(i)

≤K(i+1)(1≤i≤n-1)2)若在输入文件中i<j,且Ki=Kj

,则在经过排序后的文件中仍Ri先于Rj排序内排序：整个排序过程都在内存进行的排序。外排序：当文件很大以至于内存不足以存放全部记录，在排序过程中需要对外存进行存取访问。

例如：将下列关键字序列

52,49,80,36,14,58,61,23,97,75调整为

14,23,36,49,52,58,61,75,80,97内部排序的方法

在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

使有序区中记录的数目增加一个或几个的操作称为一趟排序。存放待排序数据的数据结构：Typerecords=Recordkey:Integer;otheritem:anytype;end;List=Array[0..n]ofrecords;逐步扩大记录有序序列长度的方法大致有下列几类：1.插入类:将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度；2.交换类:通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；3.选择类:从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；4.归并类:通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度；5.其它方法。

★计数排序排序算法的思想：对每个记录计算文件中有多少个其它记录的关键字大于该记录的关键字值，从而找到该记录的正确排序位置。keyinfocount设一个记录有三个域：关键字域该记录的其他信息域计数域算法如下：ProcedureCount_sort(varr:List;n:Integer);BeginFori:=1tondor[i].count:=1;Fori:=1ton-1DoForj:=i+1tonDoIfr[i].key>r[j].keythenr[i].count:=r[i].count+1;elser[j].count:=r[j].count+1;

Fori:=1ton-1Do[j:=i;whiler[j].count<>iDoj:=j+1;ifi<>jthencallexchange(r[i],r[j]);]End;

算法性能分析：设文件有n个记录，则外循环：i=1时，内循环要做n-1次比较；i=2时，内循环要做n-2次比较；…i=n-1时，内循环要做1次比较；总的比较次数为(n-1)+(n-2)+…+1=n(n-1)/2所以，算法所需时间为O(n2)，由于不需要记录移动和额外空间，同时算法简单，当n较小时，可采用本算法。★直接插入排序假设在排序过程中，记录序列R[1..n]的状态为：

则一趟插入排序的基本思想为：将记录R[i]插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。显然，完成这个“插入”需分三步进行：1．查找R[i]的插入位置j+1；2．将R[j+1..i-1]中的记录后移一个位置；3．将R[i]复制到R[j+1]的位置上。直接插入排序：利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。注意直接插入排序算法的三个要点：

1.从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；

R[0]:=R[i]；{设置“哨兵”}

j:=i-1;while(R[0].key<R[j].key)Doj:=j-1;

{//从后往前找}

Return(j+1);{返回R[i]的插入位置为j+1}2.对于在查找过程中找到的那些关键字不小于R[i].key的记录，并在查找的同时实现记录向后移动；

while(R[0].key<R[j].key)Do[R[j+1]:=R[j];j:=j-1;]

3.i=2，3，…,n,实现整个序列的排序。排序算法如下：Procedureinsort(varr:List;n:Integer);BeginFori:=2tonDo[r[0]:=r[i];j:=i-1;whiler[0].key<r[j].keyDo[r[j+1]:=r[j];j:=j-1;]r[j+1]:=r[0];]End;排序的时间分析：

实现排序的基本操作有两个：（1）“比较”序列中两个关键字的大小；（2）“移动”记录。对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：“比较”的次数：“移动”的次数：

最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：“移动”的次数：

总的说来，直接插入排序所需进行关键字间的比较次数和记录移动的次数均为n2/4，所以直接插入排序的时间复杂度为O(n2)。2(n-1)★折半插入排序排序算法的思想：由于直接插入排序的内循环(从1到i-1)的查找(或说是比较)是在(部分)有序表的环境下进行的，所以内循环用“折半查找法”，比用顺序查找法快。算法描述如下：Procedurebinsort(varr:List;n:Integer);BeginFori:=2tonDo[r[0]:=r[i];l:=1;h:=i-1;whilel<=hDo[m:=(l+high)div2;ifr[0].key<r[m].keythenh:=m-1elsel:=m+1;]Forj:=i-1DownTolDor[j+1]:=r[j];r[l]:=r[0];]End;★表插入排序

为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。例如:算法描述如下：ProcedureLinsertion_Sort(r:List;n:Integer);Beginr[0].key=MAXINT;r[0].next=1;r[1].next=0;Fori:=2tonDo[j:=0;k:=r[0].next;while(r[k].key<=r[i].key)and(k<>0)Do[j:=k;k:=r[k].next;]r[j].next=i;r[i].next=k;{结点i插入在结点j和结点k之间}]End;

从表插入排序的过程可以看出，它的基本操作仍是将一个记录插入到已排序好的有序表中。和直接插入排序相比，不同之处仅是以修改2n次指针值代替移动记录，排序的过程中所需进行的关键字间的比较次数相同。因此，表插入排序的时间复杂性仍是O(n2)。另一方面，表插入排序的结果只是求得了一个有序链表，则只能对它进行顺序查找，不能进行随机查找，为了能应用有序表的折半查找，需对记录进行重新排列。重排记录的做法是：顺序扫描有序链表，将链表中第i个结点移动至数组的第i个分量中。它的做法是：若第i个最小关键字的结点是数组中下标为p且p>i的分量，则互换r[i]和r[p]，且令r[i]中指针域的值改为p;由于此时数组中所有小于i的分量已是到位的记录，则当p<i时，应顺链表继续查找到p>=i时为止。算法描述如下：ProcedureArrange(varr:stlisttp);{本算法根据r[0..n]中个分量指针域的值调整r[1..n]中记录，使数组中各分量中的记录按关键字非递减有序顺序排列}Begini:=1;p:=r[0].next;whilei<=n-1Do[whilep<iDop:=r[i].next;{p指示第i个结点在当前数组中的位置}q:=r[p].next;ifp<>ithen[t:=r[p];r[p]:=r[i];r[i]:=t;r[i].next:=p;]{交换记录并保持指向r[p]中记录的指针}i:=i+1;p:=q;]End;★冒泡排序排序算法的思想：比较k1和k2,如果这些关键字的值不符合排序顺序,就交换k1和k2；然后对记录k2和k3,k3和k4等等进行相同的工作。直到kn-1和kn为止,到此得到一个最大(或最小)关键字值存在kn的位置上(通常将此过程叫做一趟)。重复这个过程,就得到在位置kn-1,kn-2等处的适当记录,使得所有记录最终被排好序。

7443347344837773888899999例如:将5个记录的关键字7,4,8,3,9进行冒泡排序。排序后k1≤k2≤…≤kn(n=5)。①②③④

因为到第四趟就没有交换的偶对了,所以整个排序结束。算法描述如下ProcedureBubble_sort(varr:List;n:Integer);BeginForm:=1tonDoread(r[m]);k:=n;Repeatall:=True;Form:=1tok-1Do[i:=m+1;ifr[m]>r[i]then[max:=r[m];r[m]:=r[i];r[i]:=max;all:=false]]k:=k-1;Until(all=True)or(k=1);End;冒泡排序的结束条件为：最后一趟没有进行“交换”。冒泡排序是一种稳定的排序算法。时间分析:最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡“比较”的次数：“移动”的次数：n-10

最坏的情况（关键字在记录序列中逆序有序）：需进行

n-1趟起泡“比较”的次数：“移动”的次数：

★希尔排序基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。即：将记录序列分成若干子序列，每个子序列分别进行插入排序,待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。假设将n个记录分成d个子序列，则这d个子序列分别为：{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}

…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。例如：

第二趟希尔排序，设增量d=3

第三趟希尔排序，设增量d=1希尔排序的算法描述如下:ProcedureShellInsert(r:List;d:Integer);{本算法对直接插入算法作了以下修改：

1.前后记录位置的增量是d，而不是1；

2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。}BeginFori:=d+1tonDoIf(r[i].key<r[i-d].key){需将R[i]插入有序增量子表}then[r[0]=r[i];{暂存在R[0]}j:=i-d;while(j>0)and(r[0].key<r[j].key)Do[r[j+d]=r[j];{记录后移，查找插入位置}j:=j-d;]r[j+d]=r[0];{插入}]End;ProcedureShell_sort(r:List,dlta:ArrayofInteger;t:Integer);Begin{按增量序列dlta[0..t-1]对顺序表L作希尔排序。}Fork=0totDoShellInsert(r,dlta[k]);End;

先取定一个两项之间的距离d1(≤n,其中n为整个表的长度),反复比较每两个相距d1的项,直到以d1为距离划分的组排序好为止(至此一趟排序完成),然后取d2<d1,再继续以d2为距离反复比较每两个相距为d2的项,…,依此类推.取每个di+1<di,直到dt=1为止。例如,假设文件中8个记录的关键字,我们不采用顺序比较,而是先从第一个关键字开始每隔4个关键字进行比较;同理第二个也从隔4个关键字进行比较,第三个…,第四个…,依次做下去.题中选d1=4,从小到大排序:初始d1=44655134294170570

第一趟后结果4617054294551370

第二趟后结果d2=20517134246559470

0513174246557094

第三趟后结果d3=155与1713与0546与0594与1346与1313,46分别交换两次

13与1794与70算法描述如下：ProcedureShell_sort(varr:List;n:Integer;all:Boolean);BeginFori:=1tonDoRead(r[i]);d:=n;{增量初值}whiled>1Do[d:=ddiv2;Repeatall:=True;Fori:=1ton-ddo[j:=i+d;ifr[i]>r[j]then[max:=r[i];r[i]:=r[j];r[j]:=max;all:=false;]]Untilall]Fori:=1tonDoWrite(r[i]);End;★选择排序基本思想：首先在n个记录中选择一个具有最小或最大关键字的记录，将选出的记录与记录集合中的第一个记录交换位置。然后在r[2]至r[n]中选择一个最小或最大的值与r[2]交换位置，…，依此类推，直至r[n-1]和r[n]比较完毕。ProcedureSelect_sort(varr:List;n:Integer);BeginFori:=1ton-1Do[m:=i;Forj:=i+1tonDoIfr[j].key<r[m].keythenm:=j;Ifm<>ithen[x:=r[i];r[i]:=r[m];r[m]:=x;]]End;算法的复杂性分析：当选则第一个最小值时需进行n-1次比较，选第二个最小值时需进行n-2次比较，…，选n-1个最小值时需进行n-(n-1)次比较，所以总的比较次数为(n-1)+(n-2)+…+2+1=n(n-1)/2故排序n个记录需要时间为O(n2)。由于执行一次交换，需三次移动记录，最多交换n-1次，故最多移动次数为3(n-1)★堆排序堆是满足下列性质的数列{R1,R2,…，Rn}：或若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左、右子树不空时，根结点的值小于(或大于)左、右子树根结点的值。968327381109下列两个序列为堆，对应的完全二叉树如下图{96，83，27，38，11，09}{12，36，24，85，47，30，53，91}1236248547305391建堆的过程：首先将一个关键字集合用完全二叉树的形式排列;

如给定关键字集合为{46,55,13,42,94,17,05,70}组成的完全二叉树如下：46551342941705702.开始建堆：采用筛选法，逐步将大的关键字筛到堆底。筛选法的思想是这样的：假设集合r有m个结点，从某个结点i(第一次

i=[m/2])开始筛选，先看第i个结点的左右子树，设第i个结点的左子树为kj

，右子树为kj+1

，若kj

<

kj+1则沿左分支筛。将ki与

kj

进行比较，若ki>

kj则对调，小的上来大的下去。然后kj作为新的根结点，在对新的根结点的左右子树进行判断，重复上述过程，直到某个结点的左或右子树根结点的下标大于m为止。第一次调用筛选法：m=8,i=[m/2]=4,从i=4开始，看k4的左右子树，仅有左子树，因此42与70比较，42<70，所以不变。j=i*2=8,i=j，再向下看，此时的i无左右子树,所以返回，如右图所示。4655134294170570{46,55,13,42,94,17,05,70}第二次调用筛选法：i=3,k3=13,13的左右子树为17和05，因17<05,故沿右子树比较，13>05,进行对调，此时13无左右子树，所以返回。4655054294171370{46,55,05,42,94,17,13,70}第三次调用筛选法：i=2,k2=55,因为42<94，所以沿左子树筛选，42<55,进行对调，此时55还有左子树70，因55<70，所以不变，再向下70无左右子树，所以返回，此时二叉树如右图所示。4642055594171370{46,42,05,55,94,17,13,70}第四次调用筛选法：i=1,k1=46,因为05<42，所以沿右子树筛选，05<46,进行对调，此时46还有左右子树17,13，因13<17，所以再沿右子树筛选，13<46,所以对调，46无左右子树，所以返回，此时二叉树如右图所示。0542135594174670{05,42,13,55,94,17,46,70}建堆的算法描述如下：ProcedureSift(varr:List;k,m:Integer);{对m个结点的集合r从某个结点i=k开始筛选，如果r[j]>r[j+1](j=2*i),则沿右分支筛选，否则沿左分支筛选}Begini:=k;j:=2*i;x:=r[i];whilej<=mDo[If(j<m)and(r[j].key>r[j+1].key)thenj:=j+1;{沿右筛}Ifx.key>r[j].keythen[r[i]:=r[j],i:=j;j:=2*i;]{关键字对调，在准备与下一层比较}elsej:=m+1;{强制跳出while循环|}]r[i]:=x;{将x放到适当的位置上}End;堆排序的过程：用拔尖的方法将对顶输出，把最后一个元素送到树根上，然后从i=1开始，调用筛选算法重新建堆，再将堆顶输出将最后一个送到树根，再重新建堆，如此反复，直到得到最后全部排序好的关键字序列。算法描述如下：ProcedureHeap_sort(varr:List;n:Integer);BeginFork:=ndiv2DownTo1DoCallSift(r,k,n);{从第n/2开始进行筛选建初始堆}Fork:=nDownTo2Do[t:=r[k];r[k]:=r[1];r[1]:=t;Write(r[k]);CallSift(r,1,k-1);]Write(r[1]);End;以上面建的堆为例,说明重建堆的执行过程。输出0570r[1]0542135594174670704213559417460513421755947046重建堆输出1346r[1]4642175594701305重建堆051742465594701305输出1770r[1]7042465594171305重建堆4255467094171305输出4294r[1]9455467042171305重建堆4655947042171305输出4670r[1]7055944642171305重建堆5570944642171305输出5594r[1]9470554642171305重建堆7094554642171305输出7094r[1]9470554642171305退出K循环打印949470554642171305堆排序的时间复杂度分析：对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1);对n个关键字，建成深度为

的堆，所需进行的关键字比较的次数至多为4n;调整“堆顶”n-1次，总共进行的关键字比较的次数不超过

因此，堆排序的时间复杂度为O(nlogn)共n-2项相加★快速排序快速排序又称分划交换排序，设输入文件有n个记录R1,R2,…,Rn,它们对应的关键字是k1,k2,…,kn，该方法先取文件中任一记录K(通常取第一个记录)，然后用K从两头到中间进行比较/交换，就能形成一个分划：凡是小于等于K的被移到左边，凡是大于K的被移到右边。例:初始关键字[4655134294051770]将46x第一次交换后[17551342940570]ijji第二次交换后[17134294055570]ji第三次交换后[17051342945570]ji第四次交换后[1705134246945570]ji快速排序步骤：1.选定R1为起点，且将R1送x；2.从最末项Rp开始起指针j倒向前找到第一个kj<x.key或

i≥j时，则判i<j?是Rj送Ri，i:=i+1；3.从Ri项起指针i向前扫描，找到第一个ki>x.key或

i≥j时，则判i<j?是Ri送Rj，

j:=j-1；4.上述过程进行到i=j时停止，将x送Ri，同时i:=i+1；

j:=j-1,即x在正确位置上，并分F为R1和R1两个子集合；5.重复调用上述过程，直到将整个集合排序好为止。快速排序的算法如下：ProcedureQuick_sort(varr:List;l,p:integer);Begini:=l;j:=p;x:=r[i];Repeatwhile(r[j].key>=x.key)and(j>i)Doj:=j-1;Ifi<jthen[r[i]:=r[j];i:=i+1;while(r[i].key<=x.key)and(i<j)Doi:=i+1;ifi<jthen[r[j]:=r[i];j:=j-1;]]Untili=j;r[i]:=x;i:=i+1;j:=j-1;ifl<jthenQuick_sort(r,l,j);ifi<pthenQuick_sort(r,i,p);End;快速排序是目前内部排序中最快的方法。若关键字的分布式均匀的，可以粗略的认为每次划分都把文件分成长度相等的两个文件。令T(n)为分类n个记录所需之比较次数，则有：

T(n)≤cn+2T(n/2)(其中cn为进行一趟排序所需的时间)T(n)≤cn+2(cn/2+2T(n/4))≤2cn+4T(n/4)……≤+nT(2)=O(nlog2n)快速排序算法的性能分析：但如果原来的文件是有次序的，则每个分划操作几乎是无用的，因为它仅使文件的大小减少一个元素，所以这种情况使得快速排序根本不快，它的运行时间接近于冒泡排序，时间复杂性为O(n2)。因此，快速排序偏爱一个无次序的文件。快速排序是一种不稳定的排序算法。归并排序的基本思想是：将两个或两个以上的有序子序列“归并”为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列

归并为一个有序序列。

★归并排序2-路归并排序算法Proceduremerge(l,m,n:Integer;r,r2:List);{表r可以看作是首尾相接的两个文件，将其合并到第三个表r2上第一个文件的下标从１到m，第二个文件的下标从m+1到n}Begini:=l;k:=1;j:=m+1;while(i<=m)and(j<=n)Do[ifr[i].key<=r[j].keythen[r2[k]:=r[i];i:=i+1;]else[r2[k]:=r[j];j:=j+1;]k:=k+1;]ifi>mthenCopy(r,j,n,r2)elseCopy(r,i,m,r2);End;采用2-路归并算法进行排序的思想：先将初始文件分成长度为１的n个子文件并且合并到相邻的子文件。则可以得到大约n/2个长度为2的子文件，重复上述过程，直到仅剩下一个长度为n的文件。

下面的例子显示了这个排序过程(直接合并排序),每个子文件用方括号括起来。初始文件2557483712928633n=8个子文件[25][57][48][37][12][92][86][33]第一趟[2557][3748][1292][3386]

第二趟[25374857][12338692]

第三趟[1225333748578692]设一个辅助数组aux,被用于保存合并x的两个子数组所得的结果。变量size用于控制被合并的子文件的大小。因为每次被合并的两个子文件总是x的两个子数组,所以必须用变量来指出子数组的上下界。ib1和ub1分别表示待合并的第一个子文件的下界与上界,ib2和ub2分别表示待合并的第二个子文件的下界和上界.变量i和j用来指示待合并的两个子文件(即源文件)的元素,变量k用于指示合并得到的目标子文件的元素。归并排序算法：ProcedureMerge_sort(varx:List;n:Integer);Beginsize:=1;whilesize<nDo[ib1:=1;k:=1;whileib1+size<=nDo[ib2:=ib1+size;ub1:=ib2-1;Ifib2+size>nthenub2:=nelseub2:=ib2+size-1;callMerge(ib1,ub1,ib2,x,aux);ib1:=ub2+1;]i:=ib1;whilek<=nDo[aux[k]:=x[i];k:=k+1;i:=i+1;]Fork:=1tonDox[k]:=aux[k];size:=size*2;]End;从上面的算法可以看出size变量的取值不超过log2n个，对size的每一个取值都扫描n个记录,所以归并排序的时间复杂性为O(nlog2n)ProcedureMsort(r,r1:List;s,t:Integer);{将r[s..t]进行2-路归并排序为r1[s..t]}Beginif(s=t)thenr1[s]=r[s]else[m=(s+t)/2;{将r[s..t]平分为r[s..m]和r[m+1..t]}Msort(r,r2,s,m);{递归地将r[s..m]归并为有序的r2[s..m]}Msort(r,r2,m+1,t);{递归地r[m+1..t]归并为有序的r2[m+1..t]}Merge(r2,r1,s,m,t);{将r2[s..m]和r2[m+1..t]归并到r1[s..t]}]End;ProcedureMerge_sort(r:List)BeginMSort(r,r1,1,n);{对记录序列r[1..n]作2-路归并排序}End;递归算法描述如下：★基数排序借助“多关键字排序”的思想来实现“单关键字排序”的算法。多关键字的排序假设有n个记录的序列{R1,R2,…，Rn}，每个记录Ri中含有d个关键字(Ki0,Ki1,…,Kid-1),则称上述记录序列对关键字(Ki0,Ki1,…,Kid-1)有序是指：对于序列中任意两个记录Ri和Rj(1≤i<j≤n)都满足下列(词典)有序关系：(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)其中K0被称为“最主”位关键字，Kd-1被称为“最次”位关键字。实现多关键字排序通常有两种作法:最高位优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，…，依次类推，直至最后对最次位关键字排序完成为止。最低位优先LSD法：先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。

例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。LSD的排序过程如下:无序序列3,2,301,2,153,1,202,3,182,1,20对K2排序1,2,152,3,183,1,202,1,203,2,30对K1排序3,1,202,1,201,2,153,2,302,3,18对K0排序1,2,152,1,202,3,183,1,203,2,30链式基数排序

假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。例如：对下列这组关键字

{209,386,768,185,247,606,230,834,539}

首先按其“个位数”取值分别为0,1,…，9“分配”成10组，之后按从0至9的顺序将它们“收集”在一起;然后按其“十位数”取值分别为0,1,…，9“分配”成10组，之后再按从0至9的顺序将它们“收集”在一起;最后按其“百位数”重复一遍上述操作，便可得到这组关键字的有序序列。在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：待排序记录以指针相链，构成一个链表；“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同；3.“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;4.对每个关键字位均重复2)和3)两步。

例如：p→369→367→167→239→237→138→230→139第一次分配得到f[0]→230←r[0]f[7]→367→167→237←r[7]f[8]→138←r[8]f[9]→369→239→139←r[9]第一次收集得到p→230→367→167→237→138→368→239→139第二次分配得到f[3]→230→237→138→239→139←r[3]f[6]→367→167→368←r[6]第二次收集得到p→230→237→138→239→139→367→167→368第三次分配得到f[1]→138→139→167←r[1]f[2]→230→237→239←r[2]f[3]→367→368←r[3]第三次收集之后便得到记录的有序序列p→138→139→167→230→237→239→367→368提醒注意：１．“分配”和“收集”的实际操作仅为修改链表中的指针和设置队列的头、尾指针；２．为查找使用，该链表尚需应用算法Arrange将它调整为有序表。基数排序的算法简单描述如下：数据类型定义如下：Typechtype=cl..crd;{没一位关键字关键字的取值范围}rcdnode=Recordkey:Array[1..d]ofchtype;{关键字}otheritem:anytype;{其它数据项}next:Integer;{指针域}End;

listtp=Array[1..n]ofrcdnode;{静态链表}Arrtp=Array[chtype]ofInteger;{指针数组}ProcedureDistribute(varr:listtp;p,i:Integer;varf,e:arrtp);{静态链表r中的记录按(key[i+1],…,key[d]有序，p指向链表中的第一个记录，本算法按第i位关键字建立子表，同一子表中记录的key[i]相同，f[j]和e[j]分别指向各子表中第一个和最后一个记录，j=cl..crd,f[j]=0表明key[i]=j的子表为空。}BeginForj:=cltocrdDof[j]:=0;{子表初始化为空表}whilep<>0Do[j:=r[p].key[i];Iff[j]=0thenf[j]:=pelser[e[j]].next:=p;e[j]:=p;{将p所指结点插入到第i个子表中}p:=r[p].next;]End;Procedurecollect(varr:listtp;i:Integer;f,r:arrtp;varp:Integer);{本算法按key[i]自小至大将f[j]<>0所指个子表链接成一个链表，

e[j]为相应各子表的尾指针，p为链结后的链表头指针}Beginj:=cl;whilef[j]=0Doj:=succ(j);{找第一个非空子表,succ为求后继的函数}p:=f[j];t:=e[j];whilej<rcdDo[j:=succ(j);while(j<rcd)and(f[j]=0)Doj:=succ(j);{找下一非空子表}Iff[j]<>0then[r[t].next:=f[j];t:=e[j];]{链接两个非空子表}]End;ProcedureRadix_sort(varr:listtp;varp:Integer);{n个记录存放在静态链表的数据域中，执行本算法进行基数排序后链表中的记录按关键字自小至大相链，p指向第一个记录}BeginFori:=1ton-1Dor[i].next:=i+1;r[n].next:=0;p:=1;{初始化链表}Fori:=dDownTo1Do[Distribute(r,p,i,f,e);{第i趟分配}Collect(r,i,f,e,p);{第i趟收集}End;基数排序的性能分析：对于n个记录(每个记录含有d个关键字，每个关键字的取值范围为Rd个值)进行链式基数排序的时间复杂度为O(d(n+rd))，其中每一趟分配的时间复杂度为O(n),每一趟收集的时间复杂度为O(rd),整个排序需进行d趟分配和收集。所需辅助空间为2rd个队列指针，当然由于需用链表做存储结构，则相对于其它以顺序结构存储记录的排序方法而言，还增加了n个指针域的空间。平面上点的圆排序问题：给定单位圆中n个点假设这n个点在单位圆中是均匀分布的，试设计一个O(n)时间的算法对这n个点依其到圆心的距离进行排序。算法设计的思想：将单位圆划分成n个环，ci，i

=1，2，…，n

如下：单位圆c的面积为π

，而圆环ci的面积s(ci)为:因此，圆环ci与单位圆c的面积之比为：由于所给的n个点Pi，i=1,2,…,n在单位圆内均匀分布，每个点落入圆环ci的概率均为，因此，我们可以采用桶排序的思想将n个圆环当作n个桶，设计出对平面上n个点依其到单位圆c的圆心的距离进行排序的算法如下：ProcedureCircular_point_sort;Vari,k:Integer;d:array[0..n]ofreal;B:array[0..n]oflistptr;BeginFori:=0tonDo[B[i]:=Nil;d[i]:=0;]Fori:=1tonDo[d[i]:=Sqrt(x[i]^2+y[i]^2);k:=Upper(n*d[i]);Insert(B,k,i);]Output(B);End;ProcedureInsert(B:array[0..n]oflistptr;k,i:Integer);Varp,q,r:listptr;found:Boolean;j:Integer;Beginnew(r);r↑.index:=i;r↑.next:=nil;p:=B[k];Ifp<>Nilthenj:=p↑.indexelsej:=0;If(p=Nil)or(d[i]<=d[j])then[r↑.next:=p;B[k]:=r;]else[q:=p;p:=p↑.next;found:=false;while(p<>Nil)andnotfoundDo[j:=p↑.index;If(d[i]<d[j])then[r↑.next:=p;q↑.next:=r;found:=True;]q:=p;p:=p↑.next;]Ifnotfoundthenq↑.next:=r;End;

ProcedureOutput(B:array[0..n]oflistptr);Vari,k:Integer;p:listptr;BeginFori:=0tonDo[p:=B[i];while(p<>Nil)Do[k:=p↑.index;print(k);p:=p↑.next;]]End;变长字符串排序问题：在由字母a~z所组成的字符串的一个集合中，各字符串长度之和为n。怎样用O(n)时间将这个集合中所有字符串依字典序进行排序。字符串采用如下存储结构：Store:Array[1..maxsize]ofchar;String=recordaddres,length:Integer;End;A:Array[1..m]ofString;设lmax=max{A[i].length};对1≤i≤lmax,用队列L[i]={j|A[j].length=i,1≤j≤m}存储长度为i的字符串依次对l[i]中的字符串，用基数排序的思想进行排序。算法描述如下：ProcedureString_sort(A:array[1..m]ofString);Vari,j,k:Integer;lmax:Integer;Q:Queue;B:array[1..26]ofQueue;L:array[1..m]ofQueue;Beginlmax:=0;Fori:=1tomdoIfA[i].length>lmaxthenlmax:=A[i].length;