第十章内部排序

1、1第十章第十章 内部排序内部排序 排序排序(sort):(sort):将一组数据元素任意的序列，重新排列成一组按将一组数据元素任意的序列，重新排列成一组按 关键字有序的序列。关键字有序的序列。 稳定与不稳定：稳定与不稳定：一种排序方法，如果排序后具有相同关键字的一种排序方法，如果排序后具有相同关键字的 记录仍维持排序之前的相对次序，则称之为记录仍维持排序之前的相对次序，则称之为稳定稳定 的，否则称为的，否则称为不稳定不稳定的。的。 例如：例如： 排序前为：排序前为： 4949，3838，6565，9797，7676，1313，2727，4949 排序后为：排序后为： 1313，2727，383

2、8，4949，4949，6565，7676，97 97 该排序是稳定的该排序是稳定的 1313，2727，3838，4949，4949，6565，7676，97 97 该排序是不稳定的该排序是不稳定的2内部排序：内部排序：待排序的数据若存储在内存中，在内待排序的数据若存储在内存中，在内存中加以处理的，这种排序方法叫内部排序。存中加以处理的，这种排序方法叫内部排序。外部排序：外部排序：如果在排序过程中，数据的主要部分如果在排序过程中，数据的主要部分存放在外存储器中（如软盘、硬盘、磁带），借存放在外存储器中（如软盘、硬盘、磁带），借助内存进行内、外存数据交换，逐步排列记录之助内存进行内、外存数据交

3、换，逐步排列记录之间的顺序，则称之为外部排序。间的顺序，则称之为外部排序。内部排序可分五类：内部排序可分五类：插入排序、交换排序、选择插入排序、交换排序、选择排序、归并排序和计数（分配）排序。排序、归并排序和计数（分配）排序。10.1 概概 述述3待排序记录的存储方式：待排序记录的存储方式：1）地址连续的一组存储单元（顺序存储），排序时需移动记录）地址连续的一组存储单元（顺序存储），排序时需移动记录2）静态链表，排序时不需移动记录，仅需修改指针）静态链表，排序时不需移动记录，仅需修改指针3）记录存放在地址连续的一组存储单元中，再设一组地址向量，排）记录存放在地址连续的一组存储单元中，再设一组地

4、址向量，排序时不需移动记录，结束后再调整记录的存储位置。序时不需移动记录，结束后再调整记录的存储位置。待排记录的数据类型：待排记录的数据类型： （以第一种方式讨论）（以第一种方式讨论）#define MAXSIZE 20 typedef int KeyType ; typedef struct KeyType key; InfoType otherinfo; RedType; /记录类型记录类型 typedef struct RedType rMAXSIZE+1; /r0闲置或作岗哨闲置或作岗哨 int length; SqList; /表的类型表的类型10.1 概概 述述410.2 插入排序

