第8章 排序技术.ppt

《第8章 排序技术.ppt》由会员分享，可在线阅读，更多相关《第8章 排序技术.ppt（113页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第8章章 排序技术排序技术概概概概 述述述述 排排序序：给给定定一一组组记记录录的的集集合合r1,r2,rn，其其相相应应的的关关键键码码分分别别为为k1,k2,kn，排排序序是是将将这这些些记记录录排排列列成成顺顺序序为为rs1,rs2,rsn的的一一个个序序列列，使使得得相相应应的的关关键键码码满满足足ks1ks2ksn（称称为为升升序序）或或ks1ks2ksn（称为降序）。称为降序）。正序：正序：待排序序列中的记录已按关键码排好序。待排序序列中的记录已按关键码排好序。逆序（反序）：逆序（反序）：待排序序列中记录的排列顺序与排好待排序序列中记录的排列顺序与排好序的顺序正好相反。序的顺序正

2、好相反。排序的基本概念排序的基本概念排序的基本概念排序的基本概念排序算法的稳定性：排序算法的稳定性：假定在待排序的记录集中，存在假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的多个具有相同键值的记录，若经过排序，这些记录的相对次序相对次序仍然保持不变，即在原序列中，仍然保持不变，即在原序列中，ki=kj且且ri在在rj之前，之前，而在排序后的序列中，而在排序后的序列中，ri仍在仍在rj之前，则称这种之前，则称这种排序算法是稳定的；否则称为不稳定的。排序算法是稳定的；否则称为不稳定的。概概概概 述述述述 排序的基本概念排序的基本概念排序的基本概念排序的基本概念学号学号姓

3、名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明64920003汤晓影汤晓影8586687278概概概概 述述述述 排序的基本概念排序的基本概念排序的基本概念排序的基本概念单键排序：单键排序：根据一个关键码进行的排序；根据一个关键码进行的排序；多键排序：多键排序：根据多个关键码进行的排序。根据多个关键码进行的排序。学号学号姓名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明64920003汤晓影汤晓影8586687278按学号排序按学号排序单键排序单键排序按成绩（高数英语思想品德）排序按成绩（高数英语思想品德）排序多键排序多键排

4、序概概概概 述述述述 排序的基本概念排序的基本概念排序的基本概念排序的基本概念设关键码分别为设关键码分别为k1,k2,km，多键排序有两种方法：，多键排序有两种方法：依次对记录进行依次对记录进行m次排序，第一次按次排序，第一次按k1排序，第二排序，第二次按次按k2排序，依此类推。这种方法要求各趟排序所用排序，依此类推。这种方法要求各趟排序所用的算法是稳定的；的算法是稳定的；将关键码将关键码k1,k2,km分别视为字符串依次首尾连接分别视为字符串依次首尾连接在一起，形成一个新的字符串，然后，对记录序列按在一起，形成一个新的字符串，然后，对记录序列按新形成的字符串排序。新形成的字符串排序。多键排序

5、多键排序单键排序单键排序排序的分类排序的分类1.内排序：内排序：在排序的整个过程中，待排序的所有记录在排序的整个过程中，待排序的所有记录全部被放置在内存中全部被放置在内存中2.外排序外排序：由于待排序的记录个数太多，不能同时放由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。间多次交换数据才能得到排序的结果。概概概概 述述述述 排序的基本概念排序的基本概念排序的基本概念排序的基本概念排序的分类

6、排序的分类1.基于比较：基于比较：基本操作基本操作关键码的比较和记录的移动，关键码的比较和记录的移动，其最差时间下限已经被证明为其最差时间下限已经被证明为（nlog2n）。2.不基于比较不基于比较：根据关键码的分布特征。：根据关键码的分布特征。概概概概 述述述述 排序的基本概念排序的基本概念排序的基本概念排序的基本概念基于比较的内排序基于比较的内排序1.插入排序插入排序（插入排序、希尔排序）（插入排序、希尔排序）2.交换排序交换排序（冒泡排序、快速排序）（冒泡排序、快速排序）3.选择排序选择排序（简单选择排序、堆排序）（简单选择排序、堆排序）4.归并排序归并排序1.基本操作基本操作。内排序在排

