第十章内部排序

1、数学与软件科学学院信息与计算科学专业2006-2007年第1学期数据结构教案-详案-2004级6班第十章 内部排序10-1概述排序(Sorting)：将数据元素的任意序列，重新排列成按关键字有序的序列的过程。其形式化描述如下：假设有n个记录，其序列为，其相应的关键字序列为，则排序是确定的一种排列，使得关键字序列满足以下非递减(或非递增)关系：，即使序列变成。稳定排序与非稳定排序：当排序之前，如果，在排序前，而排序后，仍然在前，则称这种排序为稳定排序。否则，被称为非稳定排序。内部排序与外部排序：排序过程中只涉及到随机存储器的排序过程，被称为内部排序。如果涉及外部存储器交换，则称为外部排序。注：外

2、部排序通常用于大数据记录集合的排序。内部排序的方法分类：(1) 按排序过程的基本思想和技巧分为：插入排序、交换排序、选择排序、归并排序和基数排序等；(2) 按内部排序所需的工作量分为：1) 简单排序(其时间复杂度为)；2) 先进排序法(其时间复杂度为)；3) 基数排序(其时间复杂度为)。排序过程中的主要操作：1) 比较两个关键字的大小；2) 将记录从一个位置移动到另外的位置；待排序记录的存储方式：(1) 存储于连续的存储单元上，记录之间的关系由其地址关系决定(顺序存储结构)；(2) 记录存放在静态链表中，记录之间的关系由链表指针指示(链表排序)；(3) 记录存储在连续的地址单元中，另有向量指示

3、记录之间的关系，这样可以避免移动记录，但增加存储空间为代价(地址排序)。对待排序记录数据类型的基本声明约定：#define MAXSIZE 20 typedef int KeyType;typedef struct KeyType key; InfoType otherinfo; ReType;typedef struct RedType rMAXSIZE+1;/r0闲置或作为哨兵记录int length;/顺序表的表长度 SqList;10-2插入排序10-2-1 直接插入排序(Straight Insertion Sort)排序类型：简单排序。基本思想：将一条新的记录插入到一个有序表中，使

4、新表依然有序。主要技巧：(1) 第i趟直接插入排序的操作方法：在含有i-1个记录的有序序列r1ri-1中插入记录ri，使得序列r1ri有序；(2) 在r0处设置监视哨。算法的主要步骤：(1) 在有序子表中查找插入点位置；(2) 将插入点以后的记录后移一个记录位置；(3) 插入新记录。算法描述：void InsertSort(SqList &L) /对顺序表L作直接插入排序for (i=2;i<L.length;i+) /总共n-1趟if (LT(L.ri.key,L.ri-1.key) /第i个记录比前一个小时，需要插入L.r0=L.ri; /设置哨兵L.ri=L.ri-1; /

5、将L.ri-2L.rj后移一个记录for (j=i-2;LT(L.r0.key,L.rj.key);-j) L.rj+1=L.rj;L.rj+1=L.r0; /在插入位置插入记录L.r0即原来的L.ri/if /注：for()循环退出时执行了-j，所以L.rj+1=L.r0/for/InsertSort排序实例(略)：效率分析：(1) 空间复杂度：辅助空间为一个单元，即L.r0；(2) 时间复杂度：比较次数，移动次数è整个复杂度。10-2-2 其它插入排序从直接插入算法可知：算法的主要操作为比较和移动。因此，算法的改进可以从这两个方面进行。1. 折半查找基本思想：利用子表的有序性进行

6、折半查找，以减少比较次数。主要技巧：设置了low和high两个位置指示器来表征有序表的范围。算法描述：void BInsertSort(SqList &L) /对顺序表L作折半插入排序for (i=2;i<L.length;i+) /总共n-1趟L.r0=L.ri; /暂存待插入元素low=l; high=i-1;while (low<=high) m=(low+high)/2;if (LT(L.r0.key,L.rm.key) high=m-1;else low=m+1; /whilefor (j=i-1;j>=high+1;-j) L.rj+1=L.rj;L.rh

7、igh+1=L.r0; /在插入位置插入记录L.r0即原来的L.ri/for/BInsertSort排序实例(略)：效率分析：增加了两个位置指针low和high，使得比较次数由变成了，但因移动次数为，所以整个算法的时间复杂度为。2. 2-路插入排序基本思想：在折半查找的基础上，为减少移动记录的次数，增加n个记录大小的辅助存储空间d。d用于存放有序子表，并将L.r1存入d1，然后，对余下的元素的插入排序时，分别插入到d1的前面或后面。主要技巧：1) 设置辅助存储空间d存放有序子表；2) 将d看作一个循环向量。为此，设置两个指针first和final，分别指向排序过程中有序序列的第一个记录和最后一

