[哲学]C语言第十章课件.ppt

1、数据结构 第10章 内部排序学习目的与要求：学习目的与要求：1.1.深刻理解排序的定义和各种排序方法的特点深刻理解排序的定义和各种排序方法的特点,并能并能加以灵活应用加以灵活应用;2.2.熟练掌握各种排序方法的执行过程；熟练掌握各种排序方法的执行过程；3.3.熟练掌握各种排序方法的时间复杂度的分析方法，熟练掌握各种排序方法的时间复杂度的分析方法，从从“关键字间的比较次数关键字间的比较次数”分析排序算法的平均情况分析排序算法的平均情况和最坏情况的时间性能和最坏情况的时间性能;4.4.理解排序方法理解排序方法“稳定稳定”或或“不稳定不稳定”的含义，弄清的含义，弄清楚在什么情况下要求应用的排序方法必

2、须是稳定的。楚在什么情况下要求应用的排序方法必须是稳定的。数据结构 第10章 内部排序一、概述一、概述二、插入排序二、插入排序三、交换排序三、交换排序四、选择排序四、选择排序五、归并排序五、归并排序六、基数排序六、基数排序七、七、各种排序方法的比较各种排序方法的比较数据结构 第10章 内部排序一、概述一、概述1 1基本概念基本概念排序排序：将数据元素：将数据元素(或记录或记录)的一个任意序列的一个任意序列,重新排列重新排列成一个按关键字有序的序列。成一个按关键字有序的序列。排序方法的稳定性排序方法的稳定性：对关键字相同的数据元素，排：对关键字相同的数据元素，排序前后它们的领先关系保持不变，则称

3、该排序方法是序前后它们的领先关系保持不变，则称该排序方法是稳定的稳定的；反之，称该排序方法是；反之，称该排序方法是不稳定的不稳定的。内部排序内部排序：待排序记录存放在计算机的内存中进行：待排序记录存放在计算机的内存中进行的排序。的排序。数据结构 第10章 内部排序外部排序外部排序：待排序记录的数量很大，以致内存一次：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问不能容纳全部记录，在排序过程中尚需对外存进行访问的排序。的排序。排序的时间开销排序的时间开销：排序的时间开销是衡量算法好坏的排序的时间开销是衡量算法好坏的最重要的标志。最重要的标志。排序的时间开销可用

4、算法执行中的排序的时间开销可用算法执行中的数据数据比较次数比较次数与与数据移动次数数据移动次数来衡量。算法运行时间代价的来衡量。算法运行时间代价的估算一般都估算一般都按平均情况按平均情况进行估算。对于那些进行估算。对于那些受记录关键受记录关键字序列初始排列及记录个数影响较大的字序列初始排列及记录个数影响较大的，需要需要按最好情按最好情况况和和最坏情况最坏情况进行估算进行估算。数据结构 第10章 内部排序2 2排序的分类排序的分类按排序过程依据的不同原则进行分类：按排序过程依据的不同原则进行分类：交换排序交换排序选择排序选择排序归并排序归并排序计数排序计数排序插入排序插入排序按工作量进行分类：按

5、工作量进行分类：先进的排序方法，其时间复杂度为先进的排序方法，其时间复杂度为O(nlog2n)简单的排序方法简单的排序方法,其时间复杂度为其时间复杂度为O(n2)基数排序基数排序基数排序，其时间复杂度为基数排序，其时间复杂度为O(dn)数据结构 第10章 内部排序3 3排序的基本操作和记录的存储方式排序的基本操作和记录的存储方式排序过程中需要的两种基本操作：排序过程中需要的两种基本操作：（1）比较关键字的大小；）比较关键字的大小；（2）将记录从一个位置移至另一个位置。）将记录从一个位置移至另一个位置。待排序记录序列可有下列三种存储方式：待排序记录序列可有下列三种存储方式：（1）记录存放在）记录

6、存放在一组连续的存储单元一组连续的存储单元中；类似于线性表的顺序中；类似于线性表的顺序存储结构，记录次序由存储位置决定，实现排序需移动记录。存储结构，记录次序由存储位置决定，实现排序需移动记录。（2）记录存放在）记录存放在静态链表静态链表中；记录次序由指针指示，实现排序中；记录次序由指针指示，实现排序不需移动记录，仅需修改指针。不需移动记录，仅需修改指针。链排序链排序（3）记录本身存放在一组连续的存储单元中，同时另设指示各）记录本身存放在一组连续的存储单元中，同时另设指示各个记录存储位置的个记录存储位置的地址向量地址向量，排序过程中不移动记录本身，而，排序过程中不移动记录本身，而移动地址向量中

