数据结构课件排序.ppt

《数据结构课件排序.ppt》由会员分享，可在线阅读，更多相关《数据结构课件排序.ppt（51页珍藏版）》请在沃文网上搜索。

1、数据结构课程的内容数据结构课程的内容一、教学内容：一、教学内容：1 1、插入排序（直接插入排序、折半插入排序、希尔排序）；、插入排序（直接插入排序、折半插入排序、希尔排序）；2 2、交换排序（起泡排序、快速排序）；、交换排序（起泡排序、快速排序）；3 3、选择排序（直接选择排序、堆排序）；、选择排序（直接选择排序、堆排序）；4 4、归并排序；、归并排序；5 5、基数排序；、基数排序；二、教学要求：二、教学要求：1 1、掌握排序的基本概念和各种排序方法的特点，并能加以灵、掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用；活应用；2 2、掌握插入排序、交换排序、选择排序的方法及其性能分析、

2、掌握插入排序、交换排序、选择排序的方法及其性能分析方法；方法；3 3、了解归并排序、基数排序方法。、了解归并排序、基数排序方法。第第1010章章 内部排序内部排序10.1 10.1 概述概述10.210.2 插入排序插入排序10.3 10.3 交换排序交换排序10.4 10.4 选择排序选择排序10.5 10.5 归并排序归并排序10.6 10.6 基数排序基数排序第第1010章章 内部排序内部排序10.1 10.1 概述概述1.什么是排序？什么是排序？将一组杂乱无章的将一组杂乱无章的数据数据按一定的按一定的规律规律顺次排列起来。顺次排列起来。存放在数据表中存放在数据表中按按关键字排序关键字排

3、序定义：设有记录序列：定义：设有记录序列：R1 R1、R2 .R2 .RnRn 其相应的关键字序列为：其相应的关键字序列为：K1 K1、K2 K2 KnKn ;若存在一种确定的关系：若存在一种确定的关系：KxKx=KyKy=KzKz则则将记录序列将记录序列 R1 R1、R2 .R2 .RnRn 排成按排成按该关键字有序的序列：该关键字有序的序列：Rx Rx、RyRy.RzRz 的的操作，称之为排序。操作，称之为排序。2.排序的目的是什么？排序的目的是什么？3.3.排序算法的好坏如何衡量？排序算法的好坏如何衡量？时间效率时间效率排序速度（即排序所花费的全部比较次数）排序速度（即排序所花费的全部比

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

5、，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。结果还要及时放入外存，显然外部排序要复杂得多。大多数排序算法都有两个基本的操作：大多数排序算法都有两个基本的操作：（1）比较两个关键字的大小）比较两个关键字的大小（2）将记录从一个位置移动到另一个位置）将记录从一个位置移动到另一个位置注：注：大多数排序算法都是针对顺序表结构的大多数排序算法都是针对顺序表结构的(便于直接移动元素便于直接移动元素)5.顺序存储（顺序表）的抽象数据类型如何表示？顺序存储（顺序表）的抽象数据类型如何表示？Typedefstruct/定义每个记录（数据元素）的结构定义每个记录（数据元素）的结

6、构KeyTypekey;/关键字关键字InfoTypeotherinfo;/其它数据项其它数据项RecordType;Typedefstruct/定义顺序表的结构定义顺序表的结构RecordTyperMAXSIZE+1;/存储顺序表的向量存储顺序表的向量 /r0/r0一般作哨兵或缓冲区一般作哨兵或缓冲区intlength;/顺序表的长度顺序表的长度SqList;#defineMAXSIZE20/设记录不超过设记录不超过2020个个typedefintKeyType;/设关键字为整型量（设关键字为整型量（intint型）型）6.内部排序的算法有哪些？内部排序的算法有哪些？按排序的规则不同，可分为

7、按排序的规则不同，可分为5类：类：插入排序插入排序交换排序（重点是快速排序）交换排序（重点是快速排序）选择排序选择排序归并排序归并排序基数排序基数排序d关键字的位数关键字的位数(长度长度)按排序算法的时间复杂度不同，可分为按排序算法的时间复杂度不同，可分为3类：类：简单的排序算法：时间效率低，简单的排序算法：时间效率低，O(n2)先进的排序算法先进的排序算法:时间效率高，时间效率高，O(nlog2n)基数排序算算法：时间效率高，基数排序算算法：时间效率高，O(dn)10.210.2 插入排序插入排序插入排序的基本思想是：插入排序的基本思想是：插入排序的基本思想是：插入排序的基本思想是：插入排序

