数据结构第9章排序ppt课件

1、数据构造课程的内容数据构造课程的内容9.1 9.1 概述概述9.2 9.2 插入排序插入排序9.3 9.3 交换排序交换排序9.4 9.4 选择排序选择排序9.5 9.5 归并排序归并排序9.6 9.6 基数排序基数排序9.1 9.1 概述概述1. 什么是排序？什么是排序？ 将一组杂乱无章的数据按一定的规律依次陈列起来。将一组杂乱无章的数据按一定的规律依次陈列起来。 2. 排序的目的是什么？排序的目的是什么？存放在数据表中存放在数据表中按关键字排序按关键字排序3.3.排序算法的好坏如何衡量？排序算法的好坏如何衡量？时间效率时间效率排序速度即排序所破费的全部比较排序速度即排序所破费的全部比较次数

2、次数空间效率空间效率占内存辅助空间的大小占内存辅助空间的大小稳定性稳定性假设两个记录假设两个记录A A和和B B的关键字值相等，但的关键字值相等，但排序后排序后A A、B B的先后次序坚持不变，那么称这种排序的先后次序坚持不变，那么称这种排序算法是稳定的。算法是稳定的。 便于查找！便于查找！4. 什么叫内部排序？什么叫外部排序？什么叫内部排序？什么叫外部排序？ 假设待排序记录都在内存中，称为内部排序；假设待排序记录都在内存中，称为内部排序；假设待排序记录一部分在内存，一部分在外存，假设待排序记录一部分在内存，一部分在外存，那么称为外部排序。那么称为外部排序。注：外部排序时，要将数据分批调入内存

3、来排序，中间注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。结果还要及时放入外存，显然外部排序要复杂得多。 5.5.待排序记录在内存中怎样存储和处置？待排序记录在内存中怎样存储和处置？ 顺序排序顺序排序排序时直接挪动记录；排序时直接挪动记录； 链表排序链表排序排序时只挪动指针；排序时只挪动指针； 地址排序地址排序排序时先挪动地址，最后再挪动记录。排序时先挪动地址，最后再挪动记录。注：地址排序中可以增设一维数组来专门存放记录的地址。注：地址排序中可以增设一维数组来专门存放记录的地址。注：大多数排序算法都是针对顺序表构造的注：大多数排序算法都是针对顺序

4、表构造的(便于直接挪动元素便于直接挪动元素)6. 6. 顺序存储顺序表的笼统数据类型如何表示？顺序存储顺序表的笼统数据类型如何表示？Typedef struct /定义每个记录数据元素的构造定义每个记录数据元素的构造 KeyType key ; /关键字关键字 InfoType otherinfo; /其它数据项其它数据项RecordType ;Typedef struct /定义顺序表的构造定义顺序表的构造 RecordType r MAXSIZE +1 ; /存储顺序表的向量存储顺序表的向量 /r0普通作哨兵或缓冲区普通作哨兵或缓冲区 int length ; /顺序表的长度顺序表的长度S

5、qList ;# define MAXSIZE 20 /设记录不超越设记录不超越20个个typedef int KeyType ; /设关键字为整型量设关键字为整型量int型型7. 内部排序的算法有哪些？内部排序的算法有哪些？按排序的规那么不同，可分为按排序的规那么不同，可分为5类：类：插入排序插入排序交换排序重点是快速排序交换排序重点是快速排序选择排序选择排序归并排序归并排序基数排序基数排序d关键字的位数关键字的位数(长度长度)按排序算法的时间复杂度不同，可分为按排序算法的时间复杂度不同，可分为3类：类：简单的排序算法：时间效率低，简单的排序算法：时间效率低，O(n2)先进的排序算法先进的排

6、序算法: 时间效率高，时间效率高，O( nlog2n )基数排序算算法：时间效率高，基数排序算算法：时间效率高，O( dn)9.2 9.2 插入排序插入排序插入排序有多种详细实现算法：插入排序有多种详细实现算法： 1) 直接插入排序直接插入排序 2) 折半插入排序折半插入排序 3) 2-路插入排序路插入排序 4) 表插入排序表插入排序 5) 希尔排序希尔排序新元素插入到哪里？新元素插入到哪里？例例1 1：关键字序列：关键字序列T=T=1313，6 6，3 3，3131，9 9，2727，5 5，1111， 请写出直接插入排序的中间过程序列。请写出直接插入排序的中间过程序列。【13】, 6, 3

