第十章排序ppt课件

1、新办公地点：新办公楼计算中心新办公地点：新办公楼计算中心805第十章第十章 内部排序内部排序10.1 排序排序设设 n 个记录的序列为个记录的序列为 R1 , R2 , R3 , . . . , Rn 其相应的关键字序列为其相应的关键字序列为 K1 , K2 , K3 , . . . , Kn 假设规定假设规定 1 , 2 , 3 , . . . , n 的一个陈列的一个陈列 p1 , p2 , p3 , . . . , pn ，使得相应的关键字满足如下非递减关系，使得相应的关键字满足如下非递减关系:Kp Kp Kp . . . Kp123n那么原序列变为一个按关键字有序的序列那么原序列变为一

2、个按关键字有序的序列:Rp , Rp , Rp , . . . , Rp123n 此操作过程称为排序。此操作过程称为排序。 排序分类排序分类 按待排序记录所在位置按待排序记录所在位置 内部排序：待排序记录存放在内存内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进展访问的外部排序：排序过程中需对外存进展访问的排序排序 按排序根据原那么按排序根据原那么 插入排序：直接插入排序、折半插入排序、插入排序：直接插入排序、折半插入排序、希尔排序希尔排序 交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速排序 选择排序：简单项选择择排序、堆排序选择排序：简单项选择择排序、堆排序 归并排序：归

3、并排序：2-2-路归并排序路归并排序 基数排序基数排序 按排序后关键字相等的记录的相对位置按排序后关键字相等的记录的相对位置 稳定排序稳定排序 不稳定排序不稳定排序 按排序所需任务量按排序所需任务量 简单的排序方法：简单的排序方法：T(n)=O(n) 先进的排序方法：先进的排序方法：T(n)=O(logn) 基数排序：基数排序：T(n)=O(d.n) 排序根本操作排序根本操作 比较两个关键字大小比较两个关键字大小 将记录从一个位置挪动到另一个位置将记录从一个位置挪动到另一个位置稳定排序稳定排序 与与 不稳定排序不稳定排序假设假设 Ki = Kj ，且排序前序列中，且排序前序列中 Ri 领先于领

4、先于 Rj ；假设在排序后的序列中假设在排序后的序列中 Ri 仍领先于仍领先于 Rj ，那么称排序方法是，那么称排序方法是稳定的。稳定的。假设在排序后的序列中假设在排序后的序列中 Rj 仍领先于仍领先于 Ri ，那么称排序方法，那么称排序方法是不稳定的。是不稳定的。例，序列例，序列 3 15 8 8 6 9假设排序后得假设排序后得 3 6 8 8 9 15稳定的稳定的假设排序后得假设排序后得 3 6 8 8 9 15不稳定的不稳定的内部排序内部排序 与与 外部排序外部排序内部排序内部排序: 指的是待排序记录存放在计算机随机存储指的是待排序记录存放在计算机随机存储器中进展的排序过程。器中进展的排

5、序过程。外部排序外部排序: 指的是待排序记录的数量很大，以致内存指的是待排序记录的数量很大，以致内存一次不能包容全部记录，在排序过程中尚需对外存进一次不能包容全部记录，在排序过程中尚需对外存进展访问的排序过程。展访问的排序过程。内部排序内部排序按照排序过程中所根据的原那么的不同可以分类按照排序过程中所根据的原那么的不同可以分类为为: 插入排序插入排序 交换排序交换排序(快速排序快速排序) 选择排序选择排序 归并排序归并排序 基数排序基数排序 二叉排序树排序二叉排序树排序10.2 插入排序插入排序插入排序是将当前无序区中最前端的记录插入到有序区插入排序是将当前无序区中最前端的记录插入到有序区中，