7、序过程中的基本操作：。内排序在排序过程中的基本操作：比较比较：关键码之间的比较；：关键码之间的比较；移动移动：记录从一个位置移动到另一个位置。：记录从一个位置移动到另一个位置。2.辅助存储空间辅助存储空间。辅助存储空间是指在数据规模一定的条件下，除了存辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。的其他存储空间。3.算法本身的复杂程度算法本身的复杂程度。排序算法的性能排序算法的性能排序算法的性能排序算法的性能概概概概 述述述述 排序算法的存储结构排序算法的存储结构排序算法的存储结构排序算

8、法的存储结构概概概概 述述述述 从操作角度看，排序是线性结构的一种操作，待排序从操作角度看，排序是线性结构的一种操作，待排序记录可以用记录可以用顺序顺序存储结构或存储结构或链接链接存储结构存储。存储结构存储。假定假定2：将待排序的记录序列排序为将待排序的记录序列排序为升序升序序列。序列。int rn+1;/待排序记录存储在待排序记录存储在r1rn，r0留做他用留做他用假定假定1 1：采用采用顺序顺序存储结构，关键码为存储结构，关键码为整型整型，且记录，且记录只有关键码只有关键码一个一个数据项。数据项。插入排序插入排序插入排序插入排序插入排序的主要操作是插入排序的主要操作是插入插入，其基本思想是

9、：，其基本思想是：每次将一个待排序的记录按其关键码的大小插每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部入到一个已经排好序的有序序列中，直到全部记录排好序为止。记录排好序为止。有序序列有序序列无序序列无序序列r r1r r2r ri-1r rir rnr ri+1基本思想基本思想：在插入第：在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1个记录已经排好序。个记录已经排好序。直接插入排序直接插入排序直接插入排序直接插入排序插入排序插入排序插入排序插入排序有序序列有序序列无序序列无序序列r r1r r2r ri-1r rir rnr ri+1基本思想

10、基本思想：在插入第：在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1个记录已经排好序。个记录已经排好序。（1）如何构造初始的有序序列？）如何构造初始的有序序列？（2）如何查找待插入记录的插入位置）如何查找待插入记录的插入位置?直接插入排序直接插入排序直接插入排序直接插入排序插入排序插入排序插入排序插入排序需解决的关键问题需解决的关键问题?r r1r r2r ri-1r rir rnr ri+1直接插入排序过程示例直接插入排序过程示例直接插入排序过程示例直接插入排序过程示例 r 0 1 2 3 4 5 62121181825252222101025*25*212121212525插

11、入排序插入排序插入排序插入排序i=218182222101025*25*2525i=318182222101025*25*22222525222221211010252521211515101025252525*25252121151510102525*2525212118181515101018181818101025*25*i=41818i=618182525*i=5r0的作用的作用?暂存单元暂存单元监视哨监视哨解决方法：解决方法：将第将第1个记录看成是初始有序表，然后从第个记录看成是初始有序表，然后从第2个记录起个记录起依次插入到这个有序表中，直到将第依次插入到这个有序表中，直到将第n个

12、记录插入。个记录插入。插入排序插入排序插入排序插入排序关键问题关键问题(1)如何构造初始的有序序列？如何构造初始的有序序列？算法描述：算法描述：for(i=2;i=n;i+)插入第插入第i个记录，即第个记录，即第i趟直接插入排序；趟直接插入排序；r 0 1 2 3 4 5 62121181825252222101025*25*关键问题关键问题(2)如何查找待插入记录的插入位置如何查找待插入记录的插入位置?解决方法：解决方法：在在i-1个记录的有序区个记录的有序区r1 ri-1中插入记录中插入记录ri，首，首先顺序查找先顺序查找ri的正确插入位置，然后将的正确插入位置，然后将ri插入到相插入到相

13、应位置。应位置。r0有两个作用：有两个作用：1.进入循环之前暂存了进入循环之前暂存了ri的值，使得不致于因记录的值，使得不致于因记录的后移而丢失的后移而丢失ri的内容；的内容；2.在查找插入位置的循环在查找插入位置的循环中充当中充当哨兵哨兵。插入排序插入排序插入排序插入排序算法描述：算法描述：r0=ri;j=i-1;while(r0rj)rj+1=rj;j-;r 0 1 2 3 4 5 62121181825252222101025*25*2222ijj直接插入排序过程示例直接插入排序过程示例直接插入排序过程示例直接插入排序过程示例 r 0 1 2 3 4 5 6212118182525222

