数据结构第9章排序

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

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

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

4、序表结构的( (便于直接移动元素便于直接移动元素) )6. 6. 顺序存储（顺序表）的抽象数据类型如何表示？顺序存储（顺序表）的抽象数据类型如何表示？typedef struct /定义每个记录（数据元素）的结构定义每个记录（数据元素）的结构 keytype key ; /关键字关键字 infotype otherinfo; /其它数据项其它数据项recordtype ;typedef struct /定义顺序表的结构定义顺序表的结构 recordtype r maxsize +1 ; /存储顺序表的向量存储顺序表的向量 /r0/r0一般作哨兵或缓冲区一般作哨兵或缓冲区 int length

5、; /顺序表的长度顺序表的长度sqlist ;# define maxsize 20 /设记录不超过设记录不超过2020个个typedef int keytype ; /设关键字为整型量（设关键字为整型量（intint型）型）67. 内部排序的算法有哪些？内部排序的算法有哪些？按排序的规则不同，可分为按排序的规则不同，可分为5类：类：插入排序插入排序交换排序（重点是快速排序）交换排序（重点是快速排序）选择排序选择排序归并排序归并排序基数排序基数排序d关键字的位数关键字的位数(长度长度)按排序算法的时间复杂度不同，可分为按排序算法的时间复杂度不同，可分为3类：类：简单的排序算法：时间效率低，简单

6、的排序算法：时间效率低，o(n2)先进的排序算法先进的排序算法: 时间效率高，时间效率高，o( nlog2n )基数排序算算法：时间效率高，基数排序算算法：时间效率高，o( dn)79.2 9.2 插入排序插入排序插入排序有多种具体实现算法：插入排序有多种具体实现算法： 1) 直接插入排序直接插入排序 2) 折半插入排序折半插入排序 3) 2-路插入排序路插入排序 4) 表插入排序表插入排序 5) 希尔排序希尔排序8新元素插入到哪里？新元素插入到哪里？例例1 1：关键字序列关键字序列t=（13，6，3，31，9，27，5，11），）， 请写出直接插入排序的中间过程序列。请写出直接插入排序的中间

7、过程序列。【13】, 6, 3, 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】 在已形成的在已形成的有序表中有序表中线性查找线性查找，并在，并在适当位置插入，把原来位置上的元素向后适当位置插入，把原来位置上的元素向后顺移顺移。9例例

8、2 2：关键字序列关键字序列t= （21，25，49，25*，16，08），），请写出直接插入排序的具体实现过程。请写出直接插入排序的具体实现过程。* *表示后一个表示后一个25250 1 2 3 4 5 6252525494949252525* * *161616080808解：解：假设该序列已存入一维数组假设该序列已存入一维数组v7v7中，将中，将v0v0作为缓冲或作为缓冲或暂存单元（暂存单元（temptemp）。则程序执行过程为：）。则程序执行过程为：初态：初态：时间效率：时间效率： 因为在最坏情况下，所有元素的比较因为在最坏情况下，所有元素的比较次数总和为（次数总和为（0 01 1n-