7、相应记录的移动地址向量中相应记录的地址地址。排序结束后再根据地址调整。排序结束后再根据地址调整记录的存储位置。记录的存储位置。地址排序地址排序数据结构 第10章 内部排序4 4待排序记录的数据类型待排序记录的数据类型#define MAXSIZE 20typedef int KeyType;typedef struct KeyType key;InfoType otherinfo;RcdType;typedef struct RedType rMAXSIZE+1;/0单元作为哨兵单元作为哨兵 int length;SqList;数据结构 第10章 内部排序二、插入排序二、插入排序1直接插入排序

8、直接插入排序2折半插入排序折半插入排序32-路插入排序路插入排序4表插入排序表插入排序5希尔排序希尔排序插入排序的基本方法是：每步将一个待排序的记录，按其关键插入排序的基本方法是：每步将一个待排序的记录，按其关键字大小，字大小，插入插入到前面已经到前面已经排好序排好序的一组记录的的一组记录的适当位置适当位置上，直上，直到记录到记录全部插入全部插入为止。为止。数据结构 第10章 内部排序1直接插入排序直接插入排序基本思想基本思想：当插入第当插入第i(i 1)个记录时，前面的个记录时，前面的r1,r2，ri-1已经排好序。这时，用已经排好序。这时，用ri的关的关键字与键字与ri-1，ri-2，的关

9、键字顺序进行比的关键字顺序进行比较，找到插入位置即将较，找到插入位置即将ri插入，原来位置上之插入，原来位置上之后的所有记录依次向后顺移。后的所有记录依次向后顺移。数据结构 第10章 内部排序例例49 38 65 97 76 13 27（）i=2 38 (38 49)65 97 76 13 27i=3 65 (38 49 65)97 76 13 27i=4 97 (38 49 65 97)76 13 27i=5 76 (38 49 65 76 97)13 27i=6 13 (13 38 49 65 76 97)27i=7 (13 38 49 65 76 97)27j9727j76j65j49j