14、2101025*25*212121212525插入排序插入排序插入排序插入排序i=218182222101025*25*2525i=318182222101025*25*22222525222221211010252521211515101025252525*25252121151510102525*2525212118181515101018181818101025*25*i=41818i=618182525*i=5void insertSort(int r,int n)for(i=2;i=n;i+)r0=ri;j=i-1;while(r0=ri-1，内层循，内层循环会出现什么情况环会出现什

15、么情况?r 0 1 2 3 4 5 62121181825252222101025*25*212121212525i=218182222101025*25*2525i=318182222101025*25*22222525222221211010252521211515101025252525*25252121151510102525*2525212118181515101018181818101025*25*i=41818i=618182525*i=5直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析最好情况下（正序）：最好情况下（正序）：插入排

16、序插入排序插入排序插入排序1 12 23 34 45 5时间复杂度为时间复杂度为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 5直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析插入排序插入排序插入排序插入排序最好最好情况下（正序）：情况下（正序）：比较次数：比较次数：n-1移动次数：移动次数：2(n-1)最坏最坏情况下（逆序或反序）：情况下（逆序或反序）：时间复杂度为时间复杂度为O(n

17、2)。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(n)。平均平均情况下（随机排列）：情况下（随机排列）：直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析插入排序插入排序插入排序插入排序时间复杂度为时间复杂度为O(n2)。比较次数：比较次数：移动次数：移动次数：4)1)(4(-+=

18、nnn2=i4)1)(2(2-+=nnnii2（21+i）空间性能：空间性能：需要一个记录的辅助空间。需要一个记录的辅助空间。直接插入排序算法是一种直接插入排序算法是一种稳定稳定的排序算法。的排序算法。直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析插入排序插入排序插入排序插入排序直接插入排序算法简单、容易实现，适用于待排序直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。记录基本有序或待排序记录较小时。当待排序的记录个数较多时，大量的比较和移动操当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低

19、。作使直接插入排序算法的效率降低。插入排序插入排序插入排序插入排序如何改进直接插入排序如何改进直接插入排序?注意到，在插入第注意到，在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1 个个记录已经排好序，则在寻找插入位置时，可以用折半记录已经排好序，则在寻找插入位置时，可以用折半查找来代替顺序查找，从而较少比较次数。查找来代替顺序查找，从而较少比较次数。请同学们写出这个改进的直接插入排序算法，并分析请同学们写出这个改进的直接插入排序算法，并分析时间性能。时间性能。3 34 45 52 21 1 d1希尔排序希尔排序希尔排序希尔排序希尔插入排序过程示例希尔插入排序过程示例希尔插入排序

20、过程示例希尔插入排序过程示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始序列初始序列插入排序插入排序插入排序插入排序303008081313d=4404021212525494925*25*161630300808131325252 21 125*25*303008084949131316164040d=2131325252 21 1080825*25*16163030494940402525212125*25*303008081313161640404949d=1080825252121131325*25*1616303040404949080

21、8252513131616212125*25*404030304949将整个待排序记录将整个待排序记录分割分割成若干个子序列，在子成若干个子序列，在子序列内分别进行直接插入排序序列内分别进行直接插入排序整个序列逐步基本有序整个序列逐步基本有序对全体记录进行直接插入排序对全体记录进行直接插入排序解决方法：解决方法：将相隔某个将相隔某个“增量增量”的记录组成一个子序列。的记录组成一个子序列。增量应如何取？增量应如何取？希尔最早提出的方法是希尔最早提出的方法是d1=n/2，di+1=di/2。关键问题关键问题(1)(1)应如何分割待排序记录？应如何分割待排序记录？插入排序插入排序插入排序插入排序算法

22、描述：算法描述：for(d=n/2;d=1;d=d/2)以以d为增量，进行组内直接插入排序；为增量，进行组内直接插入排序；n=9d1=4d2=2d3=1404021212525494925*25*1616初始序列初始序列303008081313d=4404021212525494925*25*1616303008081313解决方法：解决方法：在插入记录在插入记录ri时，自时，自ri-d起往前跳跃式（跳跃幅起往前跳跃式（跳跃幅度为度为d）搜索待插入位置，并且搜索待插入位置，并且r0只是暂存单元，只是暂存单元，不是哨兵。当搜索位置不是哨兵。当搜索位置0，表示插入位置已找到。，表示插入位置已找到。

23、在搜索过程中，记录后移也是跳跃在搜索过程中，记录后移也是跳跃d个位置。个位置。在整个序列中，前在整个序列中，前d个记录分别是个记录分别是d个子序列中的第个子序列中的第一个记录，所以从第一个记录，所以从第d+1个记录开始进行插入。个记录开始进行插入。插入排序插入排序插入排序插入排序关键问题关键问题(2)子序列内如何进行直接插入排序？子序列内如何进行直接插入排序？d=4404021212525494925*25*1616303008081313算法描述：算法描述：for(i=d+1;i0&r0=1;d=d/2)/以增量为以增量为d d进行直接插入排序进行直接插入排序 for(i=d+1;i0&r0

24、rj;j=j-d)rj+d=rj;/记录后移记录后移d d个位置个位置 rj+d=r0;for(i=1;in;i+)coutri;coutrj+1）rjrj+1；exchange=j；解决方法：解决方法：设变量设变量exchange记载记录交换的位置，则一趟排序后，记载记录交换的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次交记载的一定是这一趟排序中记录的最后一次交换的位置，且从此位置以后的所有记录均已经有序。换的位置，且从此位置以后的所有记录均已经有序。解决方法：解决方法：设设bound位置的记录是无序区的最后一个记录，则每位置的记录是无序区的最后一个记录，则每趟

25、起泡排序的范围是趟起泡排序的范围是r1 rbound。在一趟排序后，从在一趟排序后，从exchange位置之后的记录一定是有位置之后的记录一定是有序的，所以序的，所以bound=exchange。交换排序交换排序交换排序交换排序关键问题关键问题：如何确定起泡排序的范围如何确定起泡排序的范围？050598981212696938385353818105059898696981811212交换交换3838交换交换5353交换交换解决方法：解决方法：设设bound位置的记录是无序区的最后一个记录，则每位置的记录是无序区的最后一个记录，则每趟起泡排序的范围是趟起泡排序的范围是r1 rbound。在一趟

26、排序后，从在一趟排序后，从exchange位置之后的记录一定是有位置之后的记录一定是有序的，所以序的，所以bound=exchange。交换排序交换排序交换排序交换排序关键问题关键问题：如何确定起泡排序的范围如何确定起泡排序的范围？算法描述：算法描述：bound=exchange;for(j=1;jrj+1）rjrj+1；exchange=j；0505989812126969383853538181解决方法：解决方法：在每一趟起泡排序之前，令在每一趟起泡排序之前，令exchange的初值为的初值为0，在在以后的排序过程中，只要有记录交换，以后的排序过程中，只要有记录交换，exchange的的值

27、就会大于值就会大于0。这样，在一趟比较完毕，就可以通过。这样，在一趟比较完毕，就可以通过exchange的值是否为的值是否为0来判别是否有记录交换，从而来判别是否有记录交换，从而判别整个起泡排序的结束。判别整个起泡排序的结束。交换排序交换排序交换排序交换排序关键问题关键问题：如何判别起泡排序的结束？如何判别起泡排序的结束？解决方法：解决方法：在每一趟起泡排序之前，令在每一趟起泡排序之前，令exchange的初值为的初值为0，在在以后的排序过程中，只要有记录交换，以后的排序过程中，只要有记录交换，exchange的的值就会大于值就会大于0。这样，在一趟比较完毕，就可以通过。这样，在一趟比较完毕，

28、就可以通过exchange的值是否为的值是否为0来判别是否有记录交换，从而来判别是否有记录交换，从而判别整个起泡排序的结束。判别整个起泡排序的结束。交换排序交换排序交换排序交换排序关键问题关键问题：如何判别起泡排序的结束？如何判别起泡排序的结束？算法描述：算法描述：while(exchange)执行一趟起泡排序；执行一趟起泡排序；void BubbleSort(int r,int n)exchange=n;while(exchange)bound=exchange;exchange=0；for(j=1;jrj+1)rjrj+1；exchange=j；起泡排序算法起泡排序算法起泡排序算法起泡排序

29、算法交换排序交换排序交换排序交换排序0505989812126969383853538181起泡排序的时间性能分析起泡排序的时间性能分析起泡排序的时间性能分析起泡排序的时间性能分析最好情况（正序）：最好情况（正序）：交换排序交换排序交换排序交换排序比较次数：比较次数：n-1移动次数：移动次数：0 1 12 23 34 45 5时间复杂度为时间复杂度为O(n)。1 12 23 34 45 5最坏情况（反序）：最坏情况（反序）：起泡排序的时间性能分析起泡排序的时间性能分析起泡排序的时间性能分析起泡排序的时间性能分析最好情况（正序）：最好情况（正序）：交换排序交换排序交换排序交换排序比较次数：比较次

30、数：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-1i2)1(1-=n3n3(n-i)n-1i平均情况：平均情况：时间复杂度为时间复杂度为O(n2)。交换排序交换排序交换排序交换排序如何改进起泡排序如何改进起泡排序?1 12 23 34 45 5需扫描需扫描1趟趟5 54 43 32 21 1需扫描需扫描n-1趟趟5 51

31、 12 23 34 4需扫描需扫描2趟趟2 23 34 45 51 1需扫描需扫描n-2趟趟造成不对称的原因是什么造成不对称的原因是什么?交换排序交换排序交换排序交换排序如何改变不对称性如何改变不对称性?2 23 34 45 51 1在排序过程中交替改变扫描方向在排序过程中交替改变扫描方向双向起泡排序双向起泡排序2 23 34 41 15 51 12 23 34 45 5快速排序快速排序快速排序快速排序改进的着眼点：改进的着眼点：在起泡排序中，记录的比较和移动是在起泡排序中，记录的比较和移动是在在相邻相邻单元中进行的，记录每次交换只能上移或下移单元中进行的，记录每次交换只能上移或下移一个一个单

32、元，因而总的比较次数和移动次数较多。单元，因而总的比较次数和移动次数较多。交换排序交换排序交换排序交换排序减少总的比较次数和移动次数减少总的比较次数和移动次数增大记录的比较和移动距离增大记录的比较和移动距离较大记录从前面直接移动到后面较大记录从前面直接移动到后面较小记录从后面直接移动到前面较小记录从后面直接移动到前面快速排序的基本思想快速排序的基本思想快速排序的基本思想快速排序的基本思想首先选一个首先选一个轴值轴值（即比较的基准），通过一趟排序将（即比较的基准），通过一趟排序将待排序记录待排序记录分割分割成独立的两部分，前一部分记录的关成独立的两部分，前一部分记录的关键码均键码均小于或等于小于

33、或等于轴值，后一部分记录的关键码均轴值，后一部分记录的关键码均大大于或等于于或等于轴值，然后分别对这两部分重复上述方法，轴值，然后分别对这两部分重复上述方法，直到整个序列有序。直到整个序列有序。交换排序交换排序交换排序交换排序如何选择轴值？如何选择轴值？如何实现分割（称一次划分）？如何实现分割（称一次划分）？如何处理分割得到的两个待排序子序列？如何处理分割得到的两个待排序子序列？如何判别快速排序的结束？如何判别快速排序的结束？需解决的关键问题需解决的关键问题?13136565272750503838494955551313656527275050494938385555选择轴值的方法：选择轴值

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

35、8494955551313656527275050383849495555ji13133838656527275050494955551313656527275050494938385555交换排序交换排序交换排序交换排序关键问题关键问题：如何实现一次划分？如何实现一次划分？jjiiijijjj解决方法：解决方法：设待划分的序列是设待划分的序列是rs rt，设参数设参数i，j分别指向子分别指向子序列左、右两端的下标序列左、右两端的下标s和和t，令令rs为轴值，为轴值，（1）j从后从后向前向前扫描，直到扫描，直到rjri，将将rj移动到移动到ri的位置，使关键码小（同轴值相比）的记录移动到前的位

36、置，使关键码小（同轴值相比）的记录移动到前面去；面去；（2）i从前从前向后向后扫描，直到扫描，直到rirj，将将ri移动到移动到rj的位置，使关键码大（同轴值比较）的记录移动到后的位置，使关键码大（同轴值比较）的记录移动到后面去；面去；（3）重复上述过程，直到）重复上述过程，直到i=j。交换排序交换排序交换排序交换排序关键问题关键问题：如何实现一次划分？如何实现一次划分？交换排序交换排序交换排序交换排序关键问题关键问题：如何实现一次划分？如何实现一次划分？算法描述：算法描述：int Partition(int r,int first,int end)i=first;j=end;/初始化初始化

37、while(ij)while(ij&ri=rj)j-；/右侧扫描右侧扫描 if(ij)rirj;i+;/将较小记录交换到前面将较小记录交换到前面 while(ij&ri=rj)i+；/左侧扫描左侧扫描 if(ij)rjri;j-;/将较大记录交换到后面将较大记录交换到后面 retutn i;/i为轴值记录的最终位置为轴值记录的最终位置1313656527275050383849495555ji13133838656527275050494955551313656527275050494938385555关键问题关键问题：如何实现一次划分？如何实现一次划分？jjiiijijjjint Parti

38、tion(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-;retutn i;解决方法：解决方法：对分割得到的两个子序列递归地执行快速排序。对分割得到的两个子序列递归地执行快速排序。交换排序交换排序交换排序交换排序关键问题关键问题：如何处理分割得到的两个待排序子序列？：如何处理分割得到的两个待排序子序列？13132727383865655050494955551313272750503838494955556

39、565ijij算法描述：算法描述：交换排序交换排序交换排序交换排序关键问题关键问题：如何处理分割得到的两个待排序子序列？：如何处理分割得到的两个待排序子序列？void QuickSort(int r,int first,int end)pivotpos=Partition(r,first,end);/一次划分一次划分 QuickSort(r,first,pivotpos-1);/对前一个子序列进行快速排序对前一个子序列进行快速排序 QuickSort(r,pivotpos+1,end);/对后一个子序列进行快速排序对后一个子序列进行快速排序解决方法：解决方法：若待排序列中只有一个记录，显然已有

40、序，否则进若待排序列中只有一个记录，显然已有序，否则进行一次划分后，再分别对分割所得的两个子序列进行一次划分后，再分别对分割所得的两个子序列进行快速排序（即递归处理）。行快速排序（即递归处理）。交换排序交换排序交换排序交换排序关键问题关键问题：如何判别快速排序的结束？如何判别快速排序的结束？void QuickSort(int r,int first,int end)/在序列在序列 firstend中递归地进行快速排序中递归地进行快速排序 if(first end)pivotpos=Partition(r,first,end);QuickSort(r,first,pivotpos-1);Qui

41、ckSort(r,pivotpos+1,end);算法描述：算法描述：交换排序交换排序交换排序交换排序关键问题关键问题：如何判别快速排序的结束？如何判别快速排序的结束？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-;retutn i;快速排序的时间性能分析快速排序的时间性能分析交换排序交换排序交换排序交换排序快速排序的时间性能快速排序的时间性能快速排序递归的深度快速排序递归的深度

42、每次划分轴值的选取每次划分轴值的选取最好情况：最好情况：每一次划分对一个记录定位后，该记录的左侧子表与每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为右侧子表的长度相同，为O(nlog2n)。快速排序的时间性能分析快速排序的时间性能分析交换排序交换排序交换排序交换排序T(n)2T(n/2)n 2(2T(n/4)n/2)n4T(n/4)2n 4(2T(n/8)n/4)2n8T(n/8)3n nT(1)nlog2nO(nlog2n)最坏情况：最坏情况：每次划分只得到一个比上一次划分少一个记录的子序每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为列（另一个

43、子序列为空），为 O(n2)。最好情况：最好情况：每一次划分对一个记录定位后，该记录的左侧子表与每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为右侧子表的长度相同，为O(nlog2n)。快速排序的时间性能分析快速排序的时间性能分析交换排序交换排序交换排序交换排序平均情况：平均情况：为为O(nlog2n)。)()1(21211nOnninni=-=-=）（选择排序的主要操作是选择排序的主要操作是选择选择，其主要思想是：，其主要思想是：每趟排序在当前待排序序列中选出关键码每趟排序在当前待排序序列中选出关键码最小最小的记录，添加到有序序列中。的记录，添加到有序序列中。选择排序选择

44、排序选择排序选择排序有序序列有序序列r r1r r2r ri-1r rir rnr rk无序序列无序序列r rnr ri+1r r1r r2r ri-1r rir ri交换交换最小记录最小记录简单选择排序简单选择排序简单选择排序简单选择排序基本思想：基本思想：第第i 趟在趟在n-i+1（i=1,2,n-1）个记录中选个记录中选取关键码最小的记录作为有序序列中的第取关键码最小的记录作为有序序列中的第i个记录。个记录。选择排序选择排序选择排序选择排序需解决的关键问题需解决的关键问题?如何在待排序序列中选出关键码最小的记录？如何在待排序序列中选出关键码最小的记录？如何确定待排序序列中关键码最小的记录

45、在有如何确定待排序序列中关键码最小的记录在有序序列中的位置？序序列中的位置？简单选择排序示例简单选择排序示例08082121i i=2=2最小者最小者 08交换交换21,08最小者最小者 16交换交换25,16最小者最小者 21交换交换49,2121212828i i=1=125251616494908080808i i=3=321210808282849492121选择排序选择排序选择排序选择排序2828494916162525161616162525i i=4=4最小者最小者 25交换交换25,28i i=5=5最小者最小者 28不交换不交换选择排序选择排序选择排序选择排序简单选择排序示例

46、简单选择排序示例494921210808282816162525252549492121080816162828252528284949212108081616282825252828无序区只有无序区只有一个记录一个记录解决方法：解决方法：设置一个整型变量设置一个整型变量index，用于记录在一趟比较的过程用于记录在一趟比较的过程中关键码中关键码最小的记录位置。最小的记录位置。选择排序选择排序选择排序选择排序关键问题关键问题：如何在无序区中选出关键码最小的记录？如何在无序区中选出关键码最小的记录？212128282525161649490808indexindex index0808算法描述：

47、算法描述：index=i;for(j=i+1;j=n;j+)if(rjrindex)index=j;解决方法：解决方法：设置一个整型变量设置一个整型变量index，用于记录在一趟比较的过程用于记录在一趟比较的过程中关键码中关键码最小的记录位置。最小的记录位置。关键问题关键问题：如何在无序区中选出关键码最小的记录？如何在无序区中选出关键码最小的记录？212128282525161649490808indexindex0808解决方法：解决方法：第第i趟简单选择排序的待排序区间是趟简单选择排序的待排序区间是ri rn，则则ri是无是无序序区第一个记录，所以，将区第一个记录，所以，将index所记载

48、的关键码最小的所记载的关键码最小的记录与记录与ri交换交换。选择排序选择排序选择排序选择排序关键问题关键问题：如何确定：如何确定最小记录的最终位置？最小记录的最终位置？算法描述：算法描述：if(index!=i)ririndex;212128282525161649490808 iindex0808void selectSort(int r,int n)for(i=1;in;i+)index=i;for(j=i+1;j=n;j+)if (rjrindex)index=j;if(index!=i)ririndex;简单选择排序算法简单选择排序算法选择排序选择排序选择排序选择排序212128282

49、52516164949080808080808 iindex0808简单选择排序算法的性能分析简单选择排序算法的性能分析移动次数：移动次数：最好情况（正序）：最好情况（正序）：0次次选择排序选择排序选择排序选择排序1 12 23 34 45 51 12 23 34 45 51 12 23 34 45 51 12 23 34 45 51 12 23 34 45 51 12 23 34 4最坏情况：最坏情况：3(n-1)次次简单选择排序算法的性能分析简单选择排序算法的性能分析移动次数：移动次数：最好情况（正序）：最好情况（正序）：0次次选择排序选择排序选择排序选择排序空间性能：空间性能：需一个辅助

50、空间。需一个辅助空间。稳定性：稳定性：是一种稳定的排序算法。是一种稳定的排序算法。4 45 52 23 31 1 1 15 52 23 34 41 12 25 53 34 41 12 23 35 54 41 12 23 34 45 51 12 23 34 4比较次数：比较次数：)()1(21211nOnninni=-=-=）（简单选择排序的时间复杂度为简单选择排序的时间复杂度为O(n2)。交换一次元素移动交换一次元素移动3次次堆排序堆排序改进的着眼点：改进的着眼点：如何如何减少减少关键码间的关键码间的比较比较次数。若次数。若能利用每趟比较后的结果，也就是在找出键值最小能利用每趟比较后的结果，也