5、插入排序10.2.1 直接插入排序直接插入排序 直接插入排序：直接插入排序：将一个记录插入到已排好序的有序表中，将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增一的有序表。从而得到一个新的、记录数增一的有序表。 void Insertsort(Sqlist &L) for (i=2; i=L.length; +i) if (LT(L.ri.key, L.ri-1.key) /需将需将L.ri-1插入到有序子表插入到有序子表 L.r0=L.ri; /将将L.ri复制到岗哨复制到岗哨 L.ri=L.ri-1; for(j=i-2; LT(L.r0.key,L.rj.key);

6、 -j ) L.rj+1=L.rj; /记录后移记录后移 L.rj+1=L.r0; /插入到正确位置插入到正确位置 时间复杂度？时间复杂度？510.2.2 其他插入排序其他插入排序1.折半插入排序折半插入排序 上述插入排序的基本操作是在一个有序表中进行查找和插入，查上述插入排序的基本操作是在一个有序表中进行查找和插入，查找可以用折半查找来实现，称之为折半插入排序。找可以用折半查找来实现，称之为折半插入排序。 void BInsertsort(Sqlist &L) for (i=2;i=L.length;+i) L.r0=L.ri; low=1; high=i-1; while (low

7、=high+1;-j ) L.rj+1=L.rj; L.rhigh+1=L.r0; 折半插入排序仅减少了关键字的比较次数，而没有减少移动次数。折半插入排序仅减少了关键字的比较次数，而没有减少移动次数。时间复杂度仍为时间复杂度仍为O( n2 )6 2路插入排序路插入排序 2路插入排序是在折半插入排序的基础上再改进之，其目路插入排序是在折半插入排序的基础上再改进之，其目的是减少排序过程中记录的移动次数，但需要的是减少排序过程中记录的移动次数，但需要n个记录的个记录的辅助空间。辅助空间。 具体方法具体方法：另设一个和：另设一个和L.r同类型的数组同类型的数组d，首先将，首先将L.r1赋值给赋值给d1

8、，并将，并将d1看成是在排好序的序列中处于中间看成是在排好序的序列中处于中间位置的记录，然后从位置的记录，然后从L.r中第二个记录起依次插入到中第二个记录起依次插入到d1之之前或之后的有序序列中。先将待插记录的关键字和前或之后的有序序列中。先将待插记录的关键字和d1的的关键字进行比较，若关键字进行比较，若L.ri.keyi的分量，则互换的分量，则互换SL.ri和和SL.rp，且令，且令SL.ri中指针域的中指针域的值改为值改为p，由于此时数组中所有小于，由于此时数组中所有小于i的分量中已是的分量中已是“到位到位”的记录，则当的记录，则当p=i为止。为止。 void Arrange(SLinkL

9、istType &SL) p=SL.r0.next; for (i=1;iSL.length;+i) while (pi) p=SL.rp.next; q=SL.rp.next; if (p!=i) SL.rpSL.ri; SL.ri.next=p; p=q; 表插入排表插入排序序910.2.3 希尔排序希尔排序 希尔排序希尔排序（shells method) shells method) 又称又称“缩小增量排序缩小增量排序”。 基本思想：基本思想：先将整个待排记录序列分割成若干子序列先将整个待排记录序列分割成若干子序列, ,在每个子序列内分别进行直接插入排序，待整个序列在每个子序列内

10、分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插中的记录基本有序时，再对全体记录进行一次直接插入排序。入排序。 注意注意: :子序列的划分不是简单地子序列的划分不是简单地“逐段分割逐段分割”, ,而是将相而是将相距某个距某个“增量增量”的记录组成一个子序列。的记录组成一个子序列。“增量增量”一一次比一次小，直到增量为次比一次小，直到增量为1 1。10 void ShellInsert(SqList &L, int dk) /对对L作一趟希尔插入排序，作一趟希尔插入排序，dk为增量为增量 for (i=dk+1; i0&LT(L.r0.key,L.r

11、j.key) ; j=j-dk) L.rj+dk=L.rj; L.rj+dk=L.r0; Void ShellSort(SqList &L, int dlta, int t) /增量序列增量序列dlta0.t-1 for (k=0; kt; +k) ShellInsert(L, dltak); 10.2.3 希尔排序希尔排序1110. 3 交换排序交换排序 借助借助“交换交换”进行的排序进行的排序 主要包括：主要包括：起泡排序和快速排序。起泡排序和快速排序。 起泡排序起泡排序：首先将第一个记录的关键字和第二个记录：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个

12、记录交换之，的关键字进行比较，若为逆序，则将两个记录交换之，然后比较地二个记录和第三个记录的关键字，依次类然后比较地二个记录和第三个记录的关键字，依次类推，直至第推，直至第n-1个记录和第个记录和第n记录的关键字进行过比较记录的关键字进行过比较为止。上述过程称第一趟气泡排序，其结果时最大的为止。上述过程称第一趟气泡排序，其结果时最大的记录被放到了最后的位置上。然后再进行第二趟、第记录被放到了最后的位置上。然后再进行第二趟、第三趟三趟 时间复杂度：时间复杂度：O( n2 )12 快速排序（快速排序（Quick Sort）基本思想）基本思想：通过一趟排序将待：通过一趟排序将待排记录分割成独立的两部