8、个记录在d中的位置。(1) L.r1èd1；(2) if L.ri.key<d1.key，则L.ri插入到d1之前的有序表中；(3) 否则，L.ri插入到d1之后的有序表中。算法描述(略)：(作为课外作业)排序实例：初始关键字：49, 38, 65, 97, 76, 13, 27, 49假定对n个元素进行插入排序，则排序过程中向量d的状态如下：i=1时，final=first=1：(49)i=2时，L.r2.key=38<d1.key成立，因此，插入到d1至前，即：(49) (38)final=1,first=ni=3时，L.r3.key=65)<d1.key不成立

9、，插入到d1之后，即：(49 65) (38)final=2,first=ni=4时，L.r4.key=97<d1.key不成立，插入到d1之后，即：(49 65 97) (38)final=3,first=ni=5时，L.r5.key=76<d1.key不成立，插入到d1之后，即：(49 65 76 97) (38)final=4,first=ni=6时，L.r6.key=13<d1.key成立，插入到d1之前，即：(49 65 76 97) (13 38)final=4,first=n-1i=7时，L.r7.key=27<d1.key成立，插入到d1之前，即：(49

10、 65 76 97) (13 27 38)final=4,first=n-2i=8时，L.r8.key=49<d1.key不成立，插入到d1之后，即：(49 49 65 76 97) (13 27 38)final=4,first=n-3效率分析：其移动记录次数约为。注：当L.r1是最大/最小记录时，2-路排序完全失去其优越性，为什么？3. 表插入排序目标：希望在排序过程中完全不移动记录。基本思想：修改数据存储结构成如下的静态链表结构：#define SIZE 100 /静态链表容量typedef struct RedType rc; int next; SLNode;typedef s

11、truct SLNode rSIZE;int length; SLinkListType;假设数组下标为0的分量表示表头结点，其关键字取最大整数MAXINT。则表插入算法过程可描述如下：1) 将静态数组下标为0和1的分两看作一个循环链表；2) 依次将2到n的分量按关键字值插入到该循环链表中去。排序实例：(如图10-1所示)MAXINT4938659776132749初始状态10-012345678keynext201-i=22310-i=323140-i=4231504-i=56315042-i=663150472-i=7681504723i=8图10-1 表插入排序实例效率分析：表排序不移动

12、记录，而改为修改指针(2n次)，比较次数不变，因此，实践复杂度仍然为。进一步改进：由于是以链表形式存放的，以上算法不能进行折半查找，只能顺序查找。重排算法的基本思想：顺序扫描有序链表，将第i个链结点存入数组的第i个分量即可。重排算法如下：(如教材P269-270)10-2-3 Shell排序排序类型：插入排序。提出原因：对直接排序，当待排序记录序列为正序时，其时间复杂度可提高到。因此，如果能使待排序序列基本有序，则可提高效率。基本思想：将整个待排序记录分割成若干个子序列，并分别对其进行直接插入排序，待整个序列中的记录“基本有序”时，在对全体进行一次直接插入排序。如图10-2所示。主要技巧：子序

13、列分割及其有序化；子序列分割大小的增量思想，直到分割大小为1以便完成最后的排序。4938659776132749初始状态4913图10-3 Shell排序实例第一趟排序过程55043827655549977604第一趟排序结果1327495504493865977627971355387604654949第二趟排序过程第二趟排序结果13044938274955659776第三趟排序结果04132738494955657697Shell排序算法描述：/对顺序表作一趟Shell插入排序，和简单直接插入排序的主要差别：/ 1) 前后记录的增量是dk而不是/ 2) r0只是暂存单元，不是哨兵。当j&l