8、有多种具体实现算法：插入排序有多种具体实现算法：1)直接插入排序直接插入排序2)折半插入排序折半插入排序3)希尔排序希尔排序每步将一个待排序的对象，每步将一个待排序的对象，每步将一个待排序的对象，每步将一个待排序的对象，按其关键码大小，按其关键码大小，按其关键码大小，按其关键码大小，插入到前面插入到前面插入到前面插入到前面已经排好序的一组对象已经排好序的一组对象已经排好序的一组对象已经排好序的一组对象的的的的适当位置适当位置适当位置适当位置上上上上，直到对象全部插入为止。，直到对象全部插入为止。，直到对象全部插入为止。，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。

9、简言之，边插入边排序，保证子序列中随时都是排好序的。简言之，边插入边排序，保证子序列中随时都是排好序的。简言之，边插入边排序，保证子序列中随时都是排好序的。1)1)直接插入排序直接插入排序新元素插入到哪里？新元素插入到哪里？例例1 1：关键字序列关键字序列T=（13，6，3，31，9，27，5，11），），请写出直接插入排序的中间过程序列。请写出直接插入排序的中间过程序列。【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,

10、13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】在已形成的在已形成的有序表中有序表中线性查找线性查找，并在，并在适当位置插入，把原来位置上的元素向后适当位置插入，把原来位置上的元素向后顺移顺移。最简单的排序法！最简单的排序法！最简单的排序法！最简单的排序法！例例2：关键字序列关键字序列T=（21，25，49，25*，16，08），），请写出直接插入排序的具体实现过程。请写出直接插入排序的具体实现过程。*表示后一个表示后一个2525i i=1=121212525494925*25*161608080123456暂暂存存2121i i

11、=2=2i i=3=3i i=5=5i i=4=4i i=6=62525252525494949494925*25*25*494916161625*25*0808084949解：解：假设该序列已存入一维数组假设该序列已存入一维数组V7V7中，将中，将V0V0作为缓冲或作为缓冲或暂存单元（暂存单元（TempTemp）。）。则程序执行过程为：则程序执行过程为：21212525494925*25*2121初态：初态：1616494925*25*2525212116160808完成!对应程序参见教材对应程序参见教材P265P265。void void Insertsort(SqListInsertso

12、rt(SqList*L)*L)intint i,j;i,j;for(i=2;ilength;i+)for(i=2;ilength;i+)L-r0=L-ri;L-r0=L-ri;j=i-1;j=i-1;while(L-r0.keyrj.key)while(L-r0.keyrj.key)L-rj+1=L-rj;L-rj+1=L-rj;j-;j-;L-rj+1=L-r0;L-rj+1=L-r0;直接插入排序的演示直接插入排序的演示n n若设待排序的对象个数为若设待排序的对象个数为若设待排序的对象个数为若设待排序的对象个数为n n，则算法需要进行则算法需要进行则算法需要进行则算法需要进行n n-1-1

13、次插入。次插入。次插入。次插入。n n最好情况下：最好情况下：最好情况下：最好情况下：排序前对象已经按关键码大小从小到大有序，每排序前对象已经按关键码大小从小到大有序，每排序前对象已经按关键码大小从小到大有序，每排序前对象已经按关键码大小从小到大有序，每趟只需与前面的有序对象序列的趟只需与前面的有序对象序列的趟只需与前面的有序对象序列的趟只需与前面的有序对象序列的最后一个对象最后一个对象最后一个对象最后一个对象的的的的关键码比较关键码比较关键码比较关键码比较 1 1 1 1 次，移动次，移动次，移动次，移动 2 2 2 2 次对象。因此，总的次对象。因此，总的次对象。因此，总的次对象。因此，总