13、分，其中一部分记录的关键字均比排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序。进行排序，以达到整个序列有序。 选取一记录作为选取一记录作为枢轴枢轴（pivot） （一般为第一个记录）（一般为第一个记录）,将待排记录分成两部分。比枢轴小的放在其前面，反之放在将待排记录分成两部分。比枢轴小的放在其前面，反之放在其后面。其后面。 一趟快速排序一趟快速排序的具体做法：附设两个指针的具体做法：附设两个指针i和和j，它们的，它们的初值分别为初值分别为low和和high，

14、设枢轴记录的关键字为，设枢轴记录的关键字为pivotkey，则首先从则首先从j所指位置起向前搜索找到第一个关键字小于所指位置起向前搜索找到第一个关键字小于pivotkey的记录移到的记录移到i的位置上，然后从的位置上，然后从i所指位置起向后搜索，所指位置起向后搜索，找到第一个关键字大于找到第一个关键字大于pivotkey的记录移到的记录移到j的位置上，重复的位置上，重复这两步直到这两步直到i=j为止。为止。10. 3 交换排序交换排序-快速排序快速排序13 int Partition(SqList &L, int low, int high) /一趟快速排序一趟快速排序 i=low;

15、j=high; L.r0=L.ri; pivotkey=L.ri.key; while (ij) while (i=pivotkey) -j; L.ri=L.rj; /比枢轴记录小的记录移到底端比枢轴记录小的记录移到底端 while (ij & L.ri.key=pivotkey) +i; L.rj=L.ri; /比枢轴记录大的记录移到高端比枢轴记录大的记录移到高端 L.ri=L.r0; return i; /返回返回枢轴枢轴的位置的位置 10. 3 交换排序交换排序-快速排序的算法快速排序的算法14 void Qsort(SqList &L, int low, int hig

16、h) /对顺序表对顺序表L中的子序列中的子序列L.rlow.high 作快速排序作快速排序 if (lowhigh)/长度大于长度大于 pivotloc=Partition(L,low,high); Qsort(L,low,pivotloc-1); Qsort(L,pivotloc+1,high); void QuickSort(SqList &L) /对顺序表对顺序表L作快速排序作快速排序 Qsort(L, 1, L.length); 10. 3 交换排序交换排序-快速排序的算法快速排序的算法1510.4 选择排序选择排序 选择排序：选择排序：每一趟在每一趟在n-i+1(i=1,2,

17、3,n-1)个记录中选择关键个记录中选择关键字最小的记录作为有序序列中第字最小的记录作为有序序列中第i个记录。个记录。 10.4.1 简单选择排序简单选择排序 一趟简单选择排序一趟简单选择排序：通过通过n-i次关键字间的比较，从次关键字间的比较，从n-i+1个记个记录中选出关键字最小的记录，并和第录中选出关键字最小的记录，并和第i个记录交换之。个记录交换之。 void SelectSort(SqList &L) /对顺序表作简单选择排序对顺序表作简单选择排序 for (i=1; iL.length; +i) j=SelectMinKey(L,i);/在在L.ri.L.length中选最

18、小的记录中选最小的记录,位置位置为为j if (i!=j) L.riL.rj; /两记录交换两记录交换 16举例：举例： 30,26,28,35,47,18,32,16,45,37 第一趟第一趟: 16,26,28,35,47,18,32,30,45,37 /j=8,L.r1L.r8第二趟第二趟: 16,18,28,35,47,26,32,30,45,37 /j=6,L.r2L.r6第三趟第三趟: 16,18,26,35,47,28,32,30,45,37 /j=6,L.r3L.r6第四趟第四趟: 16,18,26,28,47,35,32,30,45,37 /j=6,L.r4L.r6第五趟第五