7、, 31, 9, 27, 5, 11【6, 13】, 3, 31, 9, 27, 5, 11【3, 6, 13】, 31, 9, 27, 5, 11【3, 6, 13，31】, 9, 27, 5, 11【3, 6, 9, 13，31】, 27, 5, 11【3, 6, 9, 13，27, 31】, 5, 11【3, 5, 6, 9, 13，27, 31】, 11【3, 5, 6, 9, 11，13，27, 31】 在已构成的有序表中线性查找，并在在已构成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。适当位置插入，把原来位置上的元素向后顺移。例例2 2：关键字序列：关键字序列

8、T= T= 2121，2525，4949，2525* *，1616，0808，请写出直接插入排序的详细实现过程。请写出直接插入排序的详细实现过程。* *表示后一个表示后一个25250 1 2 3 4 5 6254925*1608解：假设该序列已存入一维数组解：假设该序列已存入一维数组V7V7中，将中，将V0V0作为缓冲或作为缓冲或暂存单元暂存单元TempTemp。那么程序执行过程为：。那么程序执行过程为：初态：初态：时间效率：时间效率： O(n2)由于在最坏情况下，一切元素的比较由于在最坏情况下，一切元素的比较次数总和为次数总和为01n-1)O(n2)。其他情况。其他情况下还要加上挪动元素的次

