第十章F基数排序ppt课件

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 各种内部排序方法的比较讨论各种内部排序方法的比较讨论 10.6 基数排序基数排序 基数排序基数排序Radix Sor

2、ting是一种借助多关键字排序的思想对单逻辑是一种借助多关键字排序的思想对单逻辑关键字进展关系的方法。基数排序不需求进展记录关键字间的比较。关键字进展关系的方法。基数排序不需求进展记录关键字间的比较。 10.6.1 多关键字的排序多关键字的排序1定义定义 假设有假设有n个记录的序列个记录的序列R1, R2, , Rn104),(110diiiKKK，那么称序列，那么称序列104对关键字对关键字),(110dKKK有序是指：对于序列中恣意两个记录有序是指：对于序列中恣意两个记录Ri和和Rj (1i jn)都满足都满足),(110diiiKKK ),(110djjjKKK其中其中K0称为最主位关键

3、字，称为最主位关键字，Kd-1称为最次位关键字。称为最次位关键字。且每个记录且每个记录Ri中含有中含有d个关键字个关键字以下有序关系：以下有序关系：2多关键字排序的实现多关键字排序的实现 最高位优先最高位优先MSDMost Signigicant Digit first 1算法实现：先对最主位关键字算法实现：先对最主位关键字K0进展排序，将序列分成假设干子序进展排序，将序列分成假设干子序列，每个子序列中的记录都具有一样的列，每个子序列中的记录都具有一样的K0值，然后分别就每个子序列对值，然后分别就每个子序列对关键字关键字K1进展排序，按进展排序，按K1值不同再分成假设干更小的子序列，依次反复，

4、值不同再分成假设干更小的子序列，依次反复，直至对直至对Kd-2进展排序之后得到的每一子序列中的记录都具有系统的关键字进展排序之后得到的每一子序列中的记录都具有系统的关键字),(210dKKK，而后分别每个子序列对，而后分别每个子序列对Kd-1进展排序，最后将一切子进展排序，最后将一切子序列依次联接在一同成为一个有序序列。序列依次联接在一同成为一个有序序列。 2特点：按特点：按MSD进展排序时，必需将序列逐层分割成假设干子序列，进展排序时，必需将序列逐层分割成假设干子序列，然后对各子序列分别进展排序。然后对各子序列分别进展排序。2多关键字排序的实现多关键字排序的实现 最低位优先最低位优先LSDL

5、east Signigicant Digit first 1算法实现：从最次位关键字算法实现：从最次位关键字Kd-1起进展排序。然后再对高一位的关起进展排序。然后再对高一位的关键字键字Kd-2进展排序，依次反复，直至对进展排序，依次反复，直至对K0进展排序后便成为一个有序序列。进展排序后便成为一个有序序列。 2特点：特点： a. 按按LSD进展排序时，不用分成子序列，对每个关键字都是整个序列进展排序时，不用分成子序列，对每个关键字都是整个序列参与排序，但对参与排序，但对Ki(0id2) 进展排序时，只能用稳定的排序方法。进展排序时，只能用稳定的排序方法。 b. 按LSD进展排序时，在一定的条件

6、下即对前一个关键字Ki(0id-2)的不同值，后一个关键字Ki+1均取一样值，可经过假设干次“分配和“搜集来实现排序。3例子例子 例如，知扑克牌中例如，知扑克牌中52张牌面的次序关系为：张牌面的次序关系为： 2 3 A 2 3 A 2 3 A 2 3 A 每一张牌有两个每一张牌有两个“关键字：花样关键字：花样( )和面值和面值(23A)，且，且“花花样的地样的地 位高于位高于“面值。面值。扑克牌整理成如上所述关系时：扑克牌整理成如上所述关系时：MSD：先按不同：先按不同“花样分成有次序的花样分成有次序的4堆堆,每一堆的牌均具有一样的每一堆的牌均具有一样的“花样花样, 然后分别对每一堆按然后分别

7、对每一堆按“面值大小整理有序。面值大小整理有序。LSD：先按不同：先按不同“面值分成面值分成13堆堆,然后将这然后将这13堆牌自小至大叠在一同堆牌自小至大叠在一同“3 在在“2之上，之上，“4在在“3之上，之上，最上面的是，最上面的是4张张“A，然后将，然后将 这付牌整个颠倒过来再重新按不同这付牌整个颠倒过来再重新按不同“花样分成花样分成4堆，最后将这堆，最后将这4堆牌堆牌 按自小至大的次序合在一同按自小至大的次序合在一同 在最下面，在最下面， 在最上面。在最上面。 LSDLSD和和MSDMSD方法也可运用于对一个关键字进展的排序。此时方法也可运用于对一个关键字进展的排序。此时可将单关键字可将

8、单关键字KiKi看成是一个子关键字组：看成是一个子关键字组： (Ki1,Ki2,., Kid)(Ki1,Ki2,., Kid) 如对关键字取值范围为如对关键字取值范围为0 0到到999999的一组对象，可看成是的一组对象，可看成是(K1,K2,K3)(K1,K2,K3)的组合。的组合。 MSDMSD方法按方法按K1,K2,K3K1,K2,K3的顺序对一切对象排序；的顺序对一切对象排序；LSDLSD方法按方法按K3 ,K2 , K1K3 ,K2 , K1的顺序对一切对象排序。的顺序对一切对象排序。10.6.2 链式基数排序链式基数排序1定义定义 有的逻辑关键字可以看成由假设干个关键字复合而成的，

9、且每个关键字有的逻辑关键字可以看成由假设干个关键字复合而成的，且每个关键字Kj都都 在一样的范围内，那么按在一样的范围内，那么按LSD进展排序时，只需从最低数位关键字起，按关键字进展排序时，只需从最低数位关键字起，按关键字 的不同值将序列中记录的不同值将序列中记录“分配到分配到PADIX个队列中后再个队列中后再“搜集之，如此反复搜集之，如此反复d次。次。 按这种方法实现的排序称之为基数排序。其中按这种方法实现的排序称之为基数排序。其中“基指的是基指的是RADIX的取值范围。的取值范围。链式基数排序：用链表作存储构造的基数排序。链式基数排序：用链表作存储构造的基数排序。 例如，假设关键字是数值，

10、且其值都在例如，假设关键字是数值，且其值都在0K999范围内，那么可把每一个十范围内，那么可把每一个十进制数字看成一个关键字，即可以为进制数字看成一个关键字，即可以为K由由3个关键字个关键字(K0, K1, K2)组成，其中组成，其中K0是是百位数，百位数，K1是十位数，是十位数，K2是个位数，对每一个关键字是个位数，对每一个关键字0Ki9i0, 1, 2，“基为基为10。3例子例子 例如，图例如，图10.13(a)所示；第一趟分配对最低位关键字个位数进展，改动所示；第一趟分配对最低位关键字个位数进展，改动记录的指针值将链表中的记录分配至记录的指针值将链表中的记录分配至10个链队列中去，每个队

11、列中的记录关键字个链队列中去，每个队列中的记录关键字的个位数相等，如图的个位数相等，如图10.13(b)所示，其中所示，其中fi和和ei分别为第分别为第i个队列的头指针和尾个队列的头指针和尾指针；第一趟搜集是改动一切非空队列的队尾记录的指针域，令其指向下一个非指针；第一趟搜集是改动一切非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将空队列的队头记录，重新将10个队列中的记录链成一个链表，如图个队列中的记录链成一个链表，如图10.13(c)所示；所示；第二趟分配，第二趟搜集及第三趟分配和第三趟搜集分别是对十位数和百位数进第二趟分配，第二趟搜集及第三趟分配和第三趟搜集分别是对十

12、位数和百位数进行的，其过程和个位数一样，如图行的，其过程和个位数一样，如图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) 第一趟分配之后第一趟分配之后 930 063 083 184 505 278 008 109 589 269(c) 第一趟搜集之后第一趟搜集之后 e0 e1

