数据结构王红梅排序技术学习教案.pptx

《数据结构王红梅排序技术学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构王红梅排序技术学习教案.pptx（130页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构王红梅排序数据结构王红梅排序(pi x)技术技术第一页，共130页。8.1 8.1 概概概概 述述述述 p 排排序序：给给定定一一组组记记录录的的集集合合r1,r2,rn，其其相相应应的的关关键键码码分分别别(fnbi)为为k1,k2,kn，排排序序是是将将这这些些记记录录排排列列成成顺顺序序为为rs1,rs2,rsn的的一一个个序序列列，使使得得相相应应的的关关键键码码满满足足ks1ks2ksn（称称为为升升序序）或或ks1ks2ksn（称为降序）。（称为降序）。p 正序：待排序序列中的记录已按关键码排好序。正序：待排序序列中的记录已按关键码排好序。p 逆逆序序（反反序序）：

2、待待排排序序序序列列中中记记录录的的排排列列顺顺序序与与排排好好序序的的顺顺序正好相反。序正好相反。排序排序排序排序(pi x)(pi x)的基的基的基的基本概念本概念本概念本概念从操作角度看，排序是线性结构从操作角度看，排序是线性结构(jigu)的一种操作的一种操作 第1页/共130页第二页，共130页。排序算法的稳定性：假定在待排序的记录集中，存在排序算法的稳定性：假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的多个具有相同键值的记录，若经过排序，这些记录的相对相对(xingdu)次序仍然保持不变，即在原序列中，次序仍然保持不变，即在原序列中，ki=kj且且ri在

3、在rj之前，而在排序后的序列中，之前，而在排序后的序列中，ri仍在仍在rj之之前，则称这种排序算法是稳定的；否则称为不稳定的。前，则称这种排序算法是稳定的；否则称为不稳定的。排序排序排序排序(pi x)(pi x)的基本的基本的基本的基本概念概念概念概念学号学号姓名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明64920003汤晓影汤晓影85866872788.1 8.1 概概概概 述述述述 第2页/共130页第三页，共130页。排序排序排序排序(pi x)(pi x)的基的基的基的基本概念本概念本概念本概念单键单键(dn jin)排序：根据一个关键码进行的排

4、序；排序：根据一个关键码进行的排序；多键排序：根据多个关键码进行的排序。多键排序：根据多个关键码进行的排序。学号学号姓名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明64920003汤晓影汤晓影8586687278按学号排序按学号排序(pi x)单键排序单键排序(pi x)按成绩（高数英语思想品德）排序按成绩（高数英语思想品德）排序(pi x)多键排序多键排序(pi x)8.1 8.1 概概概概 述述述述 第3页/共130页第四页，共130页。排序排序排序排序(pi x)(pi x)的基本概的基本概的基本概的基本概念念念念设关键码分别为设关键码分别为设关键码分

5、别为设关键码分别为k1,k2,kmk1,k2,km，多键排序，多键排序，多键排序，多键排序(pi x)(pi x)有两种有两种有两种有两种方法：方法：方法：方法：依次对记录进行依次对记录进行依次对记录进行依次对记录进行mm次排序次排序次排序次排序(pi x)(pi x)，第一次按，第一次按，第一次按，第一次按k1k1排序排序排序排序(pi x)(pi x)，第二次按，第二次按，第二次按，第二次按k2k2排序排序排序排序(pi x)(pi x)，依此类推。这种方，依此类推。这种方，依此类推。这种方，依此类推。这种方法要求各趟排序法要求各趟排序法要求各趟排序法要求各趟排序(pi x)(pi x)所

6、用的算法是稳定的；所用的算法是稳定的；所用的算法是稳定的；所用的算法是稳定的；将关键码将关键码将关键码将关键码k1,k2,kmk1,k2,km分别视为字符串依次首尾连接分别视为字符串依次首尾连接分别视为字符串依次首尾连接分别视为字符串依次首尾连接在一起，形成一个新的字符串，然后，对记录序列按新在一起，形成一个新的字符串，然后，对记录序列按新在一起，形成一个新的字符串，然后，对记录序列按新在一起，形成一个新的字符串，然后，对记录序列按新形成的字符串排序形成的字符串排序形成的字符串排序形成的字符串排序(pi x)(pi x)。多键排序多键排序单键排序单键排序8.1 8.1 概概概概 述述述述 第4