9、数。下还要加上挪动元素的次数。 空间效率：空间效率：O1由于仅占用由于仅占用1个缓冲单元个缓冲单元算法的稳定性：稳定算法的稳定性：稳定由于由于25*排序后依然在排序后依然在25的后面。的后面。 对应程序参见教材对应程序参见教材P265。111122142221nininnniRMNnnniKCN/)()( ,/)(22优点：比较的次数大大减少，全部元素比较次数仅为优点：比较的次数大大减少，全部元素比较次数仅为O(nlog2n)。时间效率：虽然比较次数大大减少，惋惜挪动次数并未减少，时间效率：虽然比较次数大大减少，惋惜挪动次数并未减少，所以排序效率仍为所以排序效率仍为O(n2) 。空间效率：空间

10、效率： O1稳定性：稳定稳定性：稳定 对应程序见教材对应程序见教材P267仅用于顺序表仅用于顺序表新元素插入到哪里？新元素插入到哪里？讨论：假设记录是链表构造，用直接插入排序行否？折半插讨论：假设记录是链表构造，用直接插入排序行否？折半插入排序呢？入排序呢？答：直接插入不仅可行，而且还无需挪动元素，时间效率更答：直接插入不仅可行，而且还无需挪动元素，时间效率更高！自测卷上有对应的程序设计题。高！自测卷上有对应的程序设计题。 在已构成的有序表中折半查找，并在适在已构成的有序表中折半查找，并在适当位置插入，把原来位置上的元素向后顺移。当位置插入，把原来位置上的元素向后顺移。回想：回想： 链表排序链

11、表排序排序时只挪动指针；排序时只挪动指针； 地址排序地址排序排序时先挪动地址，最后再挪动记录。排序时先挪动地址，最后再挪动记录。1例：关键字序列例：关键字序列 T=(21 T=(21，2525，4949，2525* *，1616，0808， 请写出表插入排序的详细实现过程。请写出表插入排序的详细实现过程。解：假设该序列构造类型解：假设该序列构造类型) )已存入一维数组已存入一维数组V7V7中，将中，将V0V0作为表头结点。那么算法执行过程为：作为表头结点。那么算法执行过程为：i 关键字关键字 Vi.key指针指针 Vi.link0 MaxNum1212253494 25*516608指向第指向

12、第1 1个元素个元素指向头结点指向头结点03002* *表示后一个表示后一个2525int LinkInsertSort ( staticlinklis & list ) list.v0.Key = MaxNum; list.v0. Link = 1; list.v1.Link = 0; /构成循环链表构成循环链表for ( int i = 2; i = list.length; i+ ) int current = list.v0. Link; /current=当前记录指针当前记录指针 int pre = 0; /pre=当前记录当前记录current的前驱指针的前驱指针 whil

13、e ( list.vcurrent. Key link)list.vi. Link = current; /新记录新记录vi找到适宜序位开场插入找到适宜序位开场插入 list.vpre. Link = i; /在在pre与与current之间链入之间链入 表插入排序算法分析：表插入排序算法分析： 无需挪动记录，只需修正无需挪动记录，只需修正2n次指针值。但由于比较次指针值。但由于比较次数没有减少，故时间效率仍为次数没有减少，故时间效率仍为O(n2) 。 空间效率一定低，由于增开了指针分量但在运算空间效率一定低，由于增开了指针分量但在运算过程中没有用到更多的辅助单元。过程中没有用到更多的辅助单元

14、。 稳定性：稳定性：25和和25*排序前后次序未变，稳定。排序前后次序未变，稳定。讨论：此算法得到的只是一个有序链表，查找记录时只讨论：此算法得到的只是一个有序链表，查找记录时只能满足顺序查找方式。能满足顺序查找方式。改良：可以根据表中指针线索，很快对一切记录重排，改良：可以根据表中指针线索，很快对一切记录重排，构成真正的有序表顺序存储方式，从而能满足构成真正的有序表顺序存储方式，从而能满足折半查找方式。详细实现见教材折半查找方式。详细实现见教材P269。38例：关键字序列例：关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04，请写出希尔排序的详细实现过程

15、。，请写出希尔排序的详细实现过程。0123456789104938659776132749*5504初态：初态：第第1趟趟 (dk=5)第第2趟趟 (dk=3)第第3趟趟 (dk=1)4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 算法分析：开场时算法分析：开场时dk dk 的值较大，子序列中的对象较少，排序速度的值较大，子序列中的对象较少，排序速度较快；随着排序进展，较快；随着排序进展，

16、dk dk 值逐渐变小，子序列中对象个值逐渐变小，子序列中对象个数逐渐变多，由于前面任务的根底，大多数对象已根本有数逐渐变多，由于前面任务的根底，大多数对象已根本有序，所以排序速度依然很快。序，所以排序速度依然很快。void ShellSort(SqList &L，int dlta ，int t) /按增量序列按增量序列dlta0t-1对顺序表对顺序表L作作Shell排序排序 for(k=0；kt；+k) ShellSort(L，dltak)； /增量为增量为dltak的一趟插入排序的一趟插入排序 / ShellSort时间效率：时间效率：空间效率：空间效率：O O1 1由于仅占用由于

17、仅占用1 1个缓冲单元个缓冲单元算法的稳定性：不稳定算法的稳定性：不稳定由于由于4949* *排序后却到了排序后却到了4949的前面的前面参见教材参见教材P272P272dkdk值依次装在值依次装在dltatdltat中中void ShellInsert(SqList &L，int dk) for(i=dk+1；i=L.length； + i) if(ri.key 0 &(r0.keyrj.key); j=j-dk) rj+dk=rj； rj+dk=r0； 参见教材参见教材P272P272/对顺序表对顺序表L进展一趟增量为进展一趟增量为dk的的Shell排序，排序，dk为步长因

18、子为步长因子/开场将开场将ri 插入有序增量子表插入有序增量子表/暂存在暂存在r0/关键字较大的记录在子表中后移关键字较大的记录在子表中后移/在本趟终了时将在本趟终了时将ri插入到正确位置插入到正确位置课堂练习：课堂练习：1. 欲将序列欲将序列Q, H, C, Y, P, A, M, S, R, D, F, X中的关键码按中的关键码按字母升序重排，那么初始步长为字母升序重排，那么初始步长为4的希尔排序一趟的结果是？的希尔排序一趟的结果是？答：原始序列：答：原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shell一趟后：一趟后：2. 以关键字序列以关键字序列2

19、56，301，751，129，937，863，742，694，076，438为例，分别写出执行以下算法的各趟排序终了时，关为例，分别写出执行以下算法的各趟排序终了时，关键字序列的形状，并阐明这些排序方法中，哪些易于在链表包键字序列的形状，并阐明这些排序方法中，哪些易于在链表包括各种单、双、循环链表上实现？括各种单、双、循环链表上实现？ 直接插入排序直接插入排序 希尔排序取希尔排序取dk=5,3,1P,Q,R,A,D,H,C,F,M,S,X ,Y答：显然，直接插入排序方法易于在链表上实现；但希尔排答：显然，直接插入排序方法易于在链表上实现；但希尔排序方法由于是按增量选择记录，不易于在链表上实现。

20、序方法由于是按增量选择记录，不易于在链表上实现。 两种排序方法的中间形状分别描画如后：两种排序方法的中间形状分别描画如后：原始序列：原始序列： 256，301，751，129，937，863，742，694，076，438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438129129，256256，301301，751751，937937，863863，742742，69

21、4694，076076，438438129129，256256，301301，751751，937937，863863，742742，694694，076076，438438129129，256256，301301，751751，863863，937937，742742，694694，076076，438438129129，256256，301301，742742，751751，863863，937937，694694，076076，438438129129，256256，301301，694694，742742，751751，863863，937937，076076，438438076076

22、，129129，256256，301301，694694，742742，751751，863863，937937，438438076076，129129，256256，301301，438438，694694，742742，751751，863863，937937第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟第第6趟趟第第7趟趟第第8趟趟第第9趟趟原始序列：原始序列： 256，301，751，129，937，863，742，694，076，438256256，301301，751751，129129，937937，863863，742742，694694，076076，4384382562

23、56，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，694694，129129，937937，863863，742742，751751，076076，438438256256，301301，694694，076076，937937，863863，742742，751751，129129，438438256256，301301，694694，076076，438438，863863，742742，751751，129129，937937第第1趟趟dk=5第第2趟趟dk=3第第3趟趟dk=12

24、56256，301301，694694，076076，438438，863863，742742，751751，129129，937937256256，301301，694694，076076，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，694694，2562

25、56，438438，863863，742742，751751，129129，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，129129，256256，301301，438438，694694，742742，

26、751751，863863，9379379.3 9.3 交换排序交换排序交换排序的主要算法有：交换排序的主要算法有： 1) 冒泡排序冒泡排序 2) 快速排序快速排序 1) 冒泡排序冒泡排序根本思绪：每趟不断将记录两两比较，并按根本思绪：每趟不断将记录两两比较，并按“前小后大前小后大或或“前大后小规那么交换。前大后小规那么交换。优点：每趟终了时，不仅能挤出一个最大值到最后面位置，优点：每趟终了时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提早终了排序。生，还可以提早终了排序。前提：顺序存储构造前提：顺序存储