10、38j排序结果：排序结果：(13 27 38 49 65 76 97)数据结构 第10章 内部排序直接插入排序的算法直接插入排序的算法void InsertSort(SqList&L)/对待排序序列对待排序序列L进行直接插入排序进行直接插入排序 for(i=2;i=L.length;+i)if(LT(L.ri.key,L.ri-1.key)L.r0=L.ri;/复制为哨兵复制为哨兵 for(j=i-1;L.r0.key L.rj.key;-j)L.rj+1=L.rj;/记录后移记录后移 L.rj+1=L.r0;/记录插入记录插入 /InsertSort数据结构 第10章 内部排序算法评价算法评

11、价记录的比记录的比较次数较次数记录的移记录的移动次数动次数最好情况最好情况最坏情况最坏情况ni=21n10ni 2(n1)(n2)i2ni 2(n1)(n4)(i+1)2时间复杂度：时间复杂度：T(n)=O(n)结论：结论：空间复杂度：空间复杂度：S(n)=O(1)直接插入排序是一个直接插入排序是一个稳定稳定的排序方法。的排序方法。数据结构 第10章 内部排序2折半插入排序折半插入排序基本思想基本思想：利用直接插入排序的思想，只是在排序过程中，为利用直接插入排序的思想，只是在排序过程中，为减少查找次数，对已排好序的序列减少查找次数，对已排好序的序列 r1,r1,ri-1，利用折半查找法寻找利用

12、折半查找法寻找 ri 的插入位置。的插入位置。例例 (30)13 70 85 39 42 6 20i=2 13 (13 30)70 85 39 42 6 20.i=7 6 (6 13 30 39 42 70 85)20数据结构 第10章 内部排序i=8 20 (6 13 30 39 42 70 85)20lhmi=8 20 (6 13 30 39 42 70 85)20lhmi=8 20 (6 13 30 39 42 70 85)20l,m,hi=8 20 (6 13 30 39 42 70 85)20lhi=8 20 (6 13 20 30 39 42 70 85)数据结构 第10章 内部排

13、序算法描述如下：算法描述如下：void Bin_InsertSort(SqList&L)/对待排序序列对待排序序列L进行折半插入排序进行折半插入排序 for(i=2;i=L.length;+i)low=1;high=i-1;while(low=high)mid=(low+high)/2;if(r.mid.key h;j-)L.rj+1=L.rj;/记录后移记录后移 L.rj+1=L.r0;/记录插入记录插入 /Bin_InsertSort数据结构 第10章 内部排序算法分析算法分析折半插入排序减少了关键字间的比较次数（由折半插入排序减少了关键字间的比较次数（由O(n)O(n)下降到下降到O(n

14、logO(nlog2 2n)n)。折半插入排序的记录移动次数仍为折半插入排序的记录移动次数仍为O(n)。折半插入排序的时间复杂度仍为折半插入排序的时间复杂度仍为O(n)，空间复杂，空间复杂度仍为度仍为O()。折半插入排序是一个折半插入排序是一个稳定稳定的排序方法。的排序方法。数据结构 第10章 内部排序32-路插入排序路插入排序基本思想基本思想：利用直接插入排序的思想，只是在排序过程：利用直接插入排序的思想，只是在排序过程中，为减少记录的移动次数，但需要中，为减少记录的移动次数，但需要n个记录的辅助空个记录的辅助空间。其做法是：另设一个和间。其做法是：另设一个和L.r同类型的数组同类型的数组d

15、，首先将，首先将L.r1赋给赋给d.r1，并将，并将d.r1看成是在排好序的序列中处看成是在排好序的序列中处于中间位置的记录，然后从于中间位置的记录，然后从L.r中第二个记录起依次到中第二个记录起依次到d.r1之前或之后的有序序列中。之前或之后的有序序列中。例例 30 13 70 85 39 42 6 20排序过程中排序过程中d的状态变化如下：的状态变化如下：i=1 (30)firstfinali=2 (30)13 firstfinal数据结构 第10章 内部排序 30 13 70 85 39 42 6 20i=3 (30)70 13 firstfinali=4 (30)70 85 13 fi

16、rstfinali=5 (30)39 70 85 13 firstfinali=6 (30)39 42 70 85 13 firstfinali=7 (30)39 42 70 85 6 13 firstfinali=8 (30)39 42 70 85 6 13 20firstfinal数据结构 第10章 内部排序算法描述如下：算法描述如下：void Two_InsertSort(SqList L，SqList&D)/对待排序序列对待排序序列L进行进行2-路插入排序路插入排序 D.r1=L.r1;D.length=L.length;first=final=1;for(i=2;i=L.length

17、;i+)x=L.ri.key;if(x D.r1.key)if(first=1)D.rD.length=L.ri;first=D.length;else low=first;high=D.length;while(low=high)mid=(low+high)/2;if(x D.rmid.key)high=mid-1;else low=mid+1;数据结构 第10章 内部排序 for(k=first;k=high+1;k+)D.rk-1=D.rk;D.rhigh+1=L.ri;first-;else if(final=1)final+;D.rfinal=L.ri;else low=2;high

18、=final;while(low=high)mid=(low+high)/2;if(x=high+1;k+)D.rk+1=D.rk;D.rhigh+1=L.ri;fianl+;/for/Two_InsertSort数据结构 第10章 内部排序算法分析算法分析2-路插入排序减少了关键字间的比较次数路插入排序减少了关键字间的比较次数(小于小于nlog2n)。2-路插入排序减少了记录移动次数，约为路插入排序减少了记录移动次数，约为n2/8。2-路插入排序的时间复杂度仍为路插入排序的时间复杂度仍为O(n)，但空间复杂，但空间复杂度为度为O(n)。2-路插入排序是一个路插入排序是一个稳定稳定的排序方法。

19、的排序方法。数据结构 第10章 内部排序4表插入排序表插入排序表插入排序采用了静态链表的存储结构，其排序过表插入排序采用了静态链表的存储结构，其排序过程如下：首先将静态链表中数组下标为程如下：首先将静态链表中数组下标为1的分量（结的分量（结点）和表头结点构成一个循环链表，然后依次将下点）和表头结点构成一个循环链表，然后依次将下标为标为2至至n的分量（结点）按记录关键字非递减有序的分量（结点）按记录关键字非递减有序插入到循环链表中。插入到循环链表中。表插入排序的基本操作仍是将一个记录插入到已表插入排序的基本操作仍是将一个记录插入到已排好序的有序表中。和直接插入排序相比，不同之处排好序的有序表中。

20、和直接插入排序相比，不同之处仅是以修改仅是以修改2n次指针值代替移动记录，排序过程中所次指针值代替移动记录，排序过程中所需进行的关键字间的比较次数相同。因此，表插入排需进行的关键字间的比较次数相同。因此，表插入排序的时间复杂度仍是序的时间复杂度仍是O(n2)。数据结构 第10章 内部排序5希尔排序希尔排序希尔排序方法又称为希尔排序方法又称为“缩小增量缩小增量”排序。排序。基本思想：基本思想：先将整个待排序记录序列分割成若干先将整个待排序记录序列分割成若干子序列子序列分别分别进行进行直接插入排序直接插入排序，待整个序列，待整个序列“基本有序基本有序”时，再时，再对全体记录进行对全体记录进行一次一

21、次直接插入排序。直接插入排序。数据结构 第10章 内部排序例例 初始：初始：49 38 65 97 76 13 27 48 55 4取取d1=5一趟分组：一趟分组：49 38 65 97 76 13 27 48 55 4一趟排序：一趟排序：13 27 48 55 4 49 38 65 97 76取取d2=3二趟分组：二趟分组：13 27 48 55 4 49 38 65 97 76二趟排序：二趟排序：13 4 48 38 27 49 55 65 97 76取取d3=1三趟分组：三趟分组：13 4 48 38 27 49 55 65 97 76三趟排序：三趟排序：4 13 27 38 48 49

22、 55 65 76 97数据结构 第10章 内部排序希尔排序算法分析希尔排序算法分析F子序列的构成不是简单的子序列的构成不是简单的“逐段分割逐段分割”，而是将，而是将相隔相隔某个增量的记录组成一个子序列；某个增量的记录组成一个子序列；F希尔排序可提高排序速度希尔排序可提高排序速度，因为，因为关键字较小的记录关键字较小的记录跳跃式前移跳跃式前移，在进行最后一趟增量为，在进行最后一趟增量为1的插入排序时，的插入排序时，序列已基本有序序列已基本有序;F增量序列取法增量序列取法有多种：有多种：1)没有除没有除1以外的公因子以外的公因子 2)最后一个增量值必须为最后一个增量值必须为1F时间复杂度时间复杂