7、页/共130页第五页，共130页。排序的分类排序的分类1.内排序：在排序的整个过程中，待排序的所有记录全内排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中部被放置在内存中2.外排序：由于外排序：由于(yuy)待排序的记录个数太多，不能待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。之间多次交换数据才能得到排序的结果。排序排序排序排序(pi x)(pi x)的基本概的基本概的基本概

8、的基本概念念念念8.1 8.1 概概概概 述述述述 第5页/共130页第六页，共130页。排序的分类排序的分类排序的分类排序的分类1.1.基于比较：基本操作基于比较：基本操作基于比较：基本操作基于比较：基本操作关键码的比较和记录的移动关键码的比较和记录的移动关键码的比较和记录的移动关键码的比较和记录的移动(ydng)(ydng)，其最差时间下限已经被证明为，其最差时间下限已经被证明为，其最差时间下限已经被证明为，其最差时间下限已经被证明为（nlog2nnlog2n）。）。）。）。（1 1）插入排序）插入排序）插入排序）插入排序（2 2）交换排序）交换排序）交换排序）交换排序（3 3）选择排序）

9、选择排序）选择排序）选择排序（4 4）归并排序）归并排序）归并排序）归并排序2.2.不基于比较：根据关键码的分布特征。不基于比较：根据关键码的分布特征。不基于比较：根据关键码的分布特征。不基于比较：根据关键码的分布特征。排序排序排序排序(pi x)(pi x)的基本的基本的基本的基本概念概念概念概念8.1 8.1 概概概概 述述述述 第6页/共130页第七页，共130页。1.基本操作。内排序基本操作。内排序(pi x)在排序在排序(pi x)过程中的基本操作：过程中的基本操作：比较：关键码之间的比较；比较：关键码之间的比较；移动：记录从一个位置移动到另一个位置。移动：记录从一个位置移动到另一个

10、位置。2.辅助存储空间。辅助存储空间。辅助存储空间是指在数据规模一定的条件下，除了存放待排序辅助存储空间是指在数据规模一定的条件下，除了存放待排序(pi x)记录占用的存储空间之外，执行算法所需要的其他存储记录占用的存储空间之外，执行算法所需要的其他存储空间。空间。3.算法本身的复杂程度。算法本身的复杂程度。排序算法排序算法排序算法排序算法(sun f)(sun f)的性能的性能的性能的性能8.1 8.1 概概概概 述述述述 第7页/共130页第八页，共130页。排序算法排序算法排序算法排序算法(sun f)(sun f)的存储结构的存储结构的存储结构的存储结构从操作从操作(cozu)角度看，

11、排序是线性结构的一种操作角度看，排序是线性结构的一种操作(cozu)，待排序记录可以用顺序存储结构或链接存，待排序记录可以用顺序存储结构或链接存储结构存储。储结构存储。假定假定2：将待排序：将待排序(pi x)的记录序列排序的记录序列排序(pi x)为升序序列。为升序序列。int rn+1;/待排序记录存储在待排序记录存储在r1rn，r0留做他用留做他用假定假定1 1：采用采用顺序顺序存储结构，关键码为存储结构，关键码为整型整型，且记录只有，且记录只有关键码关键码一个一个数据项。数据项。8.1 8.1 概概概概 述述述述 第8页/共130页第九页，共130页。8.2 8.2 插入排序插入排序插

12、入排序插入排序插入排序的主要操作是插入，其基本思想是：每插入排序的主要操作是插入，其基本思想是：每次将一个待排序的记录按其关键码的大小次将一个待排序的记录按其关键码的大小(dxio)插入到一个已经排好序的有序序列中，插入到一个已经排好序的有序序列中，直到全部记录排好序为止。直到全部记录排好序为止。第9页/共130页第十页，共130页。基本思想：在插入基本思想：在插入(ch r)第第 i（i1）个记录时，前面的）个记录时，前面的 i-1个记录已经排好序。个记录已经排好序。直接直接直接直接(zhji)(zhji)插入排序插入排序插入排序插入排序有序序列有序序列无序序列无序序列r r1r r2r r