27、构造 例：关键字序列例：关键字序列 T=(21，25，49，25*，16，08，请写出，请写出冒泡排序的详细实现过程。冒泡排序的详细实现过程。21，25，49， 25*，16， 0821，25，25*，16， 08 ， 4921，25， 16， 08 ，25*，4921，16， 08 ，25， 25*，4916，08 ，21， 25， 25*，4908，16， 21， 25， 25*，49初态：初态：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟冒泡排序的算法分析冒泡排序的算法分析详细分析：详细分析：最好情况：初始陈列曾经有序，只执行一趟起泡，做最好情况：初始陈列曾经有序，只执行一趟起泡，

28、做 n-1 次关键码比较，不挪动对象。次关键码比较，不挪动对象。最坏情形：初始陈列逆序，算法要执行最坏情形：初始陈列逆序，算法要执行n-1趟起泡，第趟起泡，第i趟趟(1 i n) 做了做了n- i 次关键码比较，执行了次关键码比较，执行了n-i 次对象交换。次对象交换。此时的比较总次数此时的比较总次数KCN和记录挪动次数和记录挪动次数RMN为：为：11111233121nininninRMNnninKCN)()()()( )，设以首元素为枢轴中心设以首元素为枢轴中心例例1：关键字序列：关键字序列 T=(21，25，49，25*，16，08，请写出快速排序的算法步骤。请写出快速排序的算法步骤。2

29、1， 25， 49， 25*，16， 08初态：初态：第第1趟：趟：第第2趟：趟：第第3趟：趟：08，16，21，25， 25*，(49)2116，08，( )25，25*，49(08)，16，21，25，(25*，49)编程时：编程时：每一趟的子表的构成是采用从两头向中间交替式逼近法；每一趟的子表的构成是采用从两头向中间交替式逼近法；由于每趟中对各子表的操作都类似，主程序可采用递归算法。由于每趟中对各子表的操作都类似，主程序可采用递归算法。见教材见教材P275int Partition(SqList &L,int low,int high) /int Partition(SqList

30、 &L,int low,int high) /一趟快排一趟快排/交换子表交换子表 rlowhigh rlowhigh的记录，使支点枢轴记录到位，并的记录，使支点枢轴记录到位，并前往其位置。前往时，在支点之前的记录均不大于它，支点之后的前往其位置。前往时，在支点之前的记录均不大于它，支点之后的记录均不小于它。记录均不小于它。 r0=rlow; /r0=rlow; /以子表的首记录作为支点记录，放入以子表的首记录作为支点记录，放入r0r0单元单元续下页续下页一趟快速排序算法针对一个子表的操作一趟快速排序算法针对一个子表的操作pivotkey=rlow.key; /pivotkey=rlow

31、.key; /取支点的关键码存入取支点的关键码存入pivotkeypivotkey变量变量while(low high) while(low high) /从表的两端交替地向中间扫描从表的两端交替地向中间扫描while(low=pivotkey ) - -high;while(low=pivotkey ) - -high; rlow=rhigh; / rlow=rhigh; /将比支点小的记录交换到低端；将比支点小的记录交换到低端；while(lowhigh & rlow.key=pivotkey) + +low;while(lowhigh & rlow.key=pivotke

32、y) + +low; rhigh=rlow; / rhigh=rlow; /将比支点大的记录交换到高端；将比支点大的记录交换到高端； rlow=r0; /rlow=r0; /支点记录到位；支点记录到位；return low; /return low; /前往支点记录所在位置。前往支点记录所在位置。/Partition/Partition例例2：关键字序列：关键字序列 T=(21，25，49，25*，16，08，请写，请写出快速排序算法的一趟实现过程。出快速排序算法的一趟实现过程。ri0123456初态初态21254925*1608第第1趟趟highhighlowlow210825164925*

33、321pivotkey=21pivotkey=2108251649( 08 ，16 21 25* ， 49， 25 j从高端扫描从高端扫描寻觅小于寻觅小于pivot的元素的元素i从低端扫描从低端扫描寻觅大于寻觅大于pivot的元素的元素i=low; j=high;r0=rlow; pivot=rlow.key;i ji =pivot-j;ri = rj;i j &ri.key=pivot-i;rj = ri;ri = r0;return ok;void QSort ( SqList &L, int low, int high ) if ( low 1/对顺序表对顺序表L中的子序

34、列中的子序列r lowhigh 作快速排序作快速排序/一趟快排，将一趟快排，将r 一分为二一分为二/在左子区间进展递归快排，直到长度为在左子区间进展递归快排，直到长度为1/在右子区间进展递归快排，直到长度为在右子区间进展递归快排，直到长度为1/QSort新的新的low例例3：以关键字序列：以关键字序列256，301，751，129，937，863，742，694，076，438为例，写出执行快速算法的各趟排序为例，写出执行快速算法的各趟排序终了时，关键字序列的形状。终了时，关键字序列的形状。原始序列：原始序列： 256，301，751，129，937，863，742，694，076，438第第

35、1趟趟第第2趟趟第第3趟趟第第4趟趟256256，301301，751751，129129，937937，863863，742742，694694，076076，438438要求模拟算法实现步骤要求模拟算法实现步骤076076301301129129751751快速排序是递归的，需求有一个栈存放每层递归调用时的指快速排序是递归的，需求有一个栈存放每层递归调用时的指针和参数新的针和参数新的lowlow和和highhigh。可以证明，函数可以证明，函数quicksortquicksort的平均计算时间也是的平均计算时间也是O(nlog2n)O(nlog2n)。实验结果阐明：就平均计算时间而言，快速

36、排序是我们所讨实验结果阐明：就平均计算时间而言，快速排序是我们所讨论的一切内排序方法中最好的一个。论的一切内排序方法中最好的一个。最大递归调用层次数与递归树的深度一致，理想情况为最大递归调用层次数与递归树的深度一致，理想情况为 log2(n+1)log2(n+1) 。因此，要求存储开销为。因此，要求存储开销为 o(log2n)o(log2n)。假设每次划分对一个对象定位后，该对象的左侧子序列与右假设每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度一样，那么下一步将是对两个长度减半的子侧子序列的长度一样，那么下一步将是对两个长度减半的子序列进展排序，这是最理想的情况。此时，快速排序

37、的趟数序列进展排序，这是最理想的情况。此时，快速排序的趟数最少。最少。在最坏的情况，即待排序对象序列曾经按其关键码从小在最坏的情况，即待排序对象序列曾经按其关键码从小到大排好序的情况下，其递归树成为单支树，每次划分只到大排好序的情况下，其递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列。这样，必需经过得到一个比上一次少一个对象的子序列。这样，必需经过 n-1 n-1 趟才干把一切对象定位，而且第趟才干把一切对象定位，而且第 i i 趟需求经过趟需求经过 n-i n-i 次关键码比较才干找到第次关键码比较才干找到第 i i 个对象的安放位置，总的关个对象的安放位置，总的关键码比较次

38、数将到达键码比较次数将到达n2/2n2/2 快速排序是一个不稳定的排序方法快速排序是一个不稳定的排序方法设每个子表的支点都在中间比较平衡，那么：设每个子表的支点都在中间比较平衡，那么：第第1 1趟比较，可以确定趟比较，可以确定1 1个元素的位置；个元素的位置；第第2 2趟比较趟比较2 2个子表，可以再确定个子表，可以再确定2 2个元素的位置；个元素的位置；第第3 3趟比较趟比较4 4个子表，可以再确定个子表，可以再确定4 4个元素的位置；个元素的位置；第第4 4趟比较趟比较8 8个子表，可以再确定个子表，可以再确定8 8个元素的位置；个元素的位置； 只需只需log2nlog2n 1 1趟便可排

39、好序。趟便可排好序。而且，每趟需求比较和挪动的元素也呈指数下降，加上编程而且，每趟需求比较和挪动的元素也呈指数下降，加上编程时运用了交替逼近技巧，更进一步减少了挪动次数，所以速度时运用了交替逼近技巧，更进一步减少了挪动次数，所以速度特别快。特别快。教材教材P276P276有证明：快速排序的平均排序效率为有证明：快速排序的平均排序效率为O(nlog2n)O(nlog2n)；但最坏情况但最坏情况( (例如曾经有序例如曾经有序) )下仍为下仍为O(n2),O(n2),改良措施见改良措施见P277P277。 假设它不是这组对象中的第一个对象假设它不是这组对象中的第一个对象, 那么将它与这组对象中的第一

40、个对象对那么将它与这组对象中的第一个对象对调调; 在这组对象中剔除这个具有最小排序码在这组对象中剔除这个具有最小排序码的对象。在剩下的对象的对象。在剩下的对象Vi+1Vn-1中中反复执行第、步反复执行第、步, 直到剩余对象只需直到剩余对象只需一个为止。一个为止。0 1 2 3 4 5最小者最小者 08交换交换21,08最小者最小者 16交换交换25,16最小者最小者 21交换交换49,210 1 2 3 4 5结果结果最小者最小者 25*无交换无交换最小者最小者 25无交换无交换各趟排序后的结果各趟排序后的结果0 1 2 3 4 5i =1时选择排序的过程时选择排序的过程i k j i k j

41、 i k j 0 1 2 3 4 5i k j 20211ninninKCN)()( 构成初始胜者树最小关键码上升到根输出冠军并调整胜者树后树的形状输出冠军并调整胜者树后树的形状输出亚军并调整胜者树后树的形状输出亚军并调整胜者树后树的形状输出第三名并调整胜者树后树的形状输出第三名并调整胜者树后树的形状输出第四名并调整胜者树后树的形状输出第四名并调整胜者树后树的形状全部竞赛结果输出时树的形状全部竞赛结果输出时树的形状 int bottomRowSize = PowerOfTwo ( n ); /乘幂乘幂值值 int TreeSize = 2*bottomRowSize-1; /总结点个总结点个数

42、数 int loadindex = bottomRowSize-1; /内结点个内结点个数数 tree = new DataNodeTreeSize; int j = 0; /从从 a 向胜者树外结点复制数据向胜者树外结点复制数据 for ( int i = loadindex; i TreeSize; i+) treei.index = i; if ( j n ) treei.active = 1; treei.data = aj+; else treei.active = 0; i = loadindex; /进展初始比较选择最小的进展初始比较选择最小的项项 while ( i ) j =

43、 i; while ( j 2*i ) if ( !treej+1.active| /胜者送入双亲 treej.data = treej+1.data ) tree(j-1)/2 = treej; else tree(j-1)/2 = treej+1; j += 2; i = (i-1)/2; / i 退到双亲, 直到 i=0为止 for ( i = 0; i n-1; i+) /处置其它n-1个数据 ai = tree0.data; /送出最小数据 treetree0.index.active = 0; /失去参选资历 UpdateTree ( tree, tree0.index ); /调

44、整 an-1 = tree0.data; 锦标赛排序中的调整算法template void UpdateTree ( DataNode *tree, int i ) if ( i % 2 = 0 ) tree(i-1)/2 = treei-1; /i偶数, 对手左结点 else tree(i-1)/2 = treei+1; /i奇数, 对手右结点 i = (i-1) / 2; /向上调整 while ( i ) /直到直到 i=0 if ( i %2 = 0) j = i-1; else j = i+1; if ( !treei.active | !treej.active ) if ( tr

45、eei.active ) tree(i-1)/2 = treei; /i可参选可参选, i上上 else tree(i-1)/2 = treej; /否那么否那么, j上上 else/两方都可参选两方都可参选 if ( treei.data treej.data ) tree(i-1)/2 = treei; /关键码小者上关键码小者上 else tree(i-1)/2 = treej; i = (i-1) / 2; / i上升到双亲上升到双亲 123456136542123456136542Type SqList HeapType;Void HeapAdjust (HeapType &

46、 H, int s,int m) rc = H.rs ; for (j = 2*s; j=m ;j* =2) if (jm & LT(H.rj.key,H.rj +1.key ) +j; if( !LT( rc.key, H.rj.key) break; H.rs = H.rj ; s = j ; H.rs = rc ;1234561365421234561365421234561365421234561365421234561365422022kiiik1 1njnjjikkjkjjjkkjjkkii4 411111111202222222122)( if ( InitListi =

47、 InitListj ) mergedList k = InitListi; i+; k+; else mergedList k = InitListj; j+; k+; while ( i = mid ) mergedListk = InitListi; i+; k+; while ( j = right ) mergedListk = InitListj; j+; k+; void MergePass ( SortData initList , SortData mergedList , int len ) int i = 0; while (i+2*len-1 = n-1) merge(

48、 initList, mergedList, i, i+len-1, i+2*len-1); i += 2 * len; /循环两两归并循环两两归并 if ( i+len = n-1 ) merge( initList, mergedList, i, i+len-1, n-1); else for ( int j = i; j = n-1; j+) mergedList j = initListj; n设算法中参与归并的两个归并段是设算法中参与归并的两个归并段是 Aleft Amid 和和 Amid+1Aright，归并后，归并后结果归并段放在原地。结果归并段放在原地。08 16temp =

49、72temp = 72temp = 7221 3725 37temp = 62temp = 6249 54终了typedef int SortData;void merge( SortData A , int left, int mid, int right ) int i, j; SortData temp; for ( i = left; i Amid+1 ) temp = Amid; for ( j = mid-1; j = i; j- ) Aj+1 = Aj; Ai = Amid+1; if ( temp = Amid+2 ) Amid+1 = temp; else for ( j =

50、 mid+2; j Aj ) Aj-1 = Aj;else Aj-1 = temp; break; 9.6 基数排序基数排序(Radix Sorting) 前边将过的各种排序方法主要是经过关键字的比较和前边将过的各种排序方法主要是经过关键字的比较和记录的移记录的移动完成的。而动完成的。而 基数排序，不需求进展记录关键字的比较。基数排序，不需求进展记录关键字的比较。它是借助它是借助多关键字排序的思想对单逻辑关键字进展排序的方法。多关键字排序的思想对单逻辑关键字进展排序的方法。 多关键字排序通常有两种方法其一多关键字排序通常有两种方法其一 称为最高位优先法称为最高位优先法(Most Significant Digit first)简称简称MSD；其二是从最地次位关键；其二是从最地次位关键字起进展排字起进展排序。然后再对高一位的关键字进展排序，直到最高位，这序。然后再对高一位的关键字进展排序，直到最高位，这种称为最种称为最低位优先法低位优先法(Least Significant Digit first)简称简称LSD。 基数排序是借助基数排序是借助“分配和分配和“搜集两种操作对单逻辑搜集两种操作对单逻辑关键字进展排关键字进展排序的一种内排序方法。根据在实践工程中运用的关键字大序的一种内排序方法。根据