19、趟: 16,18,26,28,30,35,32,47,45,37 /j=8,L.r5L.r8第六趟第六趟: 16,18,26,28,30,32,35,47,45,37 /j=7,L.r6L.r7第七趟第七趟: 16,18,26,28,30,32,35,47,45,37 /j=7,不需交换不需交换第八趟第八趟: 16,18,26,28,30,32,35,37,45,47 /j=10,L.r8L.r10第九趟第九趟: 16,18,26,28,30,32,35,37,45,47 /j=9,不需交换不需交换1710.4.2 树形选择排序树形选择排序 树形选择排序又称锦标赛排序树形选择排序又称锦标赛排序

20、，首先对，首先对n个个记录的关键字进行两两比较，然后在其中记录的关键字进行两两比较，然后在其中 n/2 个个较小者之间再进行两两比较，如此重复，直至选较小者之间再进行两两比较，如此重复，直至选出关键字最小的记录为止。出关键字最小的记录为止。 这个过程可用一棵有这个过程可用一棵有n个叶子结点的个叶子结点的完全二完全二叉树叉树表示例如表示例如P.2791810.4.3 堆排序堆排序 堆的定义堆的定义：n n个元素的序列个元素的序列 kk1 1,k ,k2 2,.,k,.,kn n 当且仅当且仅当满足下列关系时，称为堆。当满足下列关系时，称为堆。 或或 若将此序列对应的一维数组看成是一个若将此序列对

21、应的一维数组看成是一个完全完全二叉树二叉树，则堆顶元素必为最大值（或最小值）。，则堆顶元素必为最大值（或最小值）。 iikk212 iikkiikk212 iikk19序列：序列：96,83,27,38,11,20 序列：序列：12,36,24,85,47,30,53,91 对应的完全二叉树对应的完全二叉树 对应的完全二叉树对应的完全二叉树 （大根堆）（大根堆） （小根堆）（小根堆） 在大根堆中，将堆顶和最后一个记录交换，即得第一趟在大根堆中，将堆顶和最后一个记录交换，即得第一趟的结果；再使剩余的结果；再使剩余n-1个元素的序列重又建成一个堆，则得个元素的序列重又建成一个堆，则得到到n个元素的

22、次大值。如此反复执行，便能得到一个有序序个元素的次大值。如此反复执行，便能得到一个有序序列，这个过程称为列，这个过程称为堆排序堆排序。963827832011915330478524361210.4.3 堆排序堆排序20 实现堆排序需要解决两个问题：实现堆排序需要解决两个问题： 1）如何由一个无序序列初次建成一个堆？）如何由一个无序序列初次建成一个堆？ 2）如何在一趟排序之后，调整剩余元素成）如何在一趟排序之后，调整剩余元素成为为 一个新的堆一个新的堆？10.4.3 堆排序堆排序21 问题问题2解决方法解决方法：输出堆顶元素之后，用堆中：输出堆顶元素之后，用堆中最后一个元素替代堆顶，此时根结点

23、的左右子最后一个元素替代堆顶，此时根结点的左右子树均为堆，则需自上而下进行调整即可。（自树均为堆，则需自上而下进行调整即可。（自堆顶至叶子的调整过程称为筛选）。堆顶至叶子的调整过程称为筛选）。 问题问题1解决方法：解决方法：一个无序序列建堆的过程就一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第个完全二叉树，则最后一个非终端结点是第 n/2 个元素，由此筛选只需从第个元素，由此筛选只需从第 n/2 个元素个元素开始，直到根结点。开始，直到根结点。 10.4.3 堆排序堆排序22 typedef SqL