23、度是所取增量序列的函数，但至今没人能够是所取增量序列的函数，但至今没人能够给出完整的数学分析。给出完整的数学分析。F希尔排序希尔排序是一个是一个不稳定不稳定的排序方法。的排序方法。数据结构 第10章 内部排序三、交换排序三、交换排序1起泡排序起泡排序(Bubble Sort)2快速排序快速排序(Quick Sort)数据结构 第10章 内部排序1起泡排序起泡排序(Bubble Sort)基本过程：基本过程：1)将第一个记录的关键字与第二个记录的关键字进将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序行比较，若为逆序r1.keyr2.key，则交换；然后比则交换；然后比较第二个记录与第

24、三个记录；依次类推，直至第较第二个记录与第三个记录；依次类推，直至第n-1个个记录和第记录和第n个记录比较为止个记录比较为止第一趟冒泡排序第一趟冒泡排序，结果，结果关键字最大的记录关键字最大的记录被安置在最后一个记录上被安置在最后一个记录上;2)对前对前n-1个记录进行第二趟冒泡排序，结果使个记录进行第二趟冒泡排序，结果使关关键字次大的记录键字次大的记录被安置在第被安置在第n-1个记录位置个记录位置;3)重复上述过程，直到重复上述过程，直到“在一趟排序过程中没有进在一趟排序过程中没有进行过交换记录的操作行过交换记录的操作”为止为止。数据结构 第10章 内部排序例例：49 38 38 38 38

25、 13 13 38 49 49 49 13 27 27 65 65 65 13 27 38 38 97 76 13 27 49 49 76 13 27 49 49 13 27 49 65 27 49 76 49 97初初始始关关键键字字第第一一趟趟排排序序后后第第二二趟趟排排序序后后第第三三趟趟排排序序后后第第四四趟趟排排序序后后第第五五趟趟排排序序后后第第六六趟趟排排序序后后数据结构 第10章 内部排序算法分析算法分析时间复杂度时间复杂度最好情况（正序）最好情况（正序）最坏情况（逆序）最坏情况（逆序）比较次数比较次数移动次数移动次数n-102)1()1(2nnini2)1(3)1(32nni

26、niT(n)=O(n)空间复杂度：空间复杂度：S(n)=O(1)起泡排序是一个起泡排序是一个稳定稳定的排序方法的排序方法数据结构 第10章 内部排序2快速排序快速排序(Quick Sort)对冒泡排序的一种改进对冒泡排序的一种改进基本思想：基本思想：通过一趟排序将待排序记录分割成通过一趟排序将待排序记录分割成独立的两独立的两部分部分，其中一部分的关键字均比另一部分的关键，其中一部分的关键字均比另一部分的关键字小，则可字小，则可分别对这两部分记录继续分别进行排分别对这两部分记录继续分别进行排序序，以达到整个序列有序。，以达到整个序列有序。数据结构 第10章 内部排序排序过程：排序过程：1)初始时