13、i-1r rir rnr ri+1r r1r r2r ri-1r rir rnr ri+18.2 8.2 插入排序插入排序插入排序插入排序第10页/共130页第十一页，共130页。基本思想基本思想(sxing)：在插入第：在插入第 i（i1）个记录时，前面）个记录时，前面的的 i-1个记录已经排好序。个记录已经排好序。（1）如何构造初始(ch sh)的有序序列？（2）如何查找待插入记录的插入位置?直接直接直接直接(zhji)(zhji)插入排序插入排序插入排序插入排序需解决的关键问题需解决的关键问题?8.2 8.2 插入排序插入排序插入排序插入排序第11页/共130页第十二页，共130页。直接

14、插入排序过程直接插入排序过程直接插入排序过程直接插入排序过程直接插入排序过程直接插入排序过程(guchng)(guchng)(guchng)(guchng)(guchng)(guchng)示例示例示例示例示例示例 r 0 1 2 3 4 5 62121181825252222101025*25*212121212525i=218182222101025*25*2525i=318182222101025*25*22222525222221211010252521211515101025252525*25252121151510102525*2525212118181515101018181818

15、101025*25*i=41818i=618182525*i=5r0的作用的作用?暂存单元暂存单元(dnyun)监视哨监视哨8.2 8.2 插入排序插入排序插入排序插入排序第12页/共130页第十三页，共130页。解决方法：解决方法：将第将第1个记录看成是初始有序表，然后从第个记录看成是初始有序表，然后从第2个记录起依次个记录起依次插入插入(ch r)到这个有序表中，直到将第到这个有序表中，直到将第n个记录插入个记录插入(ch r)。关键问题关键问题(1)如何构造初始如何构造初始(ch sh)的有序序列？的有序序列？算法描述算法描述(mio sh)：for(i=2;i=n;i+)插入第插入第i

16、个记录，即第个记录，即第i趟直接插入排序；趟直接插入排序；8.2 8.2 插入排序插入排序插入排序插入排序第13页/共130页第十四页，共130页。关键问题关键问题(2)如何查找待插入记录如何查找待插入记录(jl)的插入位置的插入位置?解决方法：解决方法：在在i-1个记录的有序区个记录的有序区r1 ri-1中插入记录中插入记录ri，首先，首先(shuxin)顺序查找顺序查找ri的正确插入位置，然后将的正确插入位置，然后将ri插入插入到相应位置。到相应位置。r0有两个作用：有两个作用：1.进入循环之前进入循环之前(zhqin)暂存了暂存了ri的值，使得不的值，使得不致于因记录的后移而丢失致于因记