24、ist HeapType; void HeapAdjust(HeapType &H, int s, int m) /由由H.rs.m中记录的关键字组成的完全二叉树，根结点中记录的关键字组成的完全二叉树，根结点 /的左、右子树均已是堆，现对其进行调整，使得的左、右子树均已是堆，现对其进行调整，使得H.rs.m /成为一个大根堆成为一个大根堆 rc=H.rs; for (j=2*s; j=m; j=j*2) if (j0; -i) HeapAdjust(H,i, H.length); for(i=H.length; i1;-i) H.r1H.ri; HeapAdjust(H,1,i-1);

25、 堆排序最坏情况下，时间复杂度为堆排序最坏情况下，时间复杂度为O(nlog2n)10.4.3 堆排序堆排序24 上次课要点：上次课要点：l选择排序的概念选择排序的概念l简单选择排序的思想和算法简单选择排序的思想和算法l堆排序堆排序(重点重点) 1)堆排序的核心算法堆排序的核心算法:筛选筛选 2)堆排序算法堆排序算法 3)堆排序算法时间复杂度堆排序算法时间复杂度O(nlog2n)本次课将要讲的主要内容本次课将要讲的主要内容:l归并排序的概念归并排序的概念l归并排序的核心操作归并排序的核心操作:一趟归并一趟归并(Merge)l归并排序的非递归实现归并排序的非递归实现l归并排序的递归实现归并排序的递

26、归实现2510.5 归并排序归并排序 归并排序（归并排序（merge sort）：将两个或两：将两个或两个以上的个以上的有序表有序表组合成一个新的有序表。组合成一个新的有序表。 假设初始序列含有假设初始序列含有n个记录，则可看成是个记录，则可看成是n个有序的子序列，每个子序列的长度为个有序的子序列，每个子序列的长度为1，然，然后两两归并，得到后两两归并，得到 n/2 个长度为个长度为2或或1的有序的有序子序列；再两两归并，如此重复，直到得到一子序列；再两两归并，如此重复，直到得到一个长度为个长度为n的有序序列为止，该排序方法称为的有序序列为止，该排序方法称为2-路归并排序。路归并排序。262-

27、路归并排序示例路归并排序示例 初始 6 14 12 10 2 18 16 8 第一趟 6 14 10 12 2 18 8 16 第二趟 6 10 12 14 2 8 16 18 第三趟 2 6 8 10 12 14 16 18 27 2路归并排序中的核心操作路归并排序中的核心操作是将一维数组中是将一维数组中前后相邻前后相邻的两的两个有序序列个有序序列归并归并成一个有序序列。算法如下：成一个有序序列。算法如下： void Merge(Rcdtype SR , Rcdtype &TR ,int i, int m, int n) /将有序的将有序的SRi.m和和SRm+1.n归并为有序的归并

28、为有序的TRi.n int j, k; 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) /将剩余的将剩余的SRi.m复制到复制到TR TRk.n=SRi.m; if (j=n) /将剩余的将剩余的SRj.n复制到复制到TR TRk.n=SRj.n; 10.5 归并排序归并排序-核心操作核心操作2810.5 归并排序归并排序-非递归实现非递归实现 归并排序归并排序算法思想算法思想： 1）开始时先将）开始时先将n个记录看成个记录看成n个长度为个长度为1的已排好的

29、已排好 序的表；序的表； 2）将相邻的表两两合并，得到长度为）将相邻的表两两合并，得到长度为2的（的（n/2） 个有序表；个有序表； 3）进一步再将相邻表两两合并，得到长度为）进一步再将相邻表两两合并，得到长度为4的的 （n/4）个有序表；）个有序表； 如此重复下去，直至所有记录均合并到一个如此重复下去，直至所有记录均合并到一个 长度为长度为n的有序表为止，就完成了排序。的有序表为止，就完成了排序。2910.5 归并排序归并排序-非递归实现非递归实现mergepass(Rcdtype R ,Rcdtype &R1 , int length) /对对R做一趟归并做一趟归并,结果放在结果放