13、 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) 第二趟搜集之后第二趟搜集之后 (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 10

14、9 184 269 278 505 589 930(g) 第三趟搜集之后的有序文件第三趟搜集之后的有序文件 图图10.13 链式基数排序例如链式基数排序例如505 008 109 930 063 269 278 083 184 589 2算法实现算法实现数据类型的定义数据类型的定义#defineMAX_NUM_OF_KEY8/关键字项数的最大值关键字项数的最大值#defineRADIX10/关键字基数，此时是十进制整数的基数关键字基数，此时是十进制整数的基数#defineMAX_SPACE10000typedef struct KeyType keysMAX_NUM_OF_KEY;/关键字关键

15、字 InfoType otheritems;/其他数据项其他数据项 int next; SLCell;/静态链表的结点类型静态链表的结点类型typedef struct SLCellrMAX_SPACE;/静态链表的可利用空间，静态链表的可利用空间，r0为头结点为头结点 intkeynum;/记录的当前关键字个数记录的当前关键字个数 intrecnum;/静态链表的当前长度静态链表的当前长度 SLList;/静态链表类型静态链表类型typedef int ArrTypeRADIX;/指针数组类型指针数组类型算法算法10.15如下：如下： void Distribute (SLCell &

16、;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

17、= 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为链式基数排序的算法。为链式基数排序的算法。 void Collect (SLCell &r, int

18、 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 R

19、ADIX1 & !fj; j = succ(j);/找下一个非空子表找下一个非空子表if (fj) /链接两个非空子表链接两个非空子表 rt.next = fj; t = ej;rt.next = 0;/t指向最后一个非空子表中的最后一个结点指向最后一个非空子表中的最后一个结点 / Collect算法算法10.16如下：如下：算法算法10.16为一趟搜集的算法，为一趟搜集的算法， void RadixSort (SLList &L) /L是采用静态链表表示的顺序表。对是采用静态链表表示的顺序表。对L作基数排序，使得作基数排序，使得L成为成为/按关键字自小到大的有序静态链表按关键

20、字自小到大的有序静态链表,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为链式基数排序的算法。为链式基数排序的算法。 从上述算法中容易看出，对于从上述算法中容易看出，对于n个记录假设每个记录含个记录假设每个记录含d个关键字，每个关个关键字，每个关键字的取值范围为键字的取值范围为rd个值进展链式基数排序的时间复杂度为个值进展链式基数排序的时间复杂度为O(d(n + rd)，其中，其中每一趟分配的时间复