14、的关键码比较次数为关键码比较次数为关键码比较次数为关键码比较次数为n n-1-1，对象移动次数为对象移动次数为对象移动次数为对象移动次数为 2(2(n n-1)-1)。直接插入排序的算法分析直接插入排序的算法分析最坏情况下：最坏情况下：最坏情况下：最坏情况下：第第第第i i趟插入时，第趟插入时，第趟插入时，第趟插入时，第i+1i+1个对象必须与前面个对象必须与前面个对象必须与前面个对象必须与前面i i个对象个对象个对象个对象都做关键码比较，并且每做都做关键码比较，并且每做都做关键码比较，并且每做都做关键码比较，并且每做 1 1 1 1 次比较就要做次比较就要做次比较就要做次比较就要做 1 1

15、1 1 次数据移动。则总的关键码比较次数次数据移动。则总的关键码比较次数次数据移动。则总的关键码比较次数次数据移动。则总的关键码比较次数KCNKCN和和和和对象移动次数对象移动次数对象移动次数对象移动次数RMNRMN分别为分别为分别为分别为 若待排序对象序列中出现各种可能排列的概率若待排序对象序列中出现各种可能排列的概率若待排序对象序列中出现各种可能排列的概率若待排序对象序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况相同，则可取上述最好情况和最坏情况的平均情况相同，则可取上述最好情况和最坏情况的平均情况相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键码

16、比较次数和对象移动次数。在平均情况下的关键码比较次数和对象移动次数。在平均情况下的关键码比较次数和对象移动次数。在平均情况下的关键码比较次数和对象移动次数约为约为约为约为 n n2 2/4/4。因此，直接插入排序的时间复杂度为因此，直接插入排序的时间复杂度为因此，直接插入排序的时间复杂度为因此，直接插入排序的时间复杂度为 o o(n n2 2)。直接插入排序是一种稳定的排序方法。直接插入排序是一种稳定的排序方法。直接插入排序是一种稳定的排序方法。直接插入排序是一种稳定的排序方法。2 2）折半插入排序折半插入排序优点：优点：比较的次数大大减少，全部元素比较次数仅为比较的次数大大减少，全部元素比较