30、在R1中中,子文件长度为子文件长度为length int i=0, j; / i 指向第一对子文件的起点指向第一对子文件的起点 while (i+2*length-1n) /归并长度为归并长度为length的两个相邻子文件的两个相邻子文件 merge(R, R1, i, i+length-1, i+2*length-1); i=i+2*length; /指向下一对子文件起始点指向下一对子文件起始点 if (i+length-1n-1) /剩下最后两个子文件剩下最后两个子文件,其中一个长度小于其中一个长度小于length merge(R, R1, i, i+length-1, n-1); els

31、e for (j=i; jn; j+) R1j=Rj; /最后一个文件复制到最后一个文件复制到R1中中 3010.5 归并排序归并排序-非递归实现非递归实现Void Mergesort(rcdtype R ) /对对R进行二路归并排序进行二路归并排序,结果仍在结果仍在R中中 int length=1; while (length=n) mergepass(R,R1,length); /一趟归并，结果在一趟归并，结果在R1中中 length=2*length; mergepass(R1,R,length); /再次归并再次归并,结果在结果在R中中 length=2*length; 3110.5

32、归并排序归并排序-递归实现递归实现请同学们思考：请同学们思考： 1、递归求解的三个条件？、递归求解的三个条件？ 2、归并排序中如何体现这三个条件？、归并排序中如何体现这三个条件？3210.5 归并排序归并排序-递归实现递归实现void Msort(Rcdtype SR ,Rcdtype &TR1 , int s, int t) /将将SRs.t归并排序为归并排序为TR1s.t if (s= =t) TR1s=SRs; /递归出口递归出口 else m=(s+t)/2; /将将SRs.t平分为平分为SRs.m和和SRm+1.t Msort(SR, TR2,s,m); Msort(SR,T

33、R2,m+1,t); Merge(TR2,TR1,s,m,t); /将将TR2s.m和和TR2m+1.t /归并到归并到TR1s.t void MergeSort(SqList &L) /对表对表L作归并排序作归并排序 Msort(L.r, L.r, 1, L.length); 3310.5 归并排序归并排序-算法分析算法分析l 时间复杂度：时间复杂度：第第 i 趟归并后，有序子文件长度为趟归并后，有序子文件长度为2i，因，因此此,对有对有n个记录的文件排序，必须做个记录的文件排序，必须做 趟归并，趟归并，每趟归并所花的时间是每趟归并所花的时间是O(n);因此二路归并排序的时间复因此二

34、路归并排序的时间复杂性为杂性为O(nlog2n )。l 空间复杂度：空间复杂度：归并排序需要和待排记录数量的归并排序需要和待排记录数量的辅辅 助空间，即空间复杂度为助空间，即空间复杂度为O(n)l 稳定性问题：稳定性问题：归并排序是归并排序是稳定的稳定的。 思考：用递归实现的算法如何改进？思考：用递归实现的算法如何改进？nlog23410.6 基数排序基数排序本小节主要内容本小节主要内容:l基数排序与其他排序的不同之处基数排序与其他排序的不同之处l多关键字排序的两种方法多关键字排序的两种方法l链式基数排序的两种主要操作链式基数排序的两种主要操作:分配和收集分配和收集l链式基数排序的算法链式基数

35、排序的算法3510.6 基数排序基数排序 基数排序与其他排序的不同之处基数排序与其他排序的不同之处: 前面讲到的四大类排序（插入、交换、选择、前面讲到的四大类排序（插入、交换、选择、归并）主要通过关键字间的归并）主要通过关键字间的比较和移动比较和移动这两种操这两种操作，而基数排序不需要进行关键字间的比较。作，而基数排序不需要进行关键字间的比较。基基数排序数排序(Radix Sorting) 是借助多关键字排序的思是借助多关键字排序的思想对单关键字进行的排序方法。想对单关键字进行的排序方法。3610.6 基数排序基数排序-概念概念l多关键字排序方法有两种：多关键字排序方法有两种： (1)最高位优