14、t;=0时找到插入位置void ShellInsert(SqList &L,int dk) for (i=dk+1;i<=L.length;+i) if (LT(L.ri.key,L.ri-dk.key) /需要将L.ri插入到增量子表中时L.r0=L.ri; /暂存L.rifor (j=i-dk;j>0&&LT(L.r0.key,L.rj.key);j-=dk) L.rj+dk=L.rj;L.rj+dk=L.r0;/if/for/ShellInsert/按增量序列dlta0.t-1对顺序表L作Shell排序void ShellSort(SqList &am

15、p;L,int dlta,int t) for (k=0;k<t;k+) ShellInsert(L,dltak); /一趟增量为dltak的插入排序/ShellSort注：Shell排序中的增量问题还无确定的好方法。目前为止的研究结果是：1) 当取时，其时间复杂度为，其中，t为排序趟数，；2) 当N取某个特定范围内的值时，其比较和移动次数约为；3) 当时，可减少到。10-3 快速排序排序类型：交换排序。1. 冒泡排序(Bubble Sort)基本思想：对相邻元素进行两两比较，如果逆序，则交换其值，直到第n-1个记录和第n个记录处理完后，完成一趟“冒泡”过程。经过最多不超过n-1趟，序列

16、将变成正序序列。算法描述：(略)排序实例：(略)效率分析：如果为正序，则只进行一趟排序，如果为逆序则要进行n-1趟，其比较次数为，并作等数量级的移动，因此，其时间复杂度为。2. 快速排序(Quick Sort)对冒泡法的一种改进。基本思想：通过一趟排序，将原序列分割成左右两个部分，其中左部分所有元素比右部分小(或大)。继续直到整个表有序为止。主要技巧：1) 支点(pivot)概念的引入；一趟快速排序过程的算法描述：以支点为中心，将所有关键字小于支点的记录置于支点之前，否则，置于支点之后。即以支点L.ri为中心，将序列L.rs,L.rt分割成两个子序列：L.rs,L.rs+1,L.i-1和L.r

17、i+1,L.ri+2,L.rt。算法实现描述：算法10.6(a)/假设pivotkey为支点关键字，low和high分别记录向后或向前搜索大于pivotkey或小于pivotkey的记录，并进行交换的起始位置。/结束排序的条件：low=high/交换顺序表L中L.rlow.high的记录，使支点记录到达相应位置，并返回其所在/的位置，此时，其前面的记录的关键字值均小于它，而后面的都大于它int Partition(SqList &L,int low,int high) pivotkey=L.rlow.key; /将子表的第一个记录作为支点记录while (low<high) /从