9、1)o(nn-1)o(n2 2) )。其他情况。其他情况下还要加上移动元素的次数。下还要加上移动元素的次数。 空间效率：空间效率：因为仅占用因为仅占用1 1个缓冲单元个缓冲单元算法的稳定性：算法的稳定性：因为因为2525* *排序后仍然在排序后仍然在2525的后面。的后面。 对应程序参见教材对应程序参见教材p265p265。1011111122142221nininnnirmnnnnikcn/)()( ,/)(221213优点：优点：比较的次数大大减少，全部元素比较次数仅为比较的次数大大减少，全部元素比较次数仅为o(nlogo(nlog2 2n)n)。时间效率：时间效率：虽然比较次数大大减少，

10、可惜移动次数并未减少，虽然比较次数大大减少，可惜移动次数并未减少，所以排序效率仍为所以排序效率仍为o(no(n2 2) ) 。空间效率：空间效率： o o（1 1）稳定性：稳定性：稳定稳定新元素插入到哪里？新元素插入到哪里？讨论：讨论：若记录是链表结构，用直接插入排序行否？折半插入若记录是链表结构，用直接插入排序行否？折半插入排序呢？排序呢？答：答：直接插入不仅可行，而且还无需移动元素，时间效率更直接插入不仅可行，而且还无需移动元素，时间效率更高！高！自测卷上有对应的程序设计题。自测卷上有对应的程序设计题。 在已形成的在已形成的有序表中有序表中折半查找折半查找，并在适，并在适当位置插入，把原来

11、位置上的元素向后当位置插入，把原来位置上的元素向后顺移顺移。1415回忆：回忆： 链表排序链表排序排序时只移动指针；排序时只移动指针； 地址排序地址排序排序时先移动地址，最后再移动记录。排序时先移动地址，最后再移动记录。161例：例：关键字序列关键字序列 t=(21，25，49，25*，16，08），）， 请写出表插入排序的具体实现过程。请写出表插入排序的具体实现过程。解：解：假设该序列（结构类型假设该序列（结构类型) )已存入一维数组已存入一维数组v7v7中，将中，将v0v0作为表头结点。则作为表头结点。则算法执行过程算法执行过程为：为：i0123456关键字关键字 vi.key maxnu

12、m212549 25*1608指针指针 vi.link指向第指向第1 1个元素个元素指向头结点指向头结点03002* *表示后一个表示后一个252517int 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=/current=当前记录指针当前记录指针 int p

13、re = 0; /pre=/pre=当前记录当前记录current的前驱指针的前驱指针 while ( list.vcurrent. key linkp=p-link) )list.vi. link = current; /新记录新记录vi找到合适序位开始插入找到合适序位开始插入 list.vpre. link = i; /在在prepre与与currentcurrent之间链入之间链入 18表插入排序算法分析：表插入排序算法分析： 无需移动记录，只需修改无需移动记录，只需修改2n次指针值。但由于比较次指针值。但由于比较次数没有减少，故次数没有减少，故时间效率仍为时间效率仍为o(n2) 。 空

14、间效率肯定低空间效率肯定低，因为增开了指针分量（但在运算，因为增开了指针分量（但在运算过程中没有用到更多的辅助单元）。过程中没有用到更多的辅助单元）。 稳定性：稳定性：25和和25*排序前后次序未变，排序前后次序未变，稳定稳定。讨论：讨论：此算法得到的只是一个有序链表，查找记录时只此算法得到的只是一个有序链表，查找记录时只能满足顺序查找方式。能满足顺序查找方式。改进：改进：可以根据表中指针线索，很快对所有记录重排，可以根据表中指针线索，很快对所有记录重排，形成形成真正的有序表（顺序存储方式），从而能满足真正的有序表（顺序存储方式），从而能满足折半查找方式。折半查找方式。具体实现见教材具体实现见