36、先最高位优先(Most Significant Digit first )MSD (2)最低位优先最低位优先(Least Significant Digit first )LSDl 最低位优先最低位优先(Least Significant Digit first )LSD 设：每个记录中含有设：每个记录中含有d个关键字个关键字(K0,K1,K2,Kd-1) K0 称为最主位关键字，称为最主位关键字， Kd-1 称为最次位关键字。称为最次位关键字。 最低位优先最低位优先LSD是从最次位关键字是从最次位关键字Kd-1起进行排序起进行排序,然后再对高一位的关键字然后再对高一位的关键字Kd-2进行排序

37、进行排序,依次重复依次重复,直到对直到对K0位进行排序后便成为一个有序序列。位进行排序后便成为一个有序序列。3710.6 基数排序基数排序-链式基数排序链式基数排序链式基数排序：链式基数排序：用链表作存储结构，并借助用链表作存储结构，并借助分配和收集分配和收集两种两种操作对单关键字进行排序的一种方法。操作对单关键字进行排序的一种方法。具体方法：具体方法：1. 用静态链表用静态链表存储存储n个待排记录个待排记录,并令表头指针指向第一个记录；并令表头指针指向第一个记录；2. 第一趟分配第一趟分配对最低数位（个位）进行，改变记录的指针将链对最低数位（个位）进行，改变记录的指针将链 表中的记录分配到表

38、中的记录分配到10个链表中个链表中,每个队列中所有记录的关键字每个队列中所有记录的关键字 个位数相等，个位数相等，fi和和ei分别为第分别为第i个队列的头指针和尾指针；个队列的头指针和尾指针； 第一趟收集第一趟收集是改变所有非空队列的队尾记录的指针域，令其是改变所有非空队列的队尾记录的指针域，令其 指向下一个非空队列的队头记录，重新将指向下一个非空队列的队头记录，重新将10个队列中的记录个队列中的记录 链接成一个链表；链接成一个链表；3.第二趟分配，第二趟收集第二趟分配，第二趟收集及第三趟分配和第三趟收集分别对及第三趟分配和第三趟收集分别对 十位数和百位数进行，过程相同。十位数和百位数进行，过

39、程相同。3810.6 基数排序基数排序-数据结构定义数据结构定义#define MAX_NUM_OF_KEY 8 /关键字项数的最大值关键字项数的最大值#define RADIX 10 /关键字基数关键字基数#define MAX_SPACE 10000 typedef struct KeysType keysMAX_NUM_OF_KEY; /关键字关键字 InfoType otheritems; int next; SLCell; /静态链表的静态链表的结点类型结点类型 typedef struct SLCell rMAX_SPACE; /静态链表的可利用空间，静态链表的可利用空间，r0为头

40、结点为头结点 int keynum; /记录的当前关键字个数记录的当前关键字个数 int recnum; /静态链表的当前长度静态链表的当前长度 SLList; /静态静态链表类型链表类型 typedef int ArrTypeRADIX;39 Void Distribute(SLCell &r, int i, ArrType &f, ArrType &e) /静态链表静态链表L的的r域中记录已按域中记录已按(keys0,keysi-1)有序有序 /本算法按第本算法按第i个关键字个关键字keyi建立建立RADIX个子表，使同一子表个子表，使同一子表 /中记录中记录keyi的相同；的相同；f0.RADIX-1和和e0.RADIX-1分别指分别指 /向各子表中第一个和最后一个记录向各子表中第一个和最后一个记录 int j, p; for (j=0;jRadix; +j) fj=0; /各子表初始化为空表各子表初始化为空表 for (p=r0.next; p; p=rp.next) j=ord(rp.keyi); /将第将第i个关键字映射到个关键字映射到0.RADIX-1 if