18、表的两端交替地向中间扫描 while (low<high && L.rhigh.key>=pivotkey) -high; /找比支点小的记录L.rlowßàL.rhigh; /交换，比支点小的记录到低端while (low<high && L.rlow.key<=pivotkey) +low; /找比支点大的记录L.rlowßàL.rhigh; /交换，比支点大的记录到高端return low; /返回支点位置(low=high)/Partition改进算法(算法10.6(b)/改进：因为每次交换

19、时对支点的移动是多余的。只需将支点暂存于L.r0中int Partition(SqList &L,int low,int high) L.r0=L.rlow; /将子表的第一个记录作为支点记录pivotkey=L.rlow.key; /支点关键字while (low<high) /从表的两端交替地向中间扫描 while (low<high && L.rhigh.key>=pivotkey) -high; /找比支点小的记录L.rlow=L.rhigh; /移动比支点小的记录到低端while (low<high && L.rlow.

20、key<=pivotkey) +low; /找比支点大的记录L.rhigh=low; /移动比支点大的记录到高端L.rlow=L.r0; /移动支点记录到相应位置return low; /返回支点位置(low=high)/Partition排序实例：(以改进算法为例)4938659776132749初始状态ij图10-3 快速排序实例分析第1次交换后pivotkeyj27386597761349iij27389776136549ij第2次交换后j27381397766549ij第3次交换后i27381376976549j第4次交换后ij2738134976976549完成一趟排序(a)

21、一趟排序过程的处理描述4938659776132749 初始状态一次划分后2738134976976549 分别快速排序1327384965769749651327384949657697(b) 排序的全过程实例快速排序的递归算法实现描述：/算法10.7/对顺序表L中的子序列L.rlowL.rhigh作快速排序void QSort(SqList &L,int low,int high) if (low<high) pivotkey=Partition(L,low,high); /将L.rlow.L.rhigh一分为二QSort(L,Low,pivotloc-1); /对低端子表根

22、据pivotloc进行递归排序QSort(L,pivodloc+1,high); /对高端子表根据pivotloc进行递归排序/QSort效率分析(详细分析见教材P276-277)：快速排序的平均时间为，其中，n为待排序记录个数，k为常数。结论：所有同数量级的此类排序方法中，快速排序常数因子最小。è快速排序是已知排序算法中最好的内部排序方法。10-4 选择排序基本思想：第i趟从n-i+1(i=1,2,n-1)个记录中选一最小或最大者，作为有序序列中的第i个记录。10-4-1 简单选择排序第i趟排序的基本操作：从n-i+1个记录中，通过n-i次比较，选出最小的关键字记录，并和第i个记录

23、交换。其中，。算法过程：令i从1到n-1，进行n-1趟选择操作。算法实现描述(算法10.9)：void SelectSort(SqList &L) /对顺序表L作简单选择排序for (i=1;i<L.length;i+) /下面则第i小的记录，并交换到相应位置j=SelectMinKey(L,i); if (i!=j) L.rißàL.rj;/SelectSort算法复杂度：移动次数最小为0，最大为3(n-1)次。比较次数为n(n-1)/2。è。BAOBAODIAOBAOCHAZHAOCHALIUBAOWANGDIAODIAOYANGXUEWANG图

24、10-4(a) 选拔冠军的比赛过程冠军改进思路：其主要操作是比较，因此，可以考虑如何减少比较次数。尽量利用前面比较过程中得到的信息。改进方法：锦标赛方法。从图10-4(a)-(c)知：8个队员进行比赛，决定冠军需7场比赛；亚军只需两场比赛；季军也只需两场比赛。共11场比赛，而不是像简单选择算法共需7+6+5=18场比赛。结论：如果充分利用前面比较得到的信息，则可以减少比较的总次数。这种排序方法被称为树形排序。10-4-2 树形选择排序DIAOLIUDIAOLIUZHAO#*WANGDIAODIAOYANGXUEWANG图10-4(c) 选拔亚军的比赛过程季军图10-4 锦标赛比赛过程示意图CH

25、ACHADIAOLIUCHAZHAOCHA*WANGDIAODIAOYANGXUEWANG图10-4(b) 选拔亚军的比赛过程亚军树形选择排序(Tree Selection Sort)，又称为锦标赛排序(Tournament Sort)：是一种按锦标赛思想进行的选择排序方法。273849493865272776图10-5(b)选出次小关键字276538769727133849493865272713图10-5(a)选出最小关键字13651338769713基本思想：1) 对n个记录两两比较，然后再在其中个较小者之间两两比较，重复直到选出最小者为止。用n个叶子结点的完全二叉树表示。如图10-5(

26、a)所示。2) 每个非终端结点等于其叶子结点中的最小关键字。则，根结点即最小关键字记录。3) 输出最小者后，将叶子中最小者改为最大，然后从它开始，和其另一兄弟比较，修改到根的路径上的各个节点的关键字，则根变成次小者。4) 重复3)直到所有叶子结点被输出为止。4938494938654976图10-5(c)选出第3小关键字276538769738效率分析：含有n个叶子结点的完全二叉树的深度为，则在树形选择排序中，除最小关键字要进行n-1次比较外，每选择一个次小关键字仅需进行次比较，因此其时间复杂度为。缺点：输出一个关键字后，找下一个次小关键字时，和最大关键字的比较是不必要的。空间复杂度：需要n个

27、辅助空间存放排序结果。由此，J.Willioms提出了堆排序方法，即另一种树形的选择排序。10-4-3 堆排序堆排序(Heap Sort)的目标：只需要一个记录大小的辅助存储空间，且每个待排序的记录也只占一个存储空间。堆的定义：设有n个元素的序列，当且仅当满足如下关系时，称其为堆。或者，其中，堆的存储结构：以一维数组表示。968391382711123624图10-6 堆示例4709538530(a) 堆顶元素最大的堆(b) 堆顶元素最小的堆堆的性质：1) 第一个元素为根结点；2) 任何一个非终端结点的后继结点的值将不大于其父结点的值或不小于其父结点的值；3) 堆顶元素必然是序列中的最大或最小

