《数据结构》-第十章f基数排序

1,第十章 内部排序,10.1 概述,10.2 插入排序,10.2.1 直接插入排序,10.2.2 其他插入排序,10.2.3 希尔排序,10.3 快速排序,10.4 选择排序,10.4.1 简单选择排序,10.4.2 树形选择排序,10.4.3 堆排序,10.5 归并排序,10.6 基数排序,10.6.1 多关键字的排序,10.6.2 链式基数排序,10.7 各种内部排序方法的比较讨论,2,10.6 基数排序,基数排序（Radix Sorting）是一种借助多关键字排序的思想对单逻辑关键字进行关系的方法。基数排序不需要进行记录关键字间的比较。,3,10.6.1 多关键字的排序,4,（2）多关键字排序的实现, 最高位优先MSD（Most Signigicant Digit first）,2特点：按MSD进行排序时，必须将序列逐层分割成若干子序列，然后对各子序列分别进行排序。,5,（2）多关键字排序的实现, 最低位优先LSD（Least Signigicant Digit first）,1算法实现：从最次位关键字Kd-1起进行排序。然后再对高一位的关键字Kd-2进行排序，依次重复，直至对K0进行排序后便成为一个有序序列。,2特点： a. 按LSD进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，但对Ki(0id2) 进行排序时，只能用稳定的排序方法。,b. 按LSD进行排序时，在一定的条件下（即对前一个关键字Ki(0id-2)的不同值，后一个关键字Ki+1均取相同值），可通过若干次“分配”和“收集”来实现排序。,6,（3）例子 例如，已知扑克牌中52张牌面的次序关系为： 23A23A23A23A 每一张牌有两个“关键字”：花色()和面值(23A)，且“花色”的地 位高于“面值”。,扑克牌整理成如上所述关系时：,MSD：先按不同“花色”分成有次序的4堆,每一堆的牌均具有相同的“花色”, 然后分别对每一堆按“面值”大小整理有序。,LSD：先按不同“面值”分成13堆,然后将这13堆牌自小至大叠在一起（“3” 在“2”之上，“4”在“3”之上，最上面的是4张“A”），然后将 这付牌整个颠倒过来再重新按不同“花色”分成4堆，最后将这4堆牌 按自小至大的次序合在一起（在最下面，在最上面）。,7,LSD和MSD方法也可应用于对一个关键字进行的排序。此时可将单关键字Ki看成是一个子关键字组： (Ki1,Ki2,., Kid)如对关键字取值范围为0到999的一组对象，可看成是(K1,K2,K3)的组合。MSD方法按K1,K2,K3的顺序对所有对象排序；LSD方法按K3 ,K2 , K1的顺序对所有对象排序。,8,10.6.2 链式基数排序,（1）定义 有的逻辑关键字可以看成由若干个关键字复合而成的，且每个关键字Kj都 在相同的范围内，则按LSD进行排序时，只要从最低数位关键字起，按关键字 的不同值将序列中记录“分配”到PADIX个队列中后再“收集”之，如此重复d次。 按这种方法实现的排序称之为基数排序。其中“基”指的是RADIX的取值范围。,链式基数排序：用链表作存储结构的基数排序。,例如，若关键字是数值，且其值都在0K999范围内，则可把每一个十进制数字看成一个关键字，即可认为K由3个关键字(K0, K1, K2)组成，其中K0是百位数，K1是十位数，K2是个位数，对每一个关键字0Ki9（i0, 1, 2），“基”为10。,9,（3）例子 例如，图10.13(a)所示；第一趟分配对最低位关键字（个位数）进行，改变记录的指针值将链表中的记录分配至10个链队列中去，每个队列中的记录关键字的个位数相等，如图10.13(b)所示，其中fi和ei分别为第i个队列的头指针和尾指针；第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列中的记录链成一个链表，如图10.13(c)所示；第二趟分配，第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进行的，其过程和个位数相同，如图10.13(d)(g)所示。至此排序完毕。,(a) 初始状态,(b) 第一趟分配之后,10,(c) 第一趟收集之后,(d) 第二趟分配之后,(e) 第二趟收集之后,11,(f) 第三趟分配之后,(g) 第三趟收集之后的有序文件,图10.13 链式基数排序示例,12,（2）算法实现数据类型的定义#defineMAX_NUM_OF_KEY8/关键字项数的最大值#defineRADIX10/关键字基数，此时是十进制整数的基数#defineMAX_SPACE10000typedef struct KeyType keysMAX_NUM_OF_KEY;/关键字 InfoType otheritems;/其他数据项 int next; SLCell;/静态链表的结点类型typedef struct SLCellrMAX_SPACE;/静态链表的可利用空间，r0为头结点 intkeynum;/记录的当前关键字个数 intrecnum;/静态链表的当前长度 SLList;/静态链表类型typedef int ArrTypeRADIX;/指针数组类型,13,算法10.15如下： void Distribute (SLCell /将p所指的结点插入第j个子表中 / for / Distribute,算法实现 算法10.15为链式基数排序中一趟分配的算法，算法10.16为一趟收集的算法，算法10.17为链式基数排序的算法。,14,void Collect (SLCell /t指向最后一个非空子表中的最后一个结点 / Collect,算法10.16如下：,算法10.16为一趟收集的算法，,15,void RadixSort (SLList /第i趟收集 / for / RadixSort,算法10.17如下：,算法10.17为链式基数排序的算法。,16,从上述算法中容易看出，对于n个记录（假设每个记录含d个关键字，每个关键字的取值范围为rd个值）进行链式基数排序的时间复杂度为O(d(n + rd)，其中每一趟分配的时间复杂度为O(n)，每一趟收集的时间复杂度为O(rd)，整个排序需进行d趟分配和收集。所需辅助空间为2rd个队列指针。,template void radix(Elem A, Elem B, int n, int k, int r, int cnt) /If there are k digits,then this requires that we assign keys /to bins k times./If we know how many values will be in each bin,then an /auxiliary array of size r can be used to hold the bin