17、次数仅为O(nlogO(nlog2 2n)n)。时时间间效效率率：虽虽然然比比较较次次数数大大大大减减少少，可可惜惜移移动动次次数数并并未未减减少少，所以排序效率仍为所以排序效率仍为O(nO(n2 2)。空间效率：空间效率：O O（1 1）稳定性：稳定性：稳定稳定新元素插入到哪里？新元素插入到哪里？在已形成的在已形成的有序表中有序表中折半查找折半查找，并在适，并在适当位置插入，把原来位置上的元素向后当位置插入，把原来位置上的元素向后顺移顺移。若记录是链表结构，用直接插入排序行否？折半若记录是链表结构，用直接插入排序行否？折半插入排序呢？插入排序呢？答：答：直接插入不仅可行，而且还无需移动元素，

18、时间直接插入不仅可行，而且还无需移动元素，时间效率更高！效率更高！但链表无法但链表无法但链表无法但链表无法“折半折半折半折半”！讨论讨论 loglog2 2i i +1+1折半插入排序的算法分析折半插入排序的算法分析折半查找比顺序查找快，所以折半插入排序就折半查找比顺序查找快，所以折半插入排序就折半查找比顺序查找快，所以折半插入排序就折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。平均性能来说比直接插入排序要快。平均性能来说比直接插入排序要快。平均性能来说比直接插入排序要快。在插入第在插入第在插入第在插入第 i i 个对象时，需要经过个对象时，需要经过个对象时，需要经过

19、个对象时，需要经过 次次次次关键码比较，才能确定它应插入的位置。因此，关键码比较，才能确定它应插入的位置。因此，关键码比较，才能确定它应插入的位置。因此，关键码比较，才能确定它应插入的位置。因此，将将将将 n n 个对象用折半插入排序所进行的关键码个对象用折半插入排序所进行的关键码个对象用折半插入排序所进行的关键码个对象用折半插入排序所进行的关键码比较次数为：比较次数为：比较次数为：比较次数为：n*logn*log2 2n n折半插入排序是一个稳定的排序方法。折半插入排序是一个稳定的排序方法。折半插入排序是一个稳定的排序方法。折半插入排序是一个稳定的排序方法。3 3）希尔（）希尔（shells

20、hell）排序（又称缩小增量排序）排序（又称缩小增量排序）基本思想基本思想基本思想基本思想：先将整个待排记录序列分割成若干子序列：先将整个待排记录序列分割成若干子序列：先将整个待排记录序列分割成若干子序列：先将整个待排记录序列分割成若干子序列,分分分分别进行直接插入排序，待整个序列中的记录别进行直接插入排序，待整个序列中的记录别进行直接插入排序，待整个序列中的记录别进行直接插入排序，待整个序列中的记录“基本有序基本有序基本有序基本有序”时，再对全体记录进行一次直接插入排序。时，再对全体记录进行一次直接插入排序。时，再对全体记录进行一次直接插入排序。时，再对全体记录进行一次直接插入排序。技巧：技

21、巧：技巧：技巧：子序列的构成不是简单地子序列的构成不是简单地子序列的构成不是简单地子序列的构成不是简单地“逐段分割逐段分割逐段分割逐段分割”，而是将，而是将，而是将，而是将相隔某个增量相隔某个增量相隔某个增量相隔某个增量dkdkdkdk的的的的记录组成一个子序列记录组成一个子序列记录组成一个子序列记录组成一个子序列,让增量让增量让增量让增量dkdkdkdk逐趟逐趟逐趟逐趟缩缩缩缩短（例如依次取短（例如依次取短（例如依次取短（例如依次取5,3,15,3,15,3,15,3,1），直到），直到），直到），直到dkdkdkdk1 1 1 1为止。为止。为止。为止。优点：优点：优点：优点：让关键字值小

22、的元素能很快前移，且序列若基本让关键字值小的元素能很快前移，且序列若基本让关键字值小的元素能很快前移，且序列若基本让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。有序时，再用直接插入排序处理，时间效率会高很多。有序时，再用直接插入排序处理，时间效率会高很多。有序时，再用直接插入排序处理，时间效率会高很多。38例：例：关键字序列关键字序列 T=(49T=(49，3838，6565，97,76,13,27,4997,76,13,27,49*，55,55,0404），），请写出希尔排序的具体实现过程。请写出希尔排序的具体实现过程。01234567891049

23、38659776132749*5504初态：初态：第第1趟趟(dk=5)第第2趟趟(dk=3)第第3趟趟(dk=1)4913134938276549*9755760427386549*9755135576045513270427044949*4949*7638766565 9797551327044949*387665 9713270449*76 97算法分析：算法分析：开始时开始时dk 的值较大，子序列中的对象较少，排序速度的值较大，子序列中的对象较少，排序速度较快；随着排序进展，较快；随着排序进展，dk值逐渐变小，子序列中对象个数值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大

24、多数对象已基本有序，逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。所以排序速度仍然很快。riri时间效率：时间效率：空间效率：空间效率：O O O O（1 1 1 1）因为仅占用因为仅占用1 1个缓冲单元个缓冲单元算法的稳定性：算法的稳定性：不稳定不稳定不稳定不稳定因为因为4949*排序后却到了排序后却到了4949的前面的前面O(O(O(O(n n1.251.25）O O O O（1.61.6n n1.251.25）经验公式经验公式课堂练习：课堂练习：n-1log2n2log2nn*n1、初始序列已经按键值有序时，用直接插入算法进、初始序列已经按键值有序时，用直接插

25、入算法进行排序，需要比较的次数是（）行排序，需要比较的次数是（）2.欲将序列（欲将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关中的关键码按字母升序重排，则初始步长为键码按字母升序重排，则初始步长为4的希尔排序一趟的希尔排序一趟的结果是？的结果是？答：答：原始序列：原始序列：Q,H,C,Y,P,A,M,S,R,D,F,Xshellshell一趟后：一趟后：P,Q,R,A,D,H,C,F,M,S,X,Y3.以以关关键键字字序序列列（256，301，751，129，937，863，742，694，076，438）为为例例，分分别别写写出出执执行行以以下下算算法法的的各各趟趟排排序序结

26、结束束时时，关关键键字字序序列列的的状状态态，并并说说明明这这些些排排序序方方法法中中，哪些易于在链表（包括各种单、双、循环链表）上实现？哪些易于在链表（包括各种单、双、循环链表）上实现？直接插入排序直接插入排序希尔排序（取希尔排序（取dk=5,3,1）答：答：显然，直接插入排序方法易于在链表上实现；但希尔显然，直接插入排序方法易于在链表上实现；但希尔排序方法因为是按增量选择记录，不易于在链表上实现。排序方法因为是按增量选择记录，不易于在链表上实现。两种排序方法的中间状态分别描述如后：两种排序方法的中间状态分别描述如后：课堂练习：课堂练习：原始序列：原始序列：256，301，751，129，9

27、37，863，742，694，076，438(取取取取dkdk=5,3,1)=5,3,1)256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，694694，129129，937937，863863，742742，751751，076076，438438256256，301301，694694，076076，937937，863863，742742

28、，751751，129129，438438256256，301301，694694，076076，438438，863863，742742，751751，129129，937937第第1趟趟dkdk=5=5第第2趟趟dkdk=3=3第第3趟趟dkdk=1=1256256，301301，694694，076076，438438，863863，742742，751751，129129，937937256256，301301，694694，076076，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，43843

29、8，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，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，8

30、63863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，129129，256256，301301，438438，694694，742742，751751，863863，93793710.3 10.3 交换排序交换排序两两比较待排序记录的关键两两比较待排序记录的关键两两比较待排序记录的关键两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好码，如果发生逆序（即排列顺序与排序后的次序正好码，如果发生逆序（即排列顺序与排序后的次序正好码，如果发生逆序（即排列顺序与

31、排序后的次序正好相反），则交换之，直到所有记录都排好序为止。相反），则交换之，直到所有记录都排好序为止。相反），则交换之，直到所有记录都排好序为止。相反），则交换之，直到所有记录都排好序为止。交换排序的主要算法有：交换排序的主要算法有：1)冒泡排序冒泡排序2)快速排序快速排序交换排序的基本思想是：交换排序的基本思想是：交换排序的基本思想是：交换排序的基本思想是：1)冒泡排序冒泡排序基本思路：基本思路：每趟不断将记录两两比较，并按每趟不断将记录两两比较，并按“前小后大前小后大”（或（或“前大后小前大后小”）规则交换。）规则交换。优点：优点：每趟结束时，不仅能挤出一个最大值到最后面位置，每趟结束时

32、，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。可以提前结束排序。前提：前提：顺序存储结构顺序存储结构例：例：关键字序列关键字序列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

33、趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟void void bubble_sort(SqListbubble_sort(SqList*L)*L)intint m,i,j,flag=1;m,i,j,flag=1;RecordTypeRecordType x;x;m=n-1;m=n-1;while(m0)&(flag=1)while(m0)&(flag=1)flag=0;flag=0;for(j=1;j=m;j+)for(j=1;jrj.keyL-rj+1.key)if(L-rj.keyL-rj+1.key)flag=1;flag=1;x=L-rj;x=L-rj;L-rj=L-L-rj=L-r

34、j+1;rj+1;L-rj+1=x;L-rj+1=x;m-;m-;/每次将最大值放在后面每次将最大值放在后面冒泡排序的演示冒泡排序的演示冒泡排序的算法分析冒泡排序的算法分析时间效率：时间效率：时间效率：时间效率：O O O O（n n n n2 2 2 2)因为要考虑最坏情况因为要考虑最坏情况因为要考虑最坏情况因为要考虑最坏情况空间效率：空间效率：空间效率：空间效率：O O O O（1 1 1 1）只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元稳稳稳稳 定定定定 性：性：性：性：稳定稳定稳定稳定 25252525和和和和25252525

35、*在排序前后的次序未改变在排序前后的次序未改变在排序前后的次序未改变在排序前后的次序未改变详细分析：详细分析：最好情况：最好情况：初始排列已经有序，只执行一趟起泡，做初始排列已经有序，只执行一趟起泡，做n-1次关键码比较，不移动对象。次关键码比较，不移动对象。最坏情形：最坏情形：初始排列逆序，初始排列逆序，算法要执行算法要执行n-1 1趟起泡，第趟起泡，第i趟趟(1 i n)做了做了n-i 次关键码比较，执行了次关键码比较，执行了n-i 次对象交换。次对象交换。此时的比较总次数此时的比较总次数KCN和记录移动次数和记录移动次数RMN为：为：2）快速排序快速排序 从待排序列中任取一个元素从待排序

36、列中任取一个元素从待排序列中任取一个元素从待排序列中任取一个元素 (例如取第一个例如取第一个例如取第一个例如取第一个)作为作为作为作为中心，所有比它小的元素一律前放，所有比它大的元素一中心，所有比它小的元素一律前放，所有比它大的元素一中心，所有比它小的元素一律前放，所有比它大的元素一中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中律后放，形成左右两个子表；然后再对各子表重新选择中律后放，形成左右两个子表；然后再对各子表重新选择中律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。心元素并依此规则

37、调整，直到每个子表的元素只剩一个。心元素并依此规则调整，直到每个子表的元素只剩一个。心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。此时便为有序序列了。此时便为有序序列了。此时便为有序序列了。基本思想：基本思想：基本思想：基本思想：优点：优点：优点：优点：因为每趟可以确定不止一个元素的位置，而且呈指数增因为每趟可以确定不止一个元素的位置，而且呈指数增因为每趟可以确定不止一个元素的位置，而且呈指数增因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！加，所以特别快！加，所以特别快！加，所以特别快！前提：前提：前提：前提：顺序存储结构顺序存储结构顺序存储结构顺序存

38、储结构 ()设以首元素为枢轴中心设以首元素为枢轴中心例例1：关键字序列关键字序列 T=(21，25，49，25*，16，08），），请写出快速排序请写出快速排序的算法步骤。的算法步骤。21，25，49，25*，16，08初态：初态：第第1趟：趟：第第2趟：趟：第第3趟：趟：讨论：讨论：讨论：讨论：1.1.1.1.这种不断划分子表的过程，计算机如何自动实现？这种不断划分子表的过程，计算机如何自动实现？这种不断划分子表的过程，计算机如何自动实现？这种不断划分子表的过程，计算机如何自动实现？2.“2.“2.“2.“快速排序快速排序快速排序快速排序”是否真的比任何排序算法都快？是否真的比任何排序算法都

39、快？是否真的比任何排序算法都快？是否真的比任何排序算法都快？08，16，21，25，25*，(49)2116，08，()25，25*，49(08)，16，21，25，(25*，49)1.1.这种不断划分子表的过程，计算机如何自动实现？这种不断划分子表的过程，计算机如何自动实现？编程时：编程时：每一趟的子表的形成是采用从两头向中间交替式逼近法；每一趟的子表的形成是采用从两头向中间交替式逼近法；由于每趟中对各子表的操作都相似，主程序可采用递归算法。由于每趟中对各子表的操作都相似，主程序可采用递归算法。见教材见教材P275intint PartitionPartitionPartitionParti

40、tion(SqList(SqList&L,L,intint lowlow,intint high high)/一趟快排一趟快排/交换子表交换子表 rlowhighrlowhigh的记录，使支点（枢轴）记录到位，并返回其位置。的记录，使支点（枢轴）记录到位，并返回其位置。返回时，在支点之前的记录均不大于它，支点之后的记录均不小于它。返回时，在支点之前的记录均不大于它，支点之后的记录均不小于它。r0=r0=rlowrlow;/以子表的首记录作为支点记录，放入以子表的首记录作为支点记录，放入r0r0单元单元（续下页）（续下页）一趟快速排序算法一趟快速排序算法（针对一个子表的操作）（针对一个子表的操作

41、）快速排序的演示快速排序的演示pivotkeypivotkey=rlow.keyrlow.key;/取支点的关键码存入取支点的关键码存入pivotkeypivotkey变量变量while(low high)while(low high)/从表的两端交替地向中间扫描从表的两端交替地向中间扫描while(while(lowhighlow=rhigh.key=pivotkeypivotkey)-high;-high;-high;-high;rlow=rhigh;rlow=rhigh;/将比支点小的记录交换到低端；将比支点小的记录交换到低端；while(while(lowhighlowhigh&rlo

42、w.key=rlow.key=pivotkeypivotkey)+low;+low;+low;+low;rhigh=rlow;rhigh=rlow;/将比支点大的记录交换到高端；将比支点大的记录交换到高端；rlow=r0;rlow=r0;/支点记录到位；支点记录到位；return low;return low;/返回支点记录所在位置。返回支点记录所在位置。/PartitionPartitionPartitionPartitionLow=high=3Low=high=3Low=high=3Low=high=3，本趟停止，将本趟停止，将本趟停止，将本趟停止，将支点定位并返回位置信息支点定位并返回位

43、置信息支点定位并返回位置信息支点定位并返回位置信息例例2：关键字序列关键字序列 T=(21，25，49，25*，16，08），），请写请写出快速排序算法的一趟实现过程。出快速排序算法的一趟实现过程。ri0123456初态初态21254925*1608第第1趟趟highhighlowlow210825164925*321pivotkeypivotkey=212108251649(08，16）21（25*，49，25）25252525*跑到了前面，不稳定！跑到了前面，不稳定！跑到了前面，不稳定！跑到了前面，不稳定！voidQSort(SqList&L,intlow,inthigh)if(low 1

44、/对顺序表对顺序表L中的子序列中的子序列rlowhigh 作快速排序作快速排序/一趟快排，将一趟快排，将r一分为二一分为二/在左子区间进行递归快排，直到长度为在左子区间进行递归快排，直到长度为1/在在右子区间进行递归快排，直到长度为右子区间进行递归快排，直到长度为1/QSort新的新的lowvoidvoidQ QuickuickSortSort (SqListSqList&L)&L)QSortQSort (L,(L,1,L.length););对顺序表对顺序表对顺序表对顺序表L L进行快速进行快速进行快速进行快速排序的操作函数为：排序的操作函数为：排序的操作函数为：排序的操作函数为：例例3：以

45、关键字序列（以关键字序列（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，438438076076076076，129129，

46、256256256256，751751751751，937937，863863，742742，694694，301301，438438要求模拟算法实现步骤要求模拟算法实现步骤256256256256076076301301129129751751256256256256076076076076，129129，256256256256，438438，301301，694694，742742，694694，863863，937937751751751751076076076076，129129129129，256256256256，438438438438，301301，694694，742742

47、，751751751751，863863863863，937937076076076076，129129129129，256256256256，301301，301301，694694，742742，751751751751，863863863863，937937438438438438076076076076，129129129129，256256256256，301301301301，438438438438，694694694694，742742，751751751751，863863863863，937937937937时间效率：时间效率：时间效率：时间效率：O(nlogO(nlogO

48、(nlogO(nlog2 2 2 2n)n)n)n)因为每趟确定的元素呈指数增加因为每趟确定的元素呈指数增加因为每趟确定的元素呈指数增加因为每趟确定的元素呈指数增加空间效率：空间效率：空间效率：空间效率：O O O O（loglogloglog2 2 2 2n n n n）因为算法的递归性，要用到栈空间因为算法的递归性，要用到栈空间因为算法的递归性，要用到栈空间因为算法的递归性，要用到栈空间稳稳稳稳 定定定定 性：性：性：性：不稳定不稳定不稳定不稳定 因为可选任一元素为支点。因为可选任一元素为支点。因为可选任一元素为支点。因为可选任一元素为支点。10.4 选择排序选择排序n基本思想基本思想在待

49、排记录中依次选择关键字最小的记录作为有在待排记录中依次选择关键字最小的记录作为有序序列的最后一条记录，逐渐缩小范围直至全部序序列的最后一条记录，逐渐缩小范围直至全部记录选择完毕。记录选择完毕。简单选择排序简单选择排序 49 38 65 97 76 49 38 65 97 76 1313 27 27 4949 1338 65 97 76 49 1338 65 97 76 49 2727 4949 13 2765 97 76 49 13 2765 97 76 49 38 38 4949 13 27 3865 97 76 13 27 3865 97 76 4949 4949 13 27 38 496

50、5 97 76 13 27 38 4965 97 76 4949 13 27 38 49 13 27 38 49 4949 6565 97 76 97 76 13 27 38 49 13 27 38 49 4949 6597 6597 7676 13 27 38 49 13 27 38 49 4949 65 76 97 65 76 97简单选择排序的演示简单选择排序的演示voidSelectSort(SqList&K)/简单选择排序简单选择排序for(i=1;iL.length;+i)/在在L.ri.L.length中选择中选择key最小的记录最小的记录k=i;for(j=i+1;j=L.le