28、元素；4) 一个堆对应一个完全二叉树结构。例如：图10-6(a)和10-6(b)所示分别为6个元素和8个元素的序列的堆结构。其对应的一维数组的值分别为：96,83,27,38,11,08和12,36,24,84,47,30,53,91。堆排序：建立堆，输出堆，然后重建堆，直到得到原序列的有序序列为止的排序过程。堆的筛选：当堆顶元素被输出之后，用堆的最后一个元素作为新的堆顶元素，然后从堆顶至叶子的调整(成新堆)的过程。方法：将堆看作一个完全二叉树，则最后一个非终端结点是，因此，筛选从此处开始。例如，对无序列49,38,65,97,76,13,27,49，应从第4个元素97开始，直到第一个4938

29、49976576图10-7 堆的重建或筛选实例1327(a) 无序序列树结构4938974965761327(b) 97被筛后的结果4938974913766527(c) 65被筛后的结果4938974913766527(d) 38被筛后的结果1338974949766527(e) 49被筛后的结果注1：筛选的起始位置即，筛选的范围为1-，筛选的方向从到1。注2：当根被筛选后，堆就建立起来了。元素为止，对每个元素检查其跟左、右子树之间的关系，如果满足堆的条件(即比左右子树结点的值小)，则OK，否则，调整，使其满足。(如图10-7所示)输出堆顶元素后，调整堆的过程跟图10-7相似，其主要差别在于