17、录的后移而丢失ri的内容；的内容；2.在查找插入位置的循环在查找插入位置的循环中充当哨兵。中充当哨兵。算法描述：算法描述：r0=ri;j=i-1;while(r0rj)rj+1=rj;j-;8.2 8.2 插入排序插入排序插入排序插入排序第14页/共130页第十五页，共130页。void insertSort(int r,int n)for(i=2;i=n;i+)r0=ri;j=i-1;while(r0=ri-1，内层循，内层循环会出现什么情况环会出现什么情况?8.2 8.2 插入排序插入排序插入排序插入排序第15页/共130页第十六页，共130页。直接直接直接直接(zhji)(zhji)插入

18、排序算法性能插入排序算法性能插入排序算法性能插入排序算法性能分析分析分析分析最好最好(zu ho)(zu ho)情况下（正序）：情况下（正序）：1 12 23 34 45 5时间时间(shjin)复杂度为复杂度为O(n)。比较次数：比较次数：n-1移动次数：移动次数：2(n-1)1 12 23 34 45 51 12 23 34 45 51 12 23 34 45 51 12 23 34 45 52 23 34 45 58.2 8.2 插入排序插入排序插入排序插入排序第16页/共130页第十七页，共130页。直接直接直接直接(zhji)(zhji)插入排序算法性能分插入排序算法性能分插入排序算

19、法性能分插入排序算法性能分析析析析最好最好(zu ho)(zu ho)情况下（正序）：情况下（正序）：比较次数：比较次数：n-1移动次数：移动次数：2(n-1)最坏情况最坏情况(qngkung)(qngkung)下（逆下（逆序或反序）：序或反序）：时间复杂度为时间复杂度为O(n2)。5 54 43 32 21 14 45 53 32 21 13 34 45 52 21 12 23 34 45 51 11 12 23 34 45 54 43 32 21 1比较次数：比较次数：移动次数：移动次数：2)1)(2(2-+=nnini2)1)(4(1-+=+nnin2=i）（时间复杂度为时间复杂度为O(

20、n)。8.2 8.2 插入排序插入排序插入排序插入排序第17页/共130页第十八页，共130页。平均情况下（随机平均情况下（随机(su j)(su j)排列）：排列）：直接直接直接直接(zhji)(zhji)插入排序算法性能分插入排序算法性能分插入排序算法性能分插入排序算法性能分析析析析时间时间(shjin)复杂度为复杂度为O(n2)。比较次数：比较次数：移动次数：移动次数：4)1)(4(-+=nnn2=i4)1)(2(2-+=nnnii2（21+i）8.2 8.2 插入排序插入排序插入排序插入排序第18页/共130页第十九页，共130页。空间性能：需要一个空间性能：需要一个(y)记录的辅助空

21、间。记录的辅助空间。直接插入排序算法是一种稳定的排序算法。直接插入排序算法是一种稳定的排序算法。直接直接直接直接(zhji)(zhji)插入排序算法性能插入排序算法性能插入排序算法性能插入排序算法性能分析分析分析分析直接插入排序算法简单、容易直接插入排序算法简单、容易(rngy)实现，适实现，适用于待排序记录基本有序或待排序记录较小时。用于待排序记录基本有序或待排序记录较小时。当待排序的记录个数较多时，大量的比较和移动当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。操作使直接插入排序算法的效率降低。8.2 8.2 插入排序插入排序插入排序插入排序第19页/共130页

22、第二十页，共130页。如何改进直接插入排序如何改进直接插入排序?注意到，在插入第注意到，在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1 个记录已个记录已经经(y jing)排好序，则在寻找插入位置时，可以用折半查找排好序，则在寻找插入位置时，可以用折半查找来代替顺序查找，从而减少比较次数。来代替顺序查找，从而减少比较次数。请同学们写出这个改进的直接插入排序算法请同学们写出这个改进的直接插入排序算法(sun f)，并，并分析时间性能。分析时间性能。8.2 8.2 插入排序插入排序插入排序插入排序第20页/共130页第二十一页，共130页。希尔排序希尔排序希尔排序希尔排序(pi x

23、)(pi x)改进的着眼点：改进的着眼点：（1 1）若待排序记录按关键码基本有序时，直接插入排）若待排序记录按关键码基本有序时，直接插入排序的效率可以序的效率可以(ky)(ky)大大提高；大大提高；（2 2）由于直接插入排序算法简单，则在待排序记录数）由于直接插入排序算法简单，则在待排序记录数量量n n较小时效率也很高。较小时效率也很高。8.2 8.2 插入排序插入排序插入排序插入排序第21页/共130页第二十二页，共130页。（1 1）应如何分割待排序记录，才能保证整个序列逐步）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？向基本有序发展？（2 2）子序列内如何进行）子序列内如何

24、进行(jnxng)(jnxng)直接插入排序？直接插入排序？需解决的关键问题需解决的关键问题?基本基本(jbn)(jbn)思想：将整个待排序记录分割成若干个子思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本中的记录基本(jbn)(jbn)有序时，对全体记录进行直接插有序时，对全体记录进行直接插入排序。入排序。希尔排序希尔排序希尔排序希尔排序(pi x)(pi x)8.2 8.2 插入排序插入排序插入排序插入排序第22页/共130页第二十三页，共130页。基本有序：接近正序，例如基本有序：接近正序，例

25、如1,2,8,4,5,6,7,3,9；局部有序：部分有序，例如局部有序：部分有序，例如6,7,8,9,1,2,3,4,5。局部有序不能提高直接插入排序算法局部有序不能提高直接插入排序算法(sun f)的时间的时间性能。性能。希尔排序希尔排序希尔排序希尔排序(pi x)(pi x)分割待排序记录的目的分割待排序记录的目的?1.减少待排序减少待排序(pi x)记录个数；记录个数；2.使整个序列向基本有序发展。使整个序列向基本有序发展。子序列的构成不能是简单地子序列的构成不能是简单地“逐段分割逐段分割”，而是将相距某，而是将相距某个个“增量增量”的记录组成一个子序列。的记录组成一个子序列。启示启示?

26、8.2 8.2 插入排序插入排序插入排序插入排序第23页/共130页第二十四页，共130页。希尔插入排序过程希尔插入排序过程希尔插入排序过程希尔插入排序过程希尔插入排序过程希尔插入排序过程(guchng)(guchng)(guchng)(guchng)(guchng)(guchng)示例示例示例示例示例示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始初始(ch sh)序列序列303008081313d=4404021212525494925*25*161630300808131325252 21 125*25*303008084949131316

27、164040d=2131325252 21 1080825*25*16163030494940402525212125*25*303008081313161640404949d=1080825252121131325*25*16163030404049490808252513131616212125*25*4040303049498.2 8.2 插入排序插入排序插入排序插入排序第24页/共130页第二十五页，共130页。解决方法：解决方法：将相隔某个将相隔某个“增量增量”的记录组成一个子序列的记录组成一个子序列(xli)。增量应如何取？增量应如何取？希尔最早提出的方法是希尔最早提出的方法是d1

28、=n/2，di+1=di/2。关键问题关键问题(1)(1)应如何分割应如何分割(fng)(fng)待排序待排序记录？记录？算法描述：算法描述：for(d=n/2;d=1;d=d/2)以以d为增量为增量(zn lin)，进行组内直接插入排序；，进行组内直接插入排序；8.2 8.2 插入排序插入排序插入排序插入排序第25页/共130页第二十六页，共130页。解决方法：解决方法：在插入记录在插入记录riri时，自时，自ri-dri-d起往前跳跃起往前跳跃(tioyu)(tioyu)式式（跳跃（跳跃(tioyu)(tioyu)幅度为幅度为d d）搜索待插入位置，并且）搜索待插入位置，并且r0r0只只是

29、暂存单元，不是哨兵。当搜索位置是暂存单元，不是哨兵。当搜索位置0 0，表示插入位置，表示插入位置已找到。已找到。在搜索过程中，记录后移也是跳跃在搜索过程中，记录后移也是跳跃(tioyu)d(tioyu)d个位置。个位置。在整个序列中，前在整个序列中，前d d个记录分别是个记录分别是d d个子序列中的第一个记个子序列中的第一个记录，所以从第录，所以从第d+1d+1个记录开始进行插入。个记录开始进行插入。关键问题关键问题(2)(2)子序列子序列(xli)(xli)内如何进行直接插入排序内如何进行直接插入排序？8.2 8.2 插入排序插入排序插入排序插入排序第26页/共130页第二十七页，共130页

30、。希尔插入排序过程希尔插入排序过程希尔插入排序过程希尔插入排序过程希尔插入排序过程希尔插入排序过程(guchng)(guchng)(guchng)(guchng)(guchng)(guchng)示例示例示例示例示例示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始初始(ch sh)序列序列303008081313d=4404021212525494925*25*161630300808131316164040ij1616j8.2 8.2 插入排序插入排序插入排序插入排序第27页/共130页第二十八页，共130页。希尔插入排序过程希尔插入排序过程希尔

31、插入排序过程希尔插入排序过程希尔插入排序过程希尔插入排序过程(guchng)(guchng)(guchng)(guchng)(guchng)(guchng)示例示例示例示例示例示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始初始(ch sh)序列序列303008081313d=4404021212525494925*25*161630300808131325252 21 116164040ij2 21 1j8.2 8.2 插入排序插入排序插入排序插入排序第28页/共130页第二十九页，共130页。希尔插入排序过程希尔插入排序过程希尔插入排序过程希

32、尔插入排序过程希尔插入排序过程希尔插入排序过程(guchng)(guchng)(guchng)(guchng)(guchng)(guchng)示例示例示例示例示例示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始初始(ch sh)序列序列303008081313d=4404021212525494925*25*161630300808131325252 21 116164040ij494908080808j8.2 8.2 插入排序插入排序插入排序插入排序第29页/共130页第三十页，共130页。希尔插入排序过程希尔插入排序过程希尔插入排序过程希尔插

33、入排序过程希尔插入排序过程希尔插入排序过程(guchng)(guchng)(guchng)(guchng)(guchng)(guchng)示例示例示例示例示例示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始初始(ch sh)序列序列303008081313d=4404021212525494925*25*161630300808131325252 21 116164040ij4949080825*25*303030308.2 8.2 插入排序插入排序插入排序插入排序第30页/共130页第三十一页，共130页。希尔插入排序过程希尔插入排序过程希尔插

34、入排序过程希尔插入排序过程希尔插入排序过程希尔插入排序过程(guchng)(guchng)(guchng)(guchng)(guchng)(guchng)示例示例示例示例示例示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始初始(ch sh)序列序列303008081313d=4404021212525494925*25*161630300808131325252 21 116164040ij4949080825*25*30304040131316161313jj8.2 8.2 插入排序插入排序插入排序插入排序第31页/共130页第三十二页，共13

35、0页。算法算法(sun f)描述：描述：for(i=d+1;i0&r0rj+1）rjrj+1；exchange=j；解决方法：解决方法：设变量设变量exchange记载记录交换的位置，则一趟排序后，记载记录交换的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后记载的一定是这一趟排序中记录的最后(zuhu)一次交换的位置，一次交换的位置，且从此位置以后的所有记录均已经有序。且从此位置以后的所有记录均已经有序。8.3 8.3 交换排序交换排序交换排序交换排序第39页/共130页第四十页，共130页。解决方法：解决方法：设设bound位置的记录是无序区的最后一个记录，则每趟起位

36、置的记录是无序区的最后一个记录，则每趟起泡排序的范围是泡排序的范围是r1 rbound。在一趟排序后，从在一趟排序后，从exchange位置之后的记录一定位置之后的记录一定(ydng)是有序的，所以是有序的，所以bound=exchange。关键问题关键问题：如何：如何(rh)(rh)确定起泡排序的范围？确定起泡排序的范围？050598981212696938385353818105059898696981811212交换交换3838交换交换5353交换交换8.3 8.3 交换交换交换交换(jiohun)(jiohun)排序排序排序排序第40页/共130页第四十一页，共130页。解决解决(ji

37、ju)方法：方法：设设bound位置的记录是无序区的最后一个记录，则每位置的记录是无序区的最后一个记录，则每趟起泡排序的范围是趟起泡排序的范围是r1 rbound。在一趟排序后，从在一趟排序后，从exchange位置之后的记录一定是有位置之后的记录一定是有序的，所以序的，所以bound=exchange。关键问题关键问题：如何确定：如何确定(qudng)(qudng)起泡排序的范围？起泡排序的范围？算法算法(sun f)描述：描述：bound=exchange;for(j=1;jrj+1）rjrj+1；exchange=j；8.3 8.3 交换排序交换排序交换排序交换排序第41页/共130页第

38、四十二页，共130页。0505989812126969383853538181解决方法：解决方法：在每一趟起泡排序之前，令在每一趟起泡排序之前，令exchangeexchange的初值为的初值为0 0，在，在以后的排序过程中，只要有记录交换，以后的排序过程中，只要有记录交换，exchangeexchange的的值就会大于值就会大于0 0。这样。这样(zhyng)(zhyng)，在一趟比较完毕，在一趟比较完毕，就可以通过就可以通过exchangeexchange的值是否为的值是否为0 0来判别是否有记录来判别是否有记录交换，从而判别整个起泡排序的结束。交换，从而判别整个起泡排序的结束。关键问题关

39、键问题：如何判别起泡：如何判别起泡(q po)(q po)排序的结束？排序的结束？8.3 8.3 交换交换交换交换(jiohun)(jiohun)排序排序排序排序第42页/共130页第四十三页，共130页。解决方法：解决方法：在每一趟起泡排序之前，令在每一趟起泡排序之前，令exchangeexchange的初值为的初值为0 0，在以后的，在以后的排序过程中，只要有记录交换，排序过程中，只要有记录交换，exchangeexchange的值就会大于的值就会大于0 0。这样，在一趟比较完毕，就可以这样，在一趟比较完毕，就可以(ky)(ky)通过通过exchangeexchange的值是的值是否为否为

40、0 0来判别是否有记录交换，从而判别整个起泡排序的结来判别是否有记录交换，从而判别整个起泡排序的结束。束。关键问题关键问题：如何：如何(rh)(rh)判别起泡排序的结束？判别起泡排序的结束？算法描述：算法描述：while(exchange)执行一趟起泡执行一趟起泡(q po)排序；排序；8.3 8.3 交换排序交换排序交换排序交换排序第43页/共130页第四十四页，共130页。void BubbleSort(int r,int n)exchange=n;while(exchange)bound=exchange;exchange=0；for(j=1;jrj+1)rjrj+1；exchange=

41、j；起泡起泡起泡起泡(q po)(q po)排序算法排序算法排序算法排序算法8.3 8.3 交换交换交换交换(jiohun)(jiohun)排序排序排序排序第44页/共130页第四十五页，共130页。起泡排序的时间性能起泡排序的时间性能起泡排序的时间性能起泡排序的时间性能(xngnng)(xngnng)分析分析分析分析最好最好(zu ho)情况（正序）：情况（正序）：比较次数：比较次数：n-1移动次数：移动次数：0 1 12 23 34 45 5时间时间(shjin)复杂度为复杂度为O(n)。1 12 23 34 45 58.3 8.3 交换排序交换排序交换排序交换排序第45页/共130页第四

42、十六页，共130页。最坏情况最坏情况(qngkung)(qngkung)（反序）：（反序）：起泡起泡起泡起泡(q po)(q po)排序的时间性能分排序的时间性能分排序的时间性能分排序的时间性能分析析析析最好最好(zu ho)情况（正序）：情况（正序）：比较次数：比较次数：n-1移动次数：移动次数：0 5 54 43 32 21 1时间复杂度为时间复杂度为O(n)；时间复杂度为时间复杂度为O(n2)。4 43 32 21 15 53 32 21 14 45 52 21 13 34 45 51 12 23 34 45 5比较次数：比较次数：移动次数：移动次数：2)1(1-=nn(n-i)n-1i

43、2)1(1-=n3n3(n-i)n-1i平均情况：平均情况：时间复杂度为时间复杂度为O(n2)。8.3 8.3 交换排序交换排序交换排序交换排序第46页/共130页第四十七页，共130页。快速快速快速快速(kui s)(kui s)(kui s)(kui s)排序排序排序排序改进的着眼点：在起泡排序中，记录的比较和移动是在相邻改进的着眼点：在起泡排序中，记录的比较和移动是在相邻单元中进行的，记录每次交换只能上移或下移一个单元，因单元中进行的，记录每次交换只能上移或下移一个单元，因而而(yn r)总的比较次数和移动次数较多。总的比较次数和移动次数较多。减少减少(jinsho)总的比较次数和移动次

44、数总的比较次数和移动次数增大记录的比较和移动距离增大记录的比较和移动距离较大记录从前面直接移动到后面较大记录从前面直接移动到后面较小记录从后面直接移动到前面较小记录从后面直接移动到前面8.3 8.3 交换排序交换排序交换排序交换排序第47页/共130页第四十八页，共130页。快速排序快速排序快速排序快速排序(pi x)(pi x)的基本思想的基本思想的基本思想的基本思想首先选一个轴值（即比较的基准），通过一趟排序首先选一个轴值（即比较的基准），通过一趟排序(pi x)将将待排序待排序(pi x)记录分割成独立的两部分，前一部分记录的关记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值

45、，后一部分记录的关键码均大于或等于键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。轴值，然后分别对这两部分重复上述方法，直到整个序列有序。如何选择轴值？如何选择轴值？如何实现如何实现(shxin)分割（称一次划分）？分割（称一次划分）？如何处理分割得到的两个待排序子序列？如何处理分割得到的两个待排序子序列？如何判别快速排序的结束？如何判别快速排序的结束？需解决的关键问题需解决的关键问题?8.3 8.3 交换排序交换排序交换排序交换排序第48页/共130页第四十九页，共130页。选择轴值的方法：选择轴值的方法：1.使用第一个记录的关键

46、码；使用第一个记录的关键码；2.选取序列中间记录的关键码；选取序列中间记录的关键码；3.比较序列中第一个记录、最后一个记录和中间记录比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的关键码，取关键码居中(jzhng)的作为轴值并调的作为轴值并调换到第一个记录的位置；换到第一个记录的位置；4.随机选取轴值。随机选取轴值。关键问题关键问题：如何：如何(rh)(rh)选择轴值？选择轴值？选取不同轴值的后果选取不同轴值的后果(hugu)：决定两个子序列的长度，子序列的长度最好相等。决定两个子序列的长度，子序列的长度最好相等。8.3 8.3 交换排序交换排序交换排序交换排序第49页/共

47、130页第五十页，共130页。1313656527275050383849495555ji13133838656527275050494955551313656527275050494938385555关键问题关键问题：如何实现：如何实现(shxin)(shxin)一次划分？一次划分？jjiiijijjj8.3 8.3 交换交换交换交换(jiohun)(jiohun)排序排序排序排序第50页/共130页第五十一页，共130页。解决方法：解决方法：设待划分的序列是设待划分的序列是rs rt，设参数，设参数i，j分别指向子分别指向子序列左、右两端的下标序列左、右两端的下标s和和t，令，令rs为轴值

48、，为轴值，（1）j从后向前从后向前(xin qin)扫描，直到扫描，直到rjri，将，将rj移动到移动到ri的位置，使关键码小（同轴值相比）的的位置，使关键码小（同轴值相比）的记录移动到前面去；记录移动到前面去；（2）i从前向后扫描，直到从前向后扫描，直到rirj，将，将ri移动到移动到rj的位置，使关键码大（同轴值比较）的记录移动的位置，使关键码大（同轴值比较）的记录移动到后面去；到后面去；（3）重复上述过程，直到）重复上述过程，直到i=j。关键问题关键问题：如何实现：如何实现(shxin)(shxin)一次划分？一次划分？8.3 8.3 交换交换交换交换(jiohun)(jiohun)排序

49、排序排序排序第51页/共130页第五十二页，共130页。关键问题关键问题：如何：如何(rh)(rh)实现一次划分？实现一次划分？算法算法(sun f)描述：描述：int Partition(int r,int first,int end)i=first;j=end;/初始化初始化 while(ij)while(ij&ri=rj)j-；/右侧扫描右侧扫描 if(ij)rirj;i+;/将较小记录交换到前面将较小记录交换到前面 while(ij&ri=rj)i+；/左侧扫描左侧扫描 if(ij)rjri;j-;/将较大记录交换到后面将较大记录交换到后面(hu mian)retutn i;/i为轴值

50、记录的最终位置为轴值记录的最终位置8.3 8.3 交换排序交换排序交换排序交换排序第52页/共130页第五十三页，共130页。解决方法解决方法(fngf)(fngf)：对分割得到的两个子序列递归地执行快速排序。对分割得到的两个子序列递归地执行快速排序。关键问题关键问题：如何：如何(rh)(rh)处理分割得到的两个待排序子序列？处理分割得到的两个待排序子序列？13132727383865655050494955551313272750503838494955556565ijij8.3 8.3 交换交换交换交换(jiohun)(jiohun)排序排序排序排序第53页/共130页第五十四页，共130