第十章第十章 内部排序内部排序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 各种内部排序方法的比较讨论各种内部排序方法的比较讨论 110.6 基数排序基数排序 基数排序（基数排序（Radix Sorting）是一种借助多关键字排序的思想对单逻辑是一种借助多关键字排序的思想对单逻辑关键字进行关系的方法。基数排序不需要进行记录关键字间的比较。关键字进行关系的方法。基数排序不需要进行记录关键字间的比较。 210.6.1 多关键字的排序多关键字的排序（1）定义）定义 假设有假设有n个记录的序列个记录的序列R1, R2, , Rn（104），则称序列（，则称序列（104）对关键字）对关键字有序是指：对于序列中任意两个记录有序是指：对于序列中任意两个记录Ri和和Rj (1i jn)都满足都满足 其中其中K0称为最主位关键字，称为最主位关键字，Kd-1称为最次位关键字。称为最次位关键字。且每个记录且每个记录Ri中含有中含有d个关键字个关键字下列有序关系：下列有序关系：3（2）多关键字排序的实现）多关键字排序的实现 最高位优先最高位优先MSD（Most Signigicant Digit first） 1算法算法实现实现：先：先对对最主位关最主位关键键字字K0进进行排序，将序列分成若干子序行排序，将序列分成若干子序列，每个子序列中的列，每个子序列中的记录记录都具有相同的都具有相同的K0值值，然后分，然后分别别就每个子序列就每个子序列对对关关键键字字K1进进行排序，按行排序，按K1值值不同再分成若干更小的子序列，依次重复，不同再分成若干更小的子序列，依次重复，直至直至对对Kd-2进进行排序之后得到的每一子序列中的行排序之后得到的每一子序列中的记录记录都具有系都具有系统统的关的关键键字字，而后分，而后分别别每个子序列每个子序列对对Kd-1进进行排序，最后将所有子行排序，最后将所有子序列依次联接在一起成为一个有序序列。序列依次联接在一起成为一个有序序列。 2特点：按特点：按MSD进行排序时，必须将序列逐层分割成若干子序列，进行排序时，必须将序列逐层分割成若干子序列，然后对各子序列分别进行排序。然后对各子序列分别进行排序。4（2）多关键字排序的实现）多关键字排序的实现 最低位优先最低位优先LSD（Least Signigicant Digit first） 1算法实现：从最次位关键字算法实现：从最次位关键字Kd-1起进行排序。然后再对高一位的关起进行排序。然后再对高一位的关键字键字Kd-2进行排序，依次重复，直至对进行排序，依次重复，直至对K0进行排序后便成为一个有序序列。进行排序后便成为一个有序序列。 2特点：特点： a. 按按LSD进行排序时，不必分成子序列，对每个关键字都是整个序列进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，但对参加排序，但对Ki(0id2) 进行排序时，只能用稳定的排序方法。进行排序时，只能用稳定的排序方法。 b. 按按LSD进行排序时，在一定的条件下（即对前一个关键字进行排序时，在一定的条件下（即对前一个关键字Ki(0id-2)的不同值，后一个关键字的不同值，后一个关键字Ki+1均取相同值），可通过若干次均取相同值），可通过若干次“分配分配”和和“收集收集”来来实现排序。实现排序。5（3）例子）例子 例如，已知扑克牌中例如，已知扑克牌中52张牌面的次序关系为：张牌面的次序关系为： 23A23A23A23A 每一张牌有两个每一张牌有两个“关键字关键字”：花色：花色()和面值和面值(23A)，且且“花色花色”的地的地 位高于位高于“面值面值”。扑克牌整理成如上所述关系时：扑克牌整理成如上所述关系时：MSD：先按不同先按不同“花色花色”分成有次序的分成有次序的4堆堆,每一堆的牌均具有相同的每一堆的牌均具有相同的“花色花色”, 然后分别对每一堆按然后分别对每一堆按“面值面值”大小整理有序。大小整理有序。LSD：先按不同先按不同“面值面值”分成分成13堆堆,然后将这然后将这13堆牌自小至大叠在一起（堆牌自小至大叠在一起（“3” 在在“2”之上，之上，“4”在在“3”之上，之上，最上面的是，最上面的是4张张“A”），），然后将然后将 这付牌整个颠倒过来再重新按不同这付牌整个颠倒过来再重新按不同“花色花色”分成分成4堆，最后将这堆，最后将这4堆牌堆牌 按自小至大的次序合在一起（按自小至大的次序合在一起（在最下面，在最下面，在最上面）。在最上面）。6LSDLSD和和MSDMSD方法也可应用于对一个关键字进行的排序。此时方法也可应用于对一个关键字进行的排序。此时可将单关键字可将单关键字K Ki i看成是一个子关键字组：看成是一个子关键字组： ( (K Ki i1 1,K,Ki i2 2,., K,., Ki id d) )如对关键字取值范围为如对关键字取值范围为0 0到到999999的一组对象，可看成是的一组对象，可看成是( (K K1 1,K,K2 2,K,K3 3) )的组合。的组合。MSDMSD方法按方法按K K1 1,K,K2 2,K,K3 3的的顺序对所有对象排序；顺序对所有对象排序；LSDLSD方法方法按按K K3 3 ,K,K2 2 , K , K1 1的顺序对所有对象排序。的顺序对所有对象排序。710.6.2 链式基数排序链式基数排序（1）定义）定义 有的逻辑关键字可以看成由若干个关键字复合而成的，且每个关键字有的逻辑关键字可以看成由若干个关键字复合而成的，且每个关键字Kj都都 在相同的范围内，则按在相同的范围内，则按LSD进行排序时，只要从最低数位关键字起，按关键字进行排序时，只要从最低数位关键字起，按关键字 的不同值将序列中记录的不同值将序列中记录“分配分配”到到PADIX个队列中后再个队列中后再“收集收集”之，如此重复之，如此重复d次。次。 按这种方法实现的排序称之为按这种方法实现的排序称之为基数排序基数排序。其中。其中“基基”指的是指的是RADIX的取值范围。的取值范围。链式基数排序链式基数排序：用链表作存储结构的基数排序。：用链表作存储结构的基数排序。 例如，若关例如，若关键键字是数字是数值值，且其，且其值值都在都在0K999范范围围内，内，则则可把每一个十可把每一个十进进制数字看成一个关制数字看成一个关键键字，即可字，即可认为认为K由由3个关个关键键字字(K0, K1, K2)组组成，其中成，其中K0是是百位数，百位数，K1是十位数，是十位数，K2是个位数，是个位数，对对每一个关每一个关键键字字0Ki9（i0, 1, 2），），“基基”为为10。 8（3）例子）例子 例如，图例如，图10.13(a)所示；第一趟分配对最低位关键字（个位数）进行，改变所示；第一趟分配对最低位关键字（个位数）进行，改变记录的指针值将链表中的记录分配至记录的指针值将链表中的记录分配至10个链队列中去，每个队列中的记录关键字个链队列中去，每个队列中的记录关键字的个位数相等，如图的个位数相等，如图10.13(b)所示，其中所示，其中fi和和ei分别为第分别为第i个队列的头指针和尾个队列的头指针和尾指针；第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非指针；第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将空队列的队头记录，重新将10个队列中的记录链成一个链表，如个队列中的记录链成一个链表，如图图10.13(c)所示；所示；第二趟分配，第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进第二趟分配，第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进行的，其过程和个位数相同，如行的，其过程和个位数相同，如图图10.13(d)(g)所示。至此排序完毕。所示。至此排序完毕。(a) 初始状态初始状态278 109 063 930 589 184 505 269 008 083e0 e1 e2 e3 e4 e5 e6 e7 e8 e9f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 930 063 184 505 278 109 269 589 008 083 (b) 第一趟分配之后第一趟分配之后 9930 063 083 184 505 278 008 109 589 269(c) 第一趟收集之后第一趟收集之后 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 505 930 063 278 083 269 589 008 109 184 (d) 第二趟分配之后第二趟分配之后505 008 109 930 063 269 278 083 184 589(e) 第二趟收集之后第二趟收集之后 10(f) 第三趟分配之后第三趟分配之后e0 e1 e2 e3 e4 e5 e6 e7 e8 e9f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 008269 589 063 109 184 930 505 083 278 008 063 083 109 184 269 278 505 589 930(g) 第三趟收集之后的有序文件第三趟收集之后的有序文件 图图10.13 链式基数排序示例链式基数排序示例505 008 109 930 063 269 278 083 184 58911 （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;/指针数组类型指针数组类型12算法算法10.15如下：如下： void Distribute (SLCell &r, int i, ArrType &f, ArrType &e) /静态链表静态链表L的的r域中记录已按域中记录已按(keys0, , keysi1)有序。本算法按第有序。本算法按第i/个关键字个关键字keysi建立建立RADIX个子表，使同一子表中记录的个子表，使同一子表中记录的keysi相同。相同。/f0.RADIX-1和和e0.RADIX-1分别指向各子表中第一个和最后一个记录。分别指向各子表中第一个和最后一个记录。for (j = 0; j Radix; + + j)/各子表初始化为空表各子表初始化为空表 fj = 0;for (p = r0.next; p; p = rp.next) j = ord(rp.keysi); /ord将记录中第将记录中第i个关键字映射到个关键字映射到0.RADIX-1 if (!fj)fj = p; else rej.next = p; ej = p;/将将p所指的结点插入第所指的结点插入第j个子表中个子表中 / for / Distribute算法实现算法实现 算法算法10.15为链式基数排序中一趟分配的算法，为链式基数排序中一趟分配的算法，算法算法10.16为一趟收集的算为一趟收集的算法，法，算法算法10.17为链式基数排序的算法。为链式基数排序的算法。13 void Collect (SLCell &r, int i, ArrType &f, ArrType &e) /本算法按本算法按keysi自小至大地将自小至大地将f0.RADIX1所指各子表依次链接成一个链表，所指各子表依次链接成一个链表，/一个链表，一个链表， e0.RADIX-1为各子表的尾指针。为各子表的尾指针。for (j = 0; !fj; j = succ(j);/找第一个非空子表，找第一个非空子表，succ为求后继函数为求后继函数r0.next = fj;/r0.next指向第一个非空子表中第一个结点指向第一个非空子表中第一个结点t = ej;while (j RADIX) for (j = succ(j); j RADIX1 & !fj; j = succ(j);/找下一个非空子表找下一个非空子表if (fj) /链接两个非空子表链接两个非空子表 rt.next = fj; t = ej;rt.next = 0;/t指向最后一个非空子表中的最后一个结点指向最后一个非空子表中的最后一个结点 / Collect算法算法10.16如下：如下：算法算法10.16为一趟收集的算法，为一趟收集的算法，14 void RadixSort (SLList &L) /L是采用静态链表表示的顺序表。对是采用静态链表表示的顺序表。对L作基数排序，使得作基数排序，使得L成为成为/按关键字自小到大的有序静态链表按关键字自小到大的有序静态链表,L.r0为头结点。为头结点。for (i = 0; i L.recnum; + + i) L.ri.next = i + 1;L.rL.recnum.next = 0; /将将L改造为静态链表改造为静态链表for (i = 0; i L.keynum; + + i) /按最低位优先依次对各关键字进行分配和收集按最低位优先依次对各关键字进行分配和收集 Distributr (L.r, i, f, e); /第第i趟分配趟分配 Collect(L.r, i, f, e); /第第i趟收集趟收集 / for / RadixSort 算法算法10.17如下：如下：算法算法10.17为链式基数排序的算法。为链式基数排序的算法。15 从上述算法中容易看出，对于从上述算法中容易看出，对于n个记录（假设每个记录含个记录（假设每个记录含d个关键字，每个关个关键字，每个关键字的取值范围为键字的取值范围为rd个值）进行链式基数排序的时间复杂度为个值）进行链式基数排序的时间复杂度为O(d(n + rd)，其中其中每一趟分配的时间复杂度为每一趟分配的时间复杂度为O(n)，每一趟收集的时间复杂度为每一趟收集的时间复杂度为O(rd)，整个排序需整个排序需进行进行d趟分配和收集。所需辅助空间为趟分配和收集。所需辅助空间为2rd个队列指针。个队列指针。 16template 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 bins./ cnti stores numbers of records in bini int j; for (int i=0, rtok=1; ik; i+, rtok*=r) for (j=0; jr; j+) cntj = 0;/ Count numbers of records for each bin for(j=0; jn; j+) cnt(Aj/rtok)%r+;/Index B: cntj will be last slot of bin j. for (j=1; j=0; j-) B-cnt(Aj/rtok)%r = Aj;/Copy B back to A. for (j=0; jn; j+) Aj = Bj; 17