27、令初始时令i=s,j=t;2)首先从首先从j所指位置向前搜索所指位置向前搜索第一个关键字小第一个关键字小于于pivot的记录的记录，并和，并和rp交换交换;3)再从再从i所指位置起向后搜索，找到所指位置起向后搜索，找到第一个关第一个关键字大于键字大于pivot的记录的记录，和，和rp交换交换;4)重复上述两步，直至重复上述两步，直至i=j为止为止;（此时整个（此时整个序列被分成有序的前后两块）序列被分成有序的前后两块）5)再分别对两个子序列进行再分别对两个子序列进行快速排序快速排序，直到每，直到每个子序列只含有一个记录为止。个子序列只含有一个记录为止。对对rst中记录进行一趟快速排序，附设两个

28、中记录进行一趟快速排序，附设两个指针指针i和和j，设枢轴记录设枢轴记录rp=rs，pivot=rp.key数据结构 第10章 内部排序快速排序举例快速排序举例初始关键字：初始关键字：49，38，65，97，76，13，27，49pivotkey 49491次交换后：次交换后：27，38，65，97，76，13，49ijijji2次交换后：次交换后：27，38，97，76，13，65，49ijj3次交换后：次交换后：27，38，13，97，76，65，49iji4次交换后：次交换后：27，38，13，76，97，65，49jij一趟完成后：一趟完成后：27，38，13，49，76，97，65，4

29、9数据结构 第10章 内部排序一趟完成后一趟完成后：27，38，13，49，76，97，65，49分别进行快速排序分别进行快速排序：13 27 38 49 49 65 76 97 快速排序结束：快速排序结束：13 27 38 49 49 65 76 97数据结构 第10章 内部排序快速排序算法描述：快速排序算法描述：int Partition(SqList&L,int low,int high)/对顺序表对顺序表L进行一趟快速排序，返回枢轴记录所在的位置进行一趟快速排序，返回枢轴记录所在的位置 L.r0=L.rlow;/用子表的第一记录作枢轴记录用子表的第一记录作枢轴记录 pivotkey=L

30、.rlow.key;while(lowhigh)while(low=pivotkey)-high;L.rlow=L.rhigh;/将比将比pivotkey 小的记录移到低端小的记录移到低端 while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;/将比将比pivotkey 大的记录移到高端大的记录移到高端 L.rlow=l.r0;return low;数据结构 第10章 内部排序void Qsort(SqList&L,int low,int high)/对顺序表对顺序表L的子序列的子序列L.rlow.high作快速排序作快速排序 if(low

31、high)pivotloc=Partition(L,low,high);Qsort(L,low,pivotloc-1);Qsort(L,pivotloc+1,high);/QSortvoid QuickSort(SqList&L)/对顺序表对顺序表L作快速排序作快速排序 Qsort(L,1,L.length);/QuickSort数据结构 第10章 内部排序快速排序算法分析快速排序算法分析F在在n个元素的序列中，对一个记录定位所需时间为个元素的序列中，对一个记录定位所需时间为 O(n)。若设。若设 T(n)是对是对 n 个元素的序列进行排序所需的时间，而且每次对一个个元素的序列进行排序所需的时