15、教材p269。19）2038例：例：关键字序列关键字序列 t=(49，38，65，97, 76, 13, 27, 49*，55, 04），），请写出希尔排序的具体实现过程。请写出希尔排序的具体实现过程。0149238365497576613727849*9551004初态：初态：第第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

16、 97 算法分析：算法分析：开始时开始时dk 的值较大，子序列中的对象较少，排序速度的值较大，子序列中的对象较少，排序速度较快；随着排序进展，较快；随着排序进展，dk 值逐渐变小，子序列中对象个数值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。所以排序速度仍然很快。21void shellsort(sqlist &l，int dlta ，int t) /按增量序列按增量序列dlta0t-1对顺序表对顺序表l作作shell排序排序 for(k=0；kt；+k) shellsort(l

17、，dltak)； /增量为增量为dltak的一趟插入排序的一趟插入排序 / shellsort时间效率：时间效率：空间效率：空间效率：因为仅占用因为仅占用1 1个缓冲单元个缓冲单元算法的稳定性：算法的稳定性：因为因为4949* *排序后却到了排序后却到了4949的前面的前面参见教材参见教材p272p272经验公式经验公式dkdk值依次装在值依次装在dltadltat t 中中2223void shellinsert(sqlist &l，int dk) for(i=dk+1；i=l.length； + i) if(ri.key 0 &(r0.keyrj.key); j=j-dk)

18、 rj+dk=rj； rj+dk=r0； 参见教材参见教材p272p272/对顺序表对顺序表l进行一趟增量为进行一趟增量为dk的的shell排序，排序，dk为步长因子为步长因子/开始将开始将ri 插入有序增量子表插入有序增量子表/暂存在暂存在r0/关键字较大的记录在子表中后移关键字较大的记录在子表中后移/在本趟结束时将在本趟结束时将ri插入到正确位置插入到正确位置24课堂练习：课堂练习：1. 欲将序列（欲将序列（q, h, c, y, p, a, m, s, r, d, f, x）中的关键码按）中的关键码按字母升序重排，则初始步长为字母升序重排，则初始步长为4的希尔排序一趟的结果是？的希尔排序

19、一趟的结果是？答：答：原始序列：原始序列： q, h, c, y, p, a, m, s, r, d, f, x shellshell一趟后：一趟后：2. 以关键字序列（以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的）为例，分别写出执行以下算法的各趟各趟排序结束时，关排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？括各种单、双、循环链表）上实现？ 直接插入排序直接插入排序 希尔排序（取希尔排序（取dk=5,3,

20、1）p,q,r,a,d,h,c,f,m,s,x ,y答：答：显然，直接插入排序方法易于在链表上实现；但希尔排显然，直接插入排序方法易于在链表上实现；但希尔排序方法因为是按增量选择记录，不易于在链表上实现。序方法因为是按增量选择记录，不易于在链表上实现。 两种排序方法的中间状态分别描述如后：两种排序方法的中间状态分别描述如后：25原始序列：原始序列： 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438 256256，301301 ，751751，129129，937937，863863，742742，6946

21、94，076076，438438 256256，301301，751751 ，129129，937937，863863，742742，694694，076076，438438 129129，256256，301301，751751 ，937937，863863，742742，694694，076076，438438 129129，256256，301301，751751，937937 ，863863，742742，694694，076076，438438 129129，256256，301301，751751，863863，937937 ，742742，694694，076076，438438

22、 129129，256256，301301，742742，751751，863863，937937 ，694694，076076，438438 129129，256256，301301，694694，742742，751751，863863，937937 ，076076，438438 076076，129129，256256，301301，694694，742742，751751，863863，937937 ，438438 076076，129129，256256，301301，438438，694694，742742，751751，863863，937937 第第1趟趟第第2趟趟第第3趟趟第

23、第4趟趟第第5趟趟第第6趟趟第第7趟趟第第8趟趟第第9趟趟26原始序列：原始序列： 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，694694，129129，937937，863863，742742，75

24、1751，076076，438438256256，301301，694694，076076，937937，863863，742742，751751，129129，438438256256，301301，694694，076076，438438，863863，742742，751751，129129，937937第第1趟趟dk=5dk=5第第2趟趟dk=3dk=3第第3趟趟dk=1dk=1256256，301301，694694，076076，438438，863863，742742，751751，129129，937937256256，301301，694694，076076，438438，8

25、63863，742742，751751，129129，937937076076，301301，694694，256256，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，129129，256256，438438，694694，742742，751751，8638

26、63，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，751751，863863，937937279.3 9.3 交换排序交换排序交换排序的主要算法有：交换排序的主要算法有： 1) 冒泡排序冒泡排序 2) 快速排序快速排序28 1) 基本思路：基本思路：每趟不断