6、逐渐扩展有序区，直到一切记录都插入到有序区中，逐渐扩展有序区，直到一切记录都插入到有序区中为止。中为止。 直接插入排序直接插入排序1 1过程：在有序区中进展顺序查找以确定插入的位过程：在有序区中进展顺序查找以确定插入的位置，然后挪动记录腾出空间，以便相应关键字的记录置，然后挪动记录腾出空间，以便相应关键字的记录插入。插入。在有序区的前端在有序区的前端r0r0中设一个监视哨，存放当前要插中设一个监视哨，存放当前要插入的关键字。入的关键字。例，序列例，序列 49 38 65 97 76 13 27 初始，初始，S = 49 ； 38 49 算法描画算法描画:初始，令第初始，令第 1 个元素作为初始

7、有序表；个元素作为初始有序表；依次插入第依次插入第 2 , 3 , , k 个元素构造新的有序表；个元素构造新的有序表；直至最后一个元素；直至最后一个元素； 38 49 65 38 49 65 97 38 49 65 76 97 13 38 49 65 76 97 13 27 38 49 65 76 97 直接插入排序算法主要运用比较和挪动两种操作。直接插入排序算法主要运用比较和挪动两种操作。算法：算法：InsertSort(r,n)InsertSort(r,n) for (i=2;i=n;i+)for (i=2;i=n;i+)r0=ri; j=i-1;r0=ri; j=i-1;while (

8、r0rj)while (r0rj)rj+1=rj;rj+1=rj;j-;j-; rj+1=r0;rj+1=r0; 举例：有序列：举例：有序列：20,6,15,7,320,6,15,7,3，过称为：，过称为：r0r1r2r3r4r5 6 20 6 15 7 3 15 6 20 15 7 3 7 6 15 20 7 3 3 6 7 15 20 3 3 6 7 15 20 算法评价算法评价 时间复杂度时间复杂度 假设待排序记录按关键字从小到大陈列假设待排序记录按关键字从小到大陈列(正序正序) 关键字比较次数：关键字比较次数：112nniY记录挪动次数：记录挪动次数：)1(222nni 假设待排序记录

9、按关键字从大到小陈列假设待排序记录按关键字从大到小陈列(逆序逆序) 关键字比较次数：关键字比较次数：2)1)(2(2nniniY记录挪动次数：记录挪动次数：2)1)(4()1(2nnini 假设待排序记录是随机的，取平均值假设待排序记录是随机的，取平均值 关键字比较次数约为：关键字比较次数约为：42nY记录挪动次数约为：记录挪动次数约为：42nT(n)=O(n) 空间复杂度：空间复杂度：S(n)=O(1)如何改良直接插入排序算法如何改良直接插入排序算法1. 从比较次数改良从比较次数改良: 折半插入排序折半插入排序由于直接插入排序算法利用了有序表的插入操作，由于直接插入排序算法利用了有序表的插入

10、操作，故顺序查找操作可以交换为折半查找操作。故顺序查找操作可以交换为折半查找操作。例，序列例，序列 49 38 65 97 76 13 27 设已构成有序表设已构成有序表 38 49 65 97 76 插入元素插入元素 13算法算法BinSort(r,n)BinSort(r,n) for (i=2;i=n;i+)for (i=2;i=n;i+)r0=ri; low=1; hig=i-1;r0=ri; low=1; hig=i-1; while (lowhig) while (lowhig) mid=(low+hig)/2; mid=(low+hig)/2; if (r0rmid) hig=mi

11、d-1; if (r0=low;j-)for (j=i-1;j=low;j-) rj+1=rj; rj+1=rj;rlow=r0;rlow=r0; 从挪动次数上改良从挪动次数上改良: 2-路插入排序路插入排序主要目的是减少排序过程中挪动记录的次数。主要目的是减少排序过程中挪动记录的次数。思想思想:以第一个元素为基准，将元素分为两个序列；以第一个元素为基准，将元素分为两个序列；比第一个元素小的元素构造前序列；比第一个元素小的元素构造前序列；比第一个元素大的元素构造后序列；比第一个元素大的元素构造后序列；例，序列例，序列 49 38 65 97 76 13 27 以以 49 为基准为基准 13 2

12、7 38 前序列前序列 65 76 97 后序列后序列算法描画算法描画初始，取第一个元素为基准元素；初始，取第一个元素为基准元素；构造前序列构造前序列 S1，后序列，后序列 S2 ；与基准元素比较与基准元素比较:假设小，插入到前序列假设小，插入到前序列 S1 中；中；假设大，插入到后序列假设大，插入到后序列 S2 中；中；对第对第 2 , 3 , , n 个元素依次执行个元素依次执行:S1 + 基准元素基准元素 + S2 可得最终有序表。可得最终有序表。例，序列例，序列 49 38 65 97 76 13 27 以以 49 为基准为基准前序列前序列后序列后序列 38 65 65 97 65 7

13、6 97 13 38 13 27 38 13 27 38 + 49 + 65 76 97 10.2.2 希尔希尔(shell)排序排序分析直接插入排序分析直接插入排序1. 假设待排序记录序列按关键字根本有序，那么排假设待排序记录序列按关键字根本有序，那么排序效率可大大提高；序效率可大大提高；2. 待排序记录总数越少，排序效率越高；待排序记录总数越少，排序效率越高；希尔排序希尔排序(减少增量法减少增量法)排序过程：先取一个正整数排序过程：先取一个正整数d1n，把一切相隔，把一切相隔d1的记的记录放一组，组内进展直接插入排序；然后取录放一组，组内进展直接插入排序；然后取d20)while (f0)

14、k=f-1; f=0;k=f-1; f=0;for (j=1;j=k;j+)for (j=1;jrj+1) if (rjrj+1) t=rj; rj=rj+1; rj+1=t; t=rj; rj=rj+1; rj+1=t; f-; f-; 算法也可写成：算法也可写成：BubbSort(r,n)BubbSort(r,n) for (i=0;in-1;i+)for (i=0;in-1;i+) for (j=i+1;jn;j+) for (j=i+1;jrj) if (rirj) t=ri; ri=rj; rj=t; t=ri; ri=rj; rj=t; 算法评价算法评价 时间复杂度时间复杂度 最好

15、情况正序最好情况正序 比较次数：比较次数：n-1 挪动次数：挪动次数：0 最坏情况逆序最坏情况逆序 比较次数：比较次数：)(21)(211nninniY挪动次数：挪动次数：)(23)(321nninni 空间复杂度：空间复杂度：S(n)=O(1)T(n)=O(n) 10.3.2 10.3.2 快速排序快速排序1 1根本思想：快速排序是对冒泡排序的一种改根本思想：快速排序是对冒泡排序的一种改良。经过一趟排序将一个无序区分割成两个独立良。经过一趟排序将一个无序区分割成两个独立的无序子区，其中前一部分子区中一切元素关键的无序子区，其中前一部分子区中一切元素关键字均不大于后一部分子区中元素关键字，然后

16、对字均不大于后一部分子区中元素关键字，然后对每一子区再进展分割，直到整个序列有序为止。每一子区再进展分割，直到整个序列有序为止。2 2分割过程：分割过程： 选取表中一个元素选取表中一个元素rkrk普通选取第一个普通选取第一个元素，令元素，令x=rkx=rk，称为控制关键字，称为控制关键字，用用控制关键字和无序区中其他元素关键字进展比较。控制关键字和无序区中其他元素关键字进展比较。 设置两个指示器设置两个指示器i,ji,j，分别表示线性表第，分别表示线性表第一个和最后一个元素位置。一个和最后一个元素位置。 将将j j逐渐减小，逐次比较逐渐减小，逐次比较rjrj与与x x，直到出现一个，直到出现一

17、个rjxrjxrix，然后将，然后将riri移到移到rj rj 位置。如此反复进展，直到位置。如此反复进展，直到i=ji=j为止，为止，最后将最后将x x移到移到rjrj位置，完成一趟排序。此时以位置，完成一趟排序。此时以x x为为界分割成两个子区。界分割成两个子区。举例：设序列为举例：设序列为46,55,13,42,94,5,17,7046,55,13,42,94,5,17,70j ji i46 55 13 42 94 5 17 70 46 55 13 42 94 5 17 70 起始形状，起始形状，46x46x，4646为控制关键为控制关键字字j ji i17 55 13 42 94 5

18、17 70 17 55 13 42 94 5 17 70 挪动挪动j j，17ri17rij ji i17 55 13 42 94 5 55 70 17 55 13 42 94 5 55 70 挪动挪动i i，55rj55rjj ji i17 5 13 42 94 5 55 70 17 5 13 42 94 5 55 70 挪动挪动j j，5ri5rij ji i17 5 13 42 94 94 55 70 17 5 13 42 94 94 55 70 挪动挪动i i，94rj94rjj ji i17 5 13 42 46 94 55 70 17 5 13 42 46 94 55 70 挪动挪

19、动j j，i=ji=j，xrixri，一趟排序，一趟排序终了终了算法：算法：QkSort(r,low,hig)QkSort(r,low,hig) x=rlow; i=low; j=hig;x=rlow; i=low; j=hig;while (ij)while (ij)while (i=x) j-;while (i=x) j-;t=ri; ri=rj; rj=t;t=ri; ri=rj; rj=t;while (ij&ri=x) i+;while (ij&ri=x) i+;t=ri; ri=rj; rj=t;t=ri; ri=rj; rj=t; ri=x;ri=x;QkSort

20、(r,low,i-1); QkSort(r,low,i-1); QkSort(r,i+1,hig);QkSort(r,i+1,hig); 算法评价算法评价 时间复杂度时间复杂度 最好情况每次总是选到中间值作枢轴最好情况每次总是选到中间值作枢轴T(n)=O(nlog2n) 最坏情况每次总是选到最小或最大元素作枢轴最坏情况每次总是选到最小或最大元素作枢轴T(n)=O(n) 空间复杂度：需栈空间以实现递归空间复杂度：需栈空间以实现递归 最坏情况：最坏情况：S(n)=O(n) 普通情况：普通情况：S(n)=O(log2n)T(n)=O(n)10.4 选择排序选择排序思想思想: 每一趟都选出一个最大或最

21、小的元素，并放在每一趟都选出一个最大或最小的元素，并放在适宜的位置。适宜的位置。 简单项选择择排序简单项选择择排序 树形选择排序树形选择排序 堆排序堆排序10.4.1 简单项选择择排序简单项选择择排序思想思想: 第第 1 趟选择趟选择: 从从 1n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并和第 1 个个记录交换。记录交换。第第 2 趟选择趟选择: 从从 2n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并和第 2 个个记录交换。记录交换。第第n-1趟选择趟选择:从从 n-1n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并

22、和第 n-1 个记录交换。个记录交换。. . .举例：设有序列：举例：设有序列： 5,4,12,20,27,3,1 5,4,12,20,27,3,1 ，排序，排序过称为：过称为：i=0i=0： 5 5，4 4，1212，2020，2727，3 3，1 1 i=1i=1： 1 1，4 4，1212，2020，2727，3 3，5 5 i=2i=2： 1 1，3 3，1212，2020，2727，4 4，5 5 i=3i=3： 1 1，3 3，4 4，2020，2727，1212，5 5 i=4i=4： 1 1，3 3，4 4，5 5，2727，1212，20 20 i=5i=5： 1 1，3 3

23、，4 4，5 5，1212，2727，20 20 结果：结果： 1 1，3 3，4 4，5 5，1212，2020，27 27 算法算法SelSort(r,n)SelSort(r,n) for (i=0;in-1;i+)for (i=0;in-1;i+)j=i;j=i;for (k=i+1;kn;k+)for (k=i+1;kn;k+)if (rjrk) j=k;if (rjrk) j=k;if (j!=i)if (j!=i)t=ri; ri=rk; rk=t;t=ri; ri=rk; rk=t; 算法分析：算法由两层循环构成，外层循环表示共需算法分析：算法由两层循环构成，外层循环表示共需进展

24、进展n-1n-1趟排序，内层循环表示每进展一趟排序需趟排序，内层循环表示每进展一趟排序需求进展的记录关键字间的比较。求进展的记录关键字间的比较。 比较次数：比较次数：n(n-1)/2n(n-1)/2 挪动次数：最坏情况下为挪动次数：最坏情况下为3(n-1)3(n-1)所以总的时间复杂度为：所以总的时间复杂度为：O(n2)O(n2)空间复杂度为：空间复杂度为：O(1) O(1) 交换记录用交换记录用选择排序的主要操作是进展关键字间的比较。选择排序的主要操作是进展关键字间的比较。在在 n 个关键字中选出最小值，至少需求个关键字中选出最小值，至少需求 n-1 次比较。次比较。在剩余的在剩余的 n-1

25、 个关键字中选出最小值，至少需求个关键字中选出最小值，至少需求 n-2 次比较？次比较？假设能利用前假设能利用前 n-1 次比较所得信息，可以减少后面选择的比较次数。次比较所得信息，可以减少后面选择的比较次数。体育竞赛中的锦标赛体育竞赛中的锦标赛:例，例，8 名运发动要决出名运发动要决出 冠、亚、季军。冠、亚、季军。按简单项选择择排序需求竞赛按简单项选择择排序需求竞赛 7+6+5 = 18 场。场。假设可以利用以前的竞赛结果，竞赛场次实践可以减少为假设可以利用以前的竞赛结果，竞赛场次实践可以减少为 11 场。场。前提前提: 假设假设 甲甲 胜胜 乙乙 ，乙，乙 胜胜 丙丙 ，那么，那么 甲甲

26、必能胜必能胜 丙丙 。ZhaoxiaLiuBaoDiYangXueWangBaoBaoDixiaBaoDiWang冠军冠军如何求如何求 亚军？亚军？ZhaoChaLiuDiYangXueWangxiaDixia亚军亚军可以利用前面的竞赛结果！可以利用前面的竞赛结果！xiaLiuDiWang如何求如何求 季军？季军？ZhaoLiuDiYangXueWangLiuDiDi季军季军同样可以利用前面的竞赛结果！同样可以利用前面的竞赛结果！LiuDiWangZhao10.4.2 树形选择排序树形选择排序又称锦标赛排序，是一种按照锦标赛的思想进展选择排序的方法。又称锦标赛排序，是一种按照锦标赛的思想进展选

27、择排序的方法。例，序列例，序列 49 38 65 97 76 13 27 50第一趟选择第一趟选择133813493865977613275038651327最小值最小值第二趟选择第二趟选择2738274938659776275038657627次小值次小值第三趟选择第三趟选择38385049386597765038657650次次小值次次小值493865977613275049386597762750缺陷缺陷: 需求需求大量辅助存大量辅助存储空间储空间 堆排序堆排序 堆的定义：堆的定义：n个元素的序列个元素的序列(k1,k2,kn)，当且，当且仅当满足以下关系时，称之为堆仅当满足以下关系时，

28、称之为堆或或(i=1,2,.n/2 )kik2ikik2i+1kik2ikik2i+1例例 96，83，27，38，11，9 例例 13，38，27，50，76，65，49，97962791138831327384965765097可将堆序列看成完全二叉树，那么堆顶元素完全二叉树的根可将堆序列看成完全二叉树，那么堆顶元素完全二叉树的根必为序列中必为序列中n个元素的最小值或最大值个元素的最小值或最大值 堆排序：将无序序列建成一个堆，得到关键字最小或最堆排序：将无序序列建成一个堆，得到关键字最小或最大的记录；输出堆顶的最小大值后，使剩余的大的记录；输出堆顶的最小大值后，使剩余的n-1个个元素重又建

29、成一个堆，那么可得到元素重又建成一个堆，那么可得到n个元素的次小值；反个元素的次小值；反复执行，得到一个有序序列，这个过程叫复执行，得到一个有序序列，这个过程叫 堆排序需处理的两个问题：堆排序需处理的两个问题： 如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？新的堆？ 第二个问题处理方法第二个问题处理方法挑选挑选 方法：输出堆顶元素之后，以堆中最后一个元素替代之；方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进展比较，并与然后将根结点

30、值与左、右子树的根结点值进展比较，并与其中小者进展交换；反复上述操作，直至叶子结点，将得其中小者进展交换；反复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为到新的堆，称这个从堆顶至叶子的调整过程为“挑选挑选例例13273849657650979727384965765013输出：输出：132749389765765013输出：输出：139749382765765013输出：输出：13 273849502765769713输出：输出：13 276549502738769713输出：输出：13 27 384965502738769713输出：输出：13 27 38766550

31、2738499713输出：输出：13 27 38 495065762738499713输出：输出：13 27 38 499765762738495013输出：输出：13 27 38 49 506597762738495013输出：输出：13 27 38 49 509765762738495013输出：输出：13 27 38 49 50 657665972738495013输出：输出：13 27 38 49 50 659765762738495013输出：输出：13 27 38 49 50 65 769765762738495013输出：输出：13 27 38 49 50 65 76 97算法为

32、：算法为：Typedef SqList HeapTypeTypedef SqList HeapType；/堆采用顺序构造存储堆采用顺序构造存储, ,数组数组r rVoid HeapAdjust(HeapType r,int s,int m)Void HeapAdjust(HeapType r,int s,int m) t=rs;t=rs; for(j=2 for(j=2* *s;j=m;js;j=m;j* *=2)=2) if (jrj+1) j+; if (jrj+1) j+; if (trj) rs=rj; s=j; if (trj) rs=rj; s=j; else break;else

33、 break; ri=t;ri=t; R1.7=97,38,27,50,76,65,49R1.7=97,38,27,50,76,65,49S=1,m=7S=1,m=7 第一个问题处理方法第一个问题处理方法 方法：从无序序列的第方法：从无序序列的第n/2 个元素即此无序序列对个元素即此无序序列对应的完全二叉树的最后一个非终端结点起，至第一个应的完全二叉树的最后一个非终端结点起，至第一个元素止，进展反复挑选元素止，进展反复挑选97273849657650例例 含含8个元素的无序序列个元素的无序序列49，38，65，97，76，13，27，504965382713769750496538271376

34、5097491338276576509749133827657650971327384965765097 算法为：HeapSort(HeapType r,n) for (i=n/2;i=1;i-) HeapAdjust(r,n,i); /初始建堆 for (i=n;i=2;i-) r1=ri; HeapAdjust(r,i-1,1); 算法评价算法评价 时间复杂度：最坏情况下时间复杂度：最坏情况下T(n)=O(nlogn) 空间复杂度：空间复杂度：S(n)=O(1)10.5 归并排序归并排序归并归并: 将两个或两个以上的有序表合并成一个新的有序表。将两个或两个以上的有序表合并成一个新的有序表。

35、有序线性表、有序链表的归并；有序线性表、有序链表的归并；利用归并的思想实现排序利用归并的思想实现排序 :初始，初始，n 个记录看作是个记录看作是 n 个有序的子序列，长度为个有序的子序列，长度为 1 ；两两归并，得到两两归并，得到 n/2 个长度为个长度为 2 或或 1 的有序的子序列的有序的子序列 ；再两两归并再两两归并 ；反复执行直至得到一个长度为反复执行直至得到一个长度为 n 的有序序列为止的有序序列为止 。这种排序方法称为这种排序方法称为 2路归并排序。路归并排序。例，序列例，序列 49 , 38 , 65 , 97 , 76 , 13 , 27 初始初始 49 38 65 97 76

36、 13 27 一趟归并一趟归并38 4965 9713 7627二趟归并二趟归并38 49 65 9713 27 76三趟归并三趟归并13 27 38 49 65 76 97void mergesort(JD r,int n) int i,s=1; JD tM; while(sn) tgb(s,n,r,t); s*=2; if(sn) tgb(s,n,t,r); s*=2; else i=1; while(i=n) ri=ti+; void tgb(int s,int n,JD r,JD t) int i=1; while(i=(n-2*s+1) merge(r,i,i+s-1,i+2*s-1

37、,t); i=i+2*s; if(i(n-s+1) merge(r,i,i+s-1,n,t); else while(i=n) ti=ri+;void merge(JD r,int h,int m,int w,JD t) int i,j,k; i=h; j=m+1; k=h-1; while(i=m)&(j=w) k+; if(ri.keym) while(j=w) t+k=rj+; else while(i=m) t+k=ri+; 算法评价算法评价 时间复杂度：时间复杂度：T(n)=O(nlog2n) 空间复杂度：空间复杂度：S(n)=O(n)10.6 基数排序基数排序是一种借助多关

38、键字排序的思想对单逻辑关键字进展排序的方法。是一种借助多关键字排序的思想对单逻辑关键字进展排序的方法。10.6.1 多关键字排序多关键字排序扑克牌问题扑克牌问题 :知扑克牌中知扑克牌中52张牌面的次序关系定义为张牌面的次序关系定义为: 花样花样:面值面值:2 3 A. . .例，例， 8 3花样优先级更高，花样优先级更高，为主关键字，面为主关键字，面值为次关键字值为次关键字52张牌排序方法张牌排序方法 :最高位优先法最高位优先法(MSDF) :先按不同先按不同“花样分成有次序的花样分成有次序的4堆，每一堆均具有一样的花样；堆，每一堆均具有一样的花样；然后分别对每一堆按然后分别对每一堆按“面值大

39、小整理有序。面值大小整理有序。最低位优先法最低位优先法(LSDF) :先按不同先按不同“面值分成面值分成 13 堆堆 ；然后将这然后将这 13 堆牌自小至大叠在一同堆牌自小至大叠在一同( 2 , 3 , . . . , A ) ；然后将这付牌整个颠倒过来再重新按不同的然后将这付牌整个颠倒过来再重新按不同的“花样分成花样分成 4 堆堆 ；最后将这最后将这 4 堆牌按自小至大的次序合在一同堆牌按自小至大的次序合在一同 。搜集搜集分配分配10.6.2 基数排序基数排序基数排序就是借助于基数排序就是借助于“分配和分配和“搜集两种操作实现对单逻辑关键搜集两种操作实现对单逻辑关键字的排序。字的排序。首先，

40、单逻辑关键字通常都可以看作是由假设干关键字复合而成。首先，单逻辑关键字通常都可以看作是由假设干关键字复合而成。其次，利用其次，利用 LSDF 法实现对假设干关键字的排序。法实现对假设干关键字的排序。例，假设关键字是数值，且值域为例，假设关键字是数值，且值域为 0K999 ，故可以将故可以将 K 看作是由看作是由 3 个关键字个关键字 K0 K1 K2 组成，组成，例，例，603是由是由 6 0 3 组成。组成。例，序列例，序列 278 109 063 930 589 184 505 269 008 083第一趟分配第一趟分配0 1 2 3 4 5 6 7 8 9278 109063930589184505269008083第一趟搜集第一趟搜集930063 083184505278 008109 589 269第二趟分配第二趟分配0 1 2 3 4 5 6 7 8 9930063083184505278008109589269第二趟搜集第二趟搜集505 008 109930063 269278083 184 589第二趟搜集第二趟搜集505 008 109930063 269278083 184 589第三趟分配第三趟分配0 1 2 3 4 5 6 7 8