32、间，而且每次对一个记录正确定位后，记录正确定位后，正好把序列划分为长度相等的两个子序列正好把序列划分为长度相等的两个子序列，此，此时，总的计算时间为：时，总的计算时间为：T(n)cn+2 T(n/2)/c是一个常数是一个常数 cn+2(cn/2+2T(n/4)=2cn+4T(n/4)2cn+4(cn/4+2T(n/8)=3cn+8T(n/8)cn log2n+nT(1)=O(n log2n)F快速排序的平均时间是快速排序的平均时间是O(nlogn)，在所有同数量级，在所有同数量级(O(nlogn)的的排序方法中，就排序方法中，就平均计算时间平均计算时间而言，而言，快速排序是我们所讨论的所快速排

33、序是我们所讨论的所有内部排序方法中最好的一个有内部排序方法中最好的一个。数据结构 第10章 内部排序F快速排序需要一个栈空间来实现递归，若每趟排序都将记录序快速排序需要一个栈空间来实现递归，若每趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为列均匀地分割成长度相接近的两个子序列，则栈的最大深度为O(logn)。F若初始序列按关键字基本有序（最坏情况），快速排序蜕化为若初始序列按关键字基本有序（最坏情况），快速排序蜕化为起泡排序起泡排序，其时间复杂度为，其时间复杂度为O(n2)，最坏情况下栈的深度为，最坏情况下栈的深度为n。F改进的方法，用改进的方法，用“三者取中三者取中”

34、的法则选取枢轴记录（的法则选取枢轴记录（pivotkey)。F快速排序是一种快速排序是一种不稳定不稳定的排序方法。的排序方法。F对于对于 n 较大的平均情况较大的平均情况而言，快速排序是而言，快速排序是“快速快速”的，但是当的，但是当 n 很小时很小时，这种排序方法往往比其它简单排序方法还要慢。，这种排序方法往往比其它简单排序方法还要慢。数据结构 第10章 内部排序四、选择排序四、选择排序基本思想基本思想：每一趟：每一趟(例如例如第第 i 趟趟，i=1,n-1)在在 n-i+1 个记录中选取个记录中选取关键字最小的记录关键字最小的记录 作为有序序列中作为有序序列中第第 i 个记录个记录。1简单

35、选择排序简单选择排序(Select Sort)2树形选择排序树形选择排序(Tree Selection Sort)3堆排序堆排序(Heap Sort)数据结构 第10章 内部排序1简单选择排序简单选择排序(Select Sort)基本步骤：基本步骤：i从从1开始，直到开始，直到n-1，进行，进行n-1趟排序，第趟排序，第i 趟的排趟的排序过程为：序过程为：在一组记录在一组记录rirn(i=1,2,n-1)中选择中选择具有最小关键字的记录具有最小关键字的记录,并和第并和第 i 个记录进行交换。个记录进行交换。数据结构 第10章 内部排序简单选择排序的算法简单选择排序的算法void SelectS

36、ort(SqList&L)/对顺序表对顺序表L进行简单选择排序进行简单选择排序 for(i=1;iL.length;+i)k=i;/选择关键字最小的记录选择关键字最小的记录 for(j=i+1;j L.rj.key)k=j;/最小记录与第最小记录与第i个记录互换个记录互换 if(i!=k)temp=L.ri;L.ri=L.rk;L.rk=temp;数据结构 第10章 内部排序算法分析算法分析F简单选择排序的关键字比较次数简单选择排序的关键字比较次数与记录的初始排列无关与记录的初始排列无关。第。第 i 趟趟选择具有最小关键字的记录所需的选择具有最小关键字的记录所需的比较次数比较次数是是 n-i

37、次，若整个待排次，若整个待排序序列有序序列有 n 条记录。因此，总的关键字比较次数为：条记录。因此，总的关键字比较次数为：1121ninnin)()(F记录的记录的移动次数移动次数与记录的初始排列有关。当初始状态是按其关键与记录的初始排列有关。当初始状态是按其关键字从小到大有序的时候，记录的移动次数为字从小到大有序的时候，记录的移动次数为 0，达到最少，达到最少(最好情况最好情况)。最坏情况最坏情况是每一趟都要进行交换，总的记录移动次数为是每一趟都要进行交换，总的记录移动次数为3(n-1)。F简单选择排序是一种简单选择排序是一种不稳定不稳定的排序方法。的排序方法。F简单选择排序的时间复杂度是简

38、单选择排序的时间复杂度是O(n2)，空间复杂度是，空间复杂度是O(1)。数据结构 第10章 内部排序2树形树形选择排序选择排序(Tree Selection Sort)又称又称锦标赛排序锦标赛排序(Tournament Sort),是简单选择排序的改进是简单选择排序的改进(减少关键字间的比较次数减少关键字间的比较次数)。基本思想基本思想:与体育比赛时的淘汰赛类似。与体育比赛时的淘汰赛类似。首先取得首先取得 n 个记录的关键字，进行两两比较，得个记录的关键字，进行两两比较，得到到 n/2 个比较的个比较的优胜者优胜者(关键字小者关键字小者)，作为第一步比，作为第一步比较的结果保留下来。然后对这较

39、的结果保留下来。然后对这 n/2 个记录再进行关个记录再进行关键字的两两比较，键字的两两比较，如此重复，直到选出一个关键，如此重复，直到选出一个关键字最小的记录为止。字最小的记录为止。数据结构 第10章 内部排序F如果如果 n 不是不是2的的 k 次幂，则让叶子结点数补足到满足次幂，则让叶子结点数补足到满足 2k-1个。叶个。叶结点上面一层的非叶结点是叶结点关键字两两比较的结果。最顶结点上面一层的非叶结点是叶结点关键字两两比较的结果。最顶层是树的根。层是树的根。F每次两两比较的结果是把关键字小者作为优胜者上升到双亲结每次两两比较的结果是把关键字小者作为优胜者上升到双亲结点，称这种比赛树为点，称

40、这种比赛树为胜者树胜者树。F位于最底层的叶结点叫做胜者树的外结点，非叶结点称为胜者位于最底层的叶结点叫做胜者树的外结点，非叶结点称为胜者树的内结点。每个结点除了存放记录的关键字树的内结点。每个结点除了存放记录的关键字 key 外，还存放了外，还存放了此记录此记录是否要参选的标志是否要参选的标志 flag和此记录在满二叉树中的和此记录在满二叉树中的序号序号index。数据结构 第10章 内部排序形成初始胜者树（最小关键字上升到根）形成初始胜者树（最小关键字上升到根）关键字比较次数关键字比较次数:7数据结构 第10章 内部排序关键字比较次数关键字比较次数:2关键字比较次数关键字比较次数:2数据结构

41、 第10章 内部排序说明：说明：F锦标赛排序构成的树是锦标赛排序构成的树是完全二叉树完全二叉树，其深度为，其深度为 log2n +1，其中，其中 n 为待排序元素个数。为待排序元素个数。F除第一次选择具有最小关键字的记录需要进行除第一次选择具有最小关键字的记录需要进行 n-1 次关键字比较次关键字比较外，重构胜者树选择具有次小、再次小关键字记录所需的关键字比较外，重构胜者树选择具有次小、再次小关键字记录所需的关键字比较次数均为次数均为 log2n 。总关键字比较次数为总关键字比较次数为O(nlog2n)。F记录的移动次数记录的移动次数不超过不超过关键字的比较次数，所以锦标赛排序总的关键字的比较

42、次数，所以锦标赛排序总的时间复杂度为时间复杂度为O(nlog2n)。F这种排序方法虽然减少了许多排序时间，但是这种排序方法虽然减少了许多排序时间，但是使用了较多的附加使用了较多的附加存储存储。F锦标赛排序是一个锦标赛排序是一个稳定的稳定的排序方法。排序方法。数据结构 第10章 内部排序3堆堆排序排序(Heap Sort)堆排序是树形选择排序的一种改进，主要是为了堆排序是树形选择排序的一种改进，主要是为了减少辅助存减少辅助存储空间储空间和和多余比较多余比较。堆的定义：堆的定义：n个元素的序列个元素的序列k1,k2,kn当且仅当满足下列关系时，称当且仅当满足下列关系时，称之为堆。之为堆。)2,2,

43、1(122122nikkkkkkkkiiiiiiii或数据结构 第10章 内部排序例例：（：（96，83，27，38，11，9）例：例：（13，38，27，50，76，65，49，97）可将堆序列看成完全二叉树可将堆序列看成完全二叉树大顶大顶堆堆小顶小顶堆堆数据结构 第10章 内部排序堆排序的堆排序的基本思想基本思想是：把是：把n个记录存于向量个记录存于向量r之中，把它看成完全二叉树，之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分两步处理：此时关键字序列不一定满足堆的关系。堆排序大体分两步处理：第一步：第一步：初建堆初建堆。从堆的定义出发，当。从堆的定义出发，当i=1

44、,2,n/2时应满足时应满足kik2i和和kik2i+1（或（或kik2i和和kik2i+1）。所以先取）。所以先取i=n/2(它一定是第它一定是第n个结点双亲个结点双亲的编号的编号)将以将以i结点为根的子树调整为堆；然后令结点为根的子树调整为堆；然后令i=i-1，再将以，再将以i结点为结点为根的子树调整为堆。此时可能会反复调整某些结点，直到根的子树调整为堆。此时可能会反复调整某些结点，直到i=1为止，堆为止，堆初步建成。初步建成。第二步：第二步：堆排序堆排序。首先输出堆顶元素，让堆中最后一个元素上移到原。首先输出堆顶元素，让堆中最后一个元素上移到原堆顶位置，然后恢复堆，因为经过上移堆顶元素的

45、操作后，往往破坏堆顶位置，然后恢复堆，因为经过上移堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤，直到全部元素输出完为止。恢复堆的步骤，直到全部元素输出完为止。我们称这个从堆顶至叶子的调整过程为我们称这个从堆顶至叶子的调整过程为“筛选筛选”。从。从一个无序序列建堆的过程就是一个反复一个无序序列建堆的过程就是一个反复“筛选筛选”的过程。的过程。数据结构 第10章 内部排序例如：根据输入序列例如：根据输入序列49,38,65,97,76,13,27,49，建立一个小顶堆。，建立一个小顶堆

46、。第一步：第一步：初建堆初建堆数据结构 第10章 内部排序第二步：堆排序第二步：堆排序。这是一个。这是一个反复输出堆顶元素反复输出堆顶元素，将，将堆尾元素移至堆顶，堆尾元素移至堆顶，再调整恢复堆再调整恢复堆的过程。恢复堆的过程与初建堆中的过程。恢复堆的过程与初建堆中i=1时所进行的操作完时所进行的操作完全相同。全相同。注意注意：每输出一次堆顶元素，堆顶与堆尾元素就交换一次，同时堆尾：每输出一次堆顶元素，堆顶与堆尾元素就交换一次，同时堆尾的逻辑位置退的逻辑位置退1，直到堆中剩下一个元素为止。，直到堆中剩下一个元素为止。数据结构 第10章 内部排序例如：对于给定的输入序列例如：对于给定的输入序列8

47、0,42,13,55,94,17,46，进行堆排序。，进行堆排序。数据结构 第10章 内部排序数据结构 第10章 内部排序堆排序算法描述如下：堆排序算法描述如下：void HeapSort(HeapType&H)/对顺序表对顺序表H进行堆排序进行堆排序 /初始堆建立初始堆建立 for(i=H.length/2;i 0;-i)HeapAdjust(H,i,H.length);/堆的输出与调整堆的输出与调整 for(i=H.length;i 1;-i)temp=H.r1;H.r1=H.ri;H.ri=temp;HeapAdjust(H,1,i-1);数据结构 第10章 内部排序void HeapA

48、djust(HeapType&H,int s,int m)/调整调整H.rs.m成一个大顶堆成一个大顶堆 rc=H.rs;for(j=2*s;j=m;j*=2)if(jm&H.rj.key H.rj+1.key)j+;if(rc.key H.rj.key)break;H.rs=H.rj;s=j;H.rs=rc;数据结构 第10章 内部排序算法分析算法分析时间复杂度时间复杂度：最坏情况下：最坏情况下T(n)=O(nlogn)空间复杂度空间复杂度：S(n)=O(1)对记录数较少的文件对记录数较少的文件不值得提倡，但不值得提倡，但对对n较大较大的文件的文件很有效。很有效。堆排序是一个堆排序是一个不稳

49、定不稳定的排序方法。的排序方法。数据结构 第10章 内部排序五、归并排序五、归并排序(Merging Sort)归并排序归并排序(merge sort)是一类与插入排序、交换排序、选择排是一类与插入排序、交换排序、选择排序不同的另一种排序方法。序不同的另一种排序方法。归并的含义归并的含义是将两个或两个以上的有是将两个或两个以上的有序表合并成一个新的有序表。序表合并成一个新的有序表。归并排序有多路归并排序归并排序有多路归并排序、2-路归路归并排序并排序；可用于内部排序，也可以用于外部排序。我们仅对内部；可用于内部排序，也可以用于外部排序。我们仅对内部排序的排序的2-路归并方法进行讨论。路归并方法

50、进行讨论。2-路归并排序算法思路：路归并排序算法思路：(1)把把n个记录看成个记录看成n个长度为个长度为1的有序子表；的有序子表；(2)进行两两归并使记录关键字有序，得到进行两两归并使记录关键字有序，得到n/2个长度为个长度为2的有序子表；的有序子表；(3)重复第重复第(2)步直到所有记录归并成一个长度为步直到所有记录归并成一个长度为n的有序表为止。的有序表为止。数据结构 第10章 内部排序例如：例如：初始关键字初始关键字：49 38 65 97 76 13 27一趟归并之后一趟归并之后：38 49 65 97 13 76 27两趟归并之后两趟归并之后：38 49 65 97 13 27 76