30、n个顶点变成n-1个顶点。其堆的重建过程示意图如图10-8所示。堆调整算法描述：typedef SqList HeapType; /用顺序结构表示/假定H.rs.m中除H.rs外，所有结点的关键字值之间均满足堆的定义/本函数对H.rs进行调整以重建堆，建堆的目标是大顶堆/调整的元素范围为s.mvoid HeapAdjust(HeapType &H,int s,int m) rc=H.rs;for (j=2*s;j<=m;j*=2) /沿key较大的孩子结点向下筛选if (j<m && LT(H.rj.key,H.rj+1.key) +j; /j为较大的记录之

31、下标if (!LT(rc.key,H.rj.key) break; /如果rc.key比H.rj.key大，则已经到位H.rs=H.rj;s=j; /否则，H.rj上移到H.rs处，并记住s的最新位置sH.rs=rc; /原来的H.rs放到其应当在的位置/HeapAdjust堆排序算法实现过程描述：void HeapSort(HeapType &H) /对顺序表H进行堆排序for (i=H.length/2;i>0;i-) /将H.r1.H.length建成一个大顶堆HeapAdjust(H,I,H.length);for (i=H.length;i>1;i-) H.r1&

32、#223;àH.ri; /将堆顶记录和当前子序列的最后一条记录H.ri交换HeapAdjust(H,1,i-1);/HeapSort时间效率分析：堆排序的主要时间耗费在建立初始堆及筛选过程上，假设深度为k，则筛选算法的关键字比较次数<=2(k-1)次，建立n个元素、深度为h的堆共需进行比较<=4n次。N个结点的完全二叉树深度为，调整堆的次数为n-1次，因此，总的比较次数不超过：è堆排序在最坏情况下，时间复杂度为。空间效率上：堆排序只需要一个额外的辅助存储空间。10-5 归并排序归并排序(Merging Sort)：将两个或两个以上的有序表合并成一个新表的排序方法

33、。存储结构：顺序结构或链表结构。初始关键字49 38 65 97 76 13 2738 49 65 97 13 76 2738 49 65 97 13 27 7613 27 38 49 65 76 97一趟归并之后二趟归并之后三趟归并之后图10-8 2-路归并排序示例2-路归并的基本思想：假设初始序列含有n个记录，每个记录被看作一个含有一个元素的有序子序列，子表长度为1。则可两两归并，获得个长度为2或1的有序子表。如此重复，即可得到一个长度为n的有序序列。实例：如图10-8所示。其核心思想是将相邻两个有序序列两两归并成一个新的序列。算法实现描述：/将有序序列SRi.m和SRm+1.n归并为有序

34、序列TRi.nvoid Merge(RcdType SR,RcdType &TR,int i,in m,int n) for (j=m+1,k=i;i<=m&&j<=n;+k) if (LQ(SRi.key,SRj.key) TRk=SRi+;else TRk=SRj+;if (i<=m) TRk.n=SRi.m;if (j<=n) TRk.n=SRj.n;/Merge时间效率分析：需要调用次Merge算法，其中，h为初始子表的长度，n为待排序记录个数。整个归并次数为趟。因此，其时间复杂度为。空间效率分析：需要和待排序记录个数相同大小的辅助存储空

35、间。递归形式的2-路归并算法：/将SRs.t归并为TR1s.tvoid MSort(RcdType SR,RcdType &TR1,int s,int t) if (s=t) TR1s=SRs;else m=(s+t)/2; /将SRs.t平分为SRs.m和SRm+1.tMSort(SR,TR2,s,m); /递归地将SRs.m归并为有序的TR2s.mMSort(SR,TR2,m+1,t);/递归地将SRm+1.t归并为有序的TR2m+1.tMerge(TR2,TR1,s,m,t);/将TR2s.m和TR2m+1.t归并为TR1s.t/MSortvoid MergeSort(SqLis

36、t &L) MSort(L.r,L.r,1,L.length);/MergeSort注：归并排序是一种稳定排序。10-6 基数排序基数排序(Radix Sorting)：借助多关键字排序思想对单逻辑关键字进行排序的方法。10-6-1 多关键字排序例1：扑克排序。第一种排序方法：每张牌有两个关键字：花色、面值。花色为先，面值次之。第二种排序方法：1) 先按不同的面值分成13堆，然后将其按自小至大顺序叠放，如3在2之上，4在3之上；2) 再按花色分成4堆，并将其按自小至大顺序合在一起，如梅花在下，黑心在上。排序结果：以上两种方法得到的结果完全相同。多关键字有序序列：假设有个记录序列，每一记

37、录含有个关键字,该序列对关键字有序即：，下列关系成立：，其中，为主关键字，为最次关键字。多关键字排序方法：1) 从最主关键字开始，将所有相同值的记录合并到一起，然后，对次关键字再排，直到最次关键字排序结束为止。又称为最高位优先法(Most Significant Digit first)；2) 从最次关键字出发，然后是，直到为止。又称为最低位优先法(Least Significant Digit first)。注1：MSD和LSD只规定了按关键字排序的顺序，没有规定具体排序比较方法。注2：MSD排序本质上是逐层分割方法，它将序列分割成若干个子序列，然后，分别对子序列排序。注3：LSD则没有分割

38、子序列，每个关键字都是针对所有元素进行排序。但对，只能用稳定排序。注4：基于LSD的方法可以用“分配”和“收集”的方法实现排序。如例1的方法2。10-6-2 链式基数排序逻辑关键字：由若干个简单关键字复合而成。278109063930589184505269008083e0e1e2e3e4e5e6e7e8e9930063083184505278008109589269f0f1f2f3f4f5f6f7f8f9分配方向收集方向930063083184505278008109589269505008109930063278269083184589505008109930063269278083184

39、589008063083109184269278505589930图10-9 链式基数排序实例(a)(b)(c)(d)(e)(f)008063083109184269278505589930(g)例如：0K999时，可以将其每个位上的10#数字看作一个关键字，则它由组成。其中，分别代表百位、十位和个位上的关键字值。又如：如果K由五个字母组成，则可以看作组成，其中，各个位表示第1、2、3、4、5个位置上的单字母关键字。分配：根据某个位上的关键字值将记录分配到队列RADIX中去的过程，即基数排序的“分配”。收集：将分配后的序列重新组成一新序列的过程，即“收集”。基数排序：指排序过程中，RADIX的

40、取值范围。如10#下的位关键字的取值范围为10，而字母单词时，字母的取值为26，因此，它们的基分别是10和26。链式基数排序：存储结构：以静态链表存储n个待排序记录，并令表头指针指向第一个记录。算法过程：1) 对最低数位关键字(即个位数)进行，将所有记录分配到10个链表队列中去。使每个队列中关键字的个位数相同。(“分配”)2) 改变所有队尾记录指针域，使其指向下一个非空队列的头记录，从而形成新的链表序列。(“收集”)3) 重复1) 和2)，直到关键字的最高位为止。以上过程的实例如图10-9所示。算法实现的数据类型或存储结构定义：#define MAX_NUM_OF_KEY 8 /关键字项数的最