27、将记录两两比较，并按每趟不断将记录两两比较，并按“前小后大前小后大”（或（或“前大后小前大后小”）规则交换。）规则交换。优点：优点：每趟结束时，不仅能挤出一个最大值到最后面位置，每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。生，还可以提前结束排序。前提：前提：顺序存储结构顺序存储结构 例：例：关键字序列关键字序列 t=(21，25，49，25*，16，08），请写出），请写出冒泡排序的具体实现过程。冒泡排序的具体实现过程。21，25，49， 25*，16， 0821，25，25*，1

28、6， 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趟趟29冒泡排序的算法分析冒泡排序的算法分析详细分析：详细分析：最好情况：最好情况：初始排列已经有序，只执行一趟起泡，做初始排列已经有序，只执行一趟起泡，做 n- -1 次关键码比较，不移动对象。次关键码比较，不移动对象。最坏情形：最坏情形：初始排列逆序，初始排列逆序，算法要执行算法要执行n-1 1趟起泡，第趟起泡，第i趟趟(1 i n) 做了做了n-

29、 i 次关键码比较，执行了次关键码比较，执行了n-i 次对象交换。次对象交换。此时的比较总次数此时的比较总次数kcn和记录移动次数和记录移动次数rmn为：为：11111233121nininninrmnnninkcn)()()()(3031( )，设以首元素为枢轴中心设以首元素为枢轴中心例例1：关键字序列关键字序列 t=(21，25，49，25*，16，08），），请写出快速排序的算法步骤。请写出快速排序的算法步骤。21， 25， 49， 25*，16， 08初态：初态：第第1趟：趟：第第2趟：趟：第第3趟：趟：08，16，21，25， 25*，(49)2116，08，( )25，25*，49

30、(08)，16，21，25，(25*，49)32编程时：编程时：每一趟的子表的形成是采用从两头向中间交替式逼近法；每一趟的子表的形成是采用从两头向中间交替式逼近法；由于每趟中对各子表的操作都相似，主程序可采用递归算法。由于每趟中对各子表的操作都相似，主程序可采用递归算法。见教材见教材p275int int (sqlist &l,(sqlist &l,int lowint low, ,int highint high) ) /一趟快排一趟快排/交换子表交换子表 rlowrlowhighhigh的记录，使支点（枢轴）记录到位，并返回其位置。的记录，使支点（枢轴）记录到位，并返回其位

31、置。返回时，在支点之前的记录均不大于它，支点之后的记录均不小于它。返回时，在支点之前的记录均不大于它，支点之后的记录均不小于它。 r0=r0=rlowrlow; ; /以子表的首记录作为支点记录，放入以子表的首记录作为支点记录，放入r0r0单元单元（续下页）（续下页）一趟快速排序算法一趟快速排序算法（针对一个子表的操作）（针对一个子表的操作）33pivotkey=pivotkey=rlow.keyrlow.key; ; /取支点的关键码存入取支点的关键码存入pivotkeypivotkey变量变量while(low high)while(low high) /从表的两端交替地向中间扫描从表的两

32、端交替地向中间扫描while(while(lowhighlow=pivotkeyrhigh.key=pivotkey ) ) rlow=rhigh; rlow=rhigh; /将比支点小的记录交换到低端；将比支点小的记录交换到低端；while(while(lowhighlowhigh & & rlow.key=pivotkeyrlow.key=pivotkey) ) rhigh=rlow; rhigh=rlow; /将比支点大的记录交换到高端；将比支点大的记录交换到高端；rlow=r0; rlow=r0; /支点记录到位；支点记录到位；return low; return lo

33、w; /返回支点记录所在位置。返回支点记录所在位置。 /34例例2：关键字序列关键字序列 t=(21，25，49，25*，16，08），请写），请写出快速排序算法的一趟实现过程。出快速排序算法的一趟实现过程。ri初态初态第第1趟趟0121225349425*516608highhighlowlow210825164925*321pivotkey=pivotkey=212108251649( 08 ，16 ） 21 （ 25* ， 49， 25 ）35j从高端从高端扫描扫描寻找小于寻找小于pivot的元素的元素i从低端从低端扫描扫描寻找大于寻找大于pivot的元素的元素i=low; j=high

34、;r0=rlow; pivot=rlow.key;i ji =pivot-j;ri = rj;i j &ri.key=pivot-i;rj = ri;ri = r0;return ok;36void qsort ( sqlist &l, int low, int high ) if ( low 1/对顺序表对顺序表l中的子序列中的子序列r lowhigh 作快速排序作快速排序/一趟快排，将一趟快排，将r 一分为二一分为二/在左子区间进行递归快排，直到长度为在左子区间进行递归快排，直到长度为1/在右子区间进行递归快排，直到长度为在右子区间进行递归快排，直到长度为1/qsort新的

35、新的low 1, l.length 37例例3：以关键字序列（以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速算法的）为例，写出执行快速算法的各趟各趟排序排序结束时，关键字序列的状态。结束时，关键字序列的状态。原始序列：原始序列： 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438第第1趟趟第第2趟趟第第3趟趟第第4趟趟256256，301301，751751，129129，937937，863863，742742，694694，076076，

36、438438，129129，937937，863863，742742，694694，301301，438438要求模拟算法实现步骤要求模拟算法实现步骤076076301301129129751751，129129，438438，301301，694694，742742，694694，863863，937937，301301，694694，742742，937937，301301，301301，694694，742742，937937，742742，38快速排序是递归的，需要有一个栈存放每层递归调用时的指快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数针和参数（新的（新的lowlow

37、和和highhigh）。可以证明，函数可以证明，函数quicksort的平均计算时间也是的平均计算时间也是o(nlog2n)。实实验结果表明：就平均计算时间而言，快速排序是我们所讨论验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个的所有内排序方法中最好的一个。最大递归调用层次数与递归树的深度一致，理想情况为最大递归调用层次数与递归树的深度一致，理想情况为 log2(n+1) 。因此，要求存储开销为。因此，要求存储开销为 o(log2n)。如果每次划分对一个对象定位后，该对象的左侧子序列与右如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则

38、下一步将是对两个长度减半的子序侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。此时，快速排序的趟数最列进行排序，这是最理想的情况。此时，快速排序的趟数最少。少。39在最坏的情况，即待排序对象序列已经按其关键码从小在最坏的情况，即待排序对象序列已经按其关键码从小到大排好序的情况下，到大排好序的情况下，其递归树成为单支树其递归树成为单支树，每次划分只，每次划分只得到一个比上一次少一个对象的子序列。这样，必须经过得到一个比上一次少一个对象的子序列。这样，必须经过 n-1 趟才能把所有对象定位，而且第趟才能把所有对象定位，而且第 i 趟需要经过趟需要经过 n-i 次关

39、键码比较才能找到第次关键码比较才能找到第 i 个对象的安放位置，总的关键个对象的安放位置，总的关键码比较次数将达到码比较次数将达到n n2 2/2/2 快速排序是一个快速排序是一个不稳定不稳定的排序方法的排序方法40设每个子表的支点都在中间（比较均衡），则：设每个子表的支点都在中间（比较均衡），则：第第1 1趟比较，可以确定趟比较，可以确定1 1个元素的位置；个元素的位置；第第2 2趟比较（趟比较（2 2个子表），可以再确定个子表），可以再确定2 2个元素的位置；个元素的位置；第第3 3趟比较（趟比较（4 4个子表），可以再确定个子表），可以再确定4 4个元素的位置；个元素的位置；第第4 4趟

40、比较（趟比较（8 8个子表），可以再确定个子表），可以再确定8 8个元素的位置；个元素的位置； 只需只需 loglog2 2n n 1 1趟便可排好序。趟便可排好序。而且，每趟需要比较和移动的元素也呈指数下降，加上编程而且，每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技巧，更进一步减少了移动次数，所以速度时使用了交替逼近技巧，更进一步减少了移动次数，所以速度特别快。特别快。教材教材p276p276有证明：快速排序的平均排序效率为有证明：快速排序的平均排序效率为o(nlogo(nlog2 2n)n)；但最坏情况但最坏情况( (例如已经有序例如已经有序) )下仍为下仍为o(no(

41、n2 2),),改进措施见改进措施见p277p277。4142 430 1 2 3 4 5最小者最小者最小者最小者最小者最小者440 1 2 3 4 5结果结果最小者最小者最小者最小者各趟排序后的结果各趟排序后的结果45typedef int sortdata;void selectsort ( sortdata v , int n ) for ( int i = 0; i n-1; i+ ) int k = i; /选择具有最小排序码的对象 for ( int j = i+1; j n; j+) if ( vj vk ) k = j; /当前具最小排序码的对象 if ( k != i ) /

42、对换到第 i 个位置 swap ( vi, vk ); 460 1 2 3 4 5i =1时选择排序的过程时选择排序的过程i k j i k j i k j 470 1 2 3 4 5i k j 20211ninninkcn)()(48495051 形成初始胜者树（最小关键码上升到根）形成初始胜者树（最小关键码上升到根）52输出冠军并调整胜者树后树的状态输出冠军并调整胜者树后树的状态53输出亚军并调整胜者树后树的状态输出亚军并调整胜者树后树的状态54输出第三名并调整胜者树后树的状态输出第三名并调整胜者树后树的状态55输出第四名并调整胜者树后树的状态输出第四名并调整胜者树后树的状态56全部比赛结

43、果输出时树的状态全部比赛结果输出时树的状态57template class datanode public: type data; /数据值数据值 int index; /结点在满二叉树中顺序号结点在满二叉树中顺序号 int active; /参选标志：参选标志：=1, 参选参选, =0, 不参选不参选template void tournamentsort ( type a , int n ) datanode *tree; datanode item; 58 int bottomrowsize = poweroftwo ( n ); /乘幂值乘幂值 int treesize = 2*bot

44、tomrowsize-1; /总结点个数总结点个数 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; /进行初始比较选择最小的项进行初始

45、比较选择最小的项 while ( i ) 59 j = 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.ac

46、tive = 0; /失去参选资格失去参选资格 60 updatetree ( tree, tree0.index ); /调整调整 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; /向上调整向上调整 61 while ( i ) /直到直到 i=0 if ( i

47、%2 = 0) j = i-1; else j = i+1; if ( !treei.active | !treej.active ) if ( treei.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上升到双亲上升到双亲 626

48、364heapadjust651234561365426612345613654267type sqlist heaptype;void heapadjust (heaptype & h, int s,int m) rc = h.rs ; for (j = 2*s; j=m ;j* =2) if (j0 ;-i)（从最下层的分支结点向上）（从最下层的分支结点向上） heapadjust (h,i,h.length);69heapadjustheapadjust7012345613654271123456136542721234561365427312345613654274123456

49、13654275/对表对表h1到到hn进行排序进行排序, 使得表中各使得表中各/个对象按其关键码非递减有序。个对象按其关键码非递减有序。 void heapsort (heaptype & h ) for (i= h.length/2; i0 ;-i)（从最下层的分支结点向上）（从最下层的分支结点向上） heapadjust (h,i,h.length); for (i= h.length; i1 ; -i ) h.r1 h.ri ; heapadjust( h, 1, i-1);（从根结点向下）（从根结点向下） 76heapadjust2022kiiik1 177heapadjust

50、njnjjikkjkjjjkkjjkkii4 411111111202222222122)(7879808182typedef int sortdata;void merge ( sortdata initlist , sortdata mergedlist , int left, int mid, int right ) int i = left, j = mid+1, k = left; while ( i = mid & j = right ) /两两比较 if ( initlisti = initlistj ) mergedlist k = initlisti; i+; k+;

51、 else mergedlist k = initlistj; j+; k+; 83 while ( i = mid ) mergedlistk = initlisti; i+; k+; while ( j = right ) mergedlistk = initlistj; j+; k+; 8485void mergepass ( sortdata initlist , sortdata mergedlist , int len ) int i = 0; while (i+2*len-1 = n-1) merge( initlist, mergedlist, i, i+len-1, i+2*

52、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; 8687void mergesort ( sortdata initlist , int n ) /按对象排序码非递减的顺序对表中对象排序 sortdata templistn; int len = 1; while ( len n ) mergepass ( initlist, te

53、mplist, len ); len *= 2;mergepass ( templist, initlist, len ); len *= 2; 8889n设算法中参加归并的两个归并段是设算法中参加归并的两个归并段是 aleft amid 和和 amid+1 aright，归并后结，归并后结果归并段放在原地。果归并段放在原地。08 16temp = 7290temp = 72temp = 7221 3725 3791temp = 62temp = 6249 54结束92typedef int sortdata;void merge( sortdata a , int left, int mid

54、, 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; 93 else for ( j = mid+2; j aj ) aj-1 = aj;else aj-1 = temp; break; 9.6 基数排序基数排序(radix sorting) 前边将过的各种排序方法主要是通过关键字的比较和记录的移前边将过的各种排

55、序方法主要是通过关键字的比较和记录的移动完成的。而动完成的。而 基数排序，不需要进行记录关键字的比较。它是借助基数排序，不需要进行记录关键字的比较。它是借助多关键字排序的思想对单逻辑关键字进行排序的方法。多关键字排序的思想对单逻辑关键字进行排序的方法。 多关键字排序通常有两种方法其一多关键字排序通常有两种方法其一 称为最高位优先法称为最高位优先法(most significant digit first)简称简称msd；其二是从最地次位关键字起进行排；其二是从最地次位关键字起进行排序。然后再对高一位的关键字进行排序，直到最高位，这种称为最序。然后再对高一位的关键字进行排序，直到最高位，这种称为

56、最低位优先法低位优先法(least significant digit first)简称简称lsd。 基数排序是借助基数排序是借助“分配分配”和和“收集收集”两种操作对单逻辑关键字进行排两种操作对单逻辑关键字进行排序的一种内排序方法。根据在实际工程中使用的关键字大都是由数序的一种内排序方法。根据在实际工程中使用的关键字大都是由数字（或字母）组成的，现在，以数字为例来说明这种排序的过程。字（或字母）组成的，现在，以数字为例来说明这种排序的过程。我们知道数字关键字都是由我们知道数字关键字都是由0到到9十个数字组成，那么，在内存设立十个数字组成，那么，在内存设立编号为编号为09的十个桶。对待排序的记

57、录从其关键字的最低为到最高的十个桶。对待排序的记录从其关键字的最低为到最高位作如下处理：把每个记录存放（分配）到内存中桶号与该记录关位作如下处理：把每个记录存放（分配）到内存中桶号与该记录关键字当前数位上数字相同的桶中。经过处理（收集）得到一次排序键字当前数位上数字相同的桶中。经过处理（收集）得到一次排序结果。下面以顺序存储为例看一看实际过程。结果。下面以顺序存储为例看一看实际过程。 初始状态初始状态 278 109 063 930 589 184 505 269 008 183 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 269 083 008 589 930 063 184

58、 505 278 109 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 930 063 083 184 505 278 008 109 589 269 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 109 589 008 269 184 505 930 063 278 083 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 第二次第二次 505 008 109 930 063 269 278 083 184 589 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 083 063 184 278 589 008 109 269 505 930 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9第三次第三次 008 063 083 109 184 269 178 505 589 930第一次 由上面分析可知基数排序若用顺序存储，每个桶都要分配由上面分析可知基数排序若用顺序存储，每个桶都要分配n 个单个单元总的空间量应为元总的空间量应为10*n。但实际上根本用不了那么多，因尔造成。但实际上根本用不了那么多，因尔造成空间的极大浪费。所以，基数排序一般都采用链表存储。链表存空间的极大浪费。所以，基数排序一般