41、大值#define RADIX 10 /关键字中的基数值(10#)#define MAX_SPACE 10000 typedef struct /静态链表的结点类型KeysType keysMAX_NUM_OF_KEY; /关键字数组或序列InfoType otheritems; /其它数据信息int next; /指针 SLCell; typedef struct SLCell rMAX_SPACE; /静态链表的可利用空间，其中，r0为表头结点int keynum; /记录的当前关键字个数int recnum; /静态链表的当前长度 SList;typedef int ArrTypeRAD

42、IX; /指针数组类型一趟分配算法的实现描述：(算法10.15)/静态链表L的r域中记录已按keys0,keysi-1有序/本算法按第i个关键字keysi建立RADIX子表，使同一子表中记录的keysi相同/f0.RADIX-1和e0.RADIX-1分别指向各子表的第一个和最后一个记录void Distribute(SLCell &r,int i,ArrType &f,ArrType &e) for (j=0;j<Radix;+j) fj=0; /各子表初始化为空表for (p=r0.next;p;p=rp.next) j=ord(rp.keysi); /将记录r

43、p的第i个关键字映射到0.RADIX-1范围内if (!fj) fj=p; /如果当前子表为空else rej.next=p; /否则接入表尾上去ej=p;/Distribute一趟收集的算法实现描述：(算法10.16)/本算法按keysi自小至大顺序，将f0.RADIX-1中各个子表链接成一个链表/e0.RADIX-1是各个子表的尾指针表void Collect(SLCell &r,int i,ArrType f,ArrType e)for (j=0;!fj;j=succ(j) ; /找第一个非空子表，其中succ(j)获得j的后继r0.next=fj; t=ej; /r0.next

44、指向第一个非空子表中的第一个结点while (j<RADIX) for (j=succ(j);j<RADIX-1 && !fj; j=succ(j) ; /找下一个非空子表if (fj) rt.next=fj;t=ej; /链接两个非空子表 rt.next=0; /t指向最后一个非空子表中的最后一个结点/Collect链式基数排序的总体控制算法：(算法10.17)：/L是静态链表表示的顺序表/对L作基数排序，使L按升序排列在静态链表L中，其中，L.r0为链表头void RadixSort(SLList &L) for (i=0;i<L.recnum;+

45、i) L.ri.next=i+1; L.rL.recnum.next=0; /将L改造成静态链表for (i=0;i<L.keynum;+i) Distribute(L.r,I,f,e); /第i趟分配Collect(L.r,I,f,e); /第i趟收集/RadixSort基数排序算法的效率：如果基数为r，每条记录有d个关键字，共n条记录，则共需d趟分配与收集过程，在每一趟分配中，要将n条记录分配到各基数链表中去的时间复杂度为，一趟收集的复杂度为，因此，其整体复杂度为。其空间复杂度上，需要2rd个队列指针以及n个指针域空间。10-7 各种内排序方法的比较讨论排序方法平均时间最坏情况辅助存

46、储简单排序快速排序堆排序归并排序基数排序各种内部排序的基本性能情况如左表所示。具体分析如下：(1) 平均时间上：快速排序最好，但最坏情况不如堆排序和归并排序。当n很大时，归并排序比堆快，但辅助存储空间最多。(2) 简单排序包含除Shell排序以外的所有插入排序、冒泡、简单选择排序。(3) 基数排序的时间复杂度也可写成，当记录个数很多二关键字较小的序列的排序。(4) 从稳定性上看，基数排序和简单排序都是稳定排序。快速排序、堆排序、Shell排序等属于不稳定排序，因为它们基于交换操作。注1：各种排序方法在应用过程中，应当根据实际情况的需要，分别选择使用或结合使用。没有哪一种是绝对优势的。比如，有的适合于n小的排序，有的适合于n大的排序；有的适合于辅助空间多的排序，而有的则适合于很少需要辅助