数据结构及算法-排序.ppt

《数据结构及算法-排序.ppt》由会员分享，可在线阅读，更多相关《数据结构及算法-排序.ppt（116页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章第八章第八章第八章 排序技术排序技术排序技术排序技术本章的基本内容是：本章的基本内容是：排序的基本概念排序的基本概念插入排序插入排序交换排序交换排序选择排序选择排序归并排序归并排序 8.18.18.18.1概概概概 述述述述 排排序序：将将一一组组“无无序序”的的记记录录序序列列,调调整整为为按按关关键键字字“有有序序”的记录序列的记录序列.学号学号姓名姓名高数高数英语英语思想品德思想品德0002王王 军军85880001李李 明明64920003汤晓影汤晓影85866872781.1.排序的基本概念排序的基本概念排序的基本概念排序的基本概念排排序序：给给定定一一组组记记录录的的集集合合

2、r1,r2,rn，其其相相应应的的关关键键码码分分别别为为k1,k2,kn，排排序序是是将将这这些些记记录录排排列列成成顺顺序序为为rs1,rs2,rsn的的一一个个序序列列，使使得得相相应应的的关关键键码码满满足足非非递递减减关关系系ks1ks2ksn（称称为为升升序序）或或非非递递增增关关系系ks1ks2ksn（称为称为降序降序）。）。1.1.排序的基本概念排序的基本概念排序的基本概念排序的基本概念学号学号姓名姓名高数高数英语英语0002李李 明明640001王王 军军850003汤晓影汤晓影85726878学号学号姓名姓名高数高数英语英语0001王王 军军850002李李 明明64000

3、3汤晓影汤晓影856872788.18.18.18.1概概概概 述述述述 假定在待排序的记录集中，存在假定在待排序的记录集中，存在多多个具有相同键值个具有相同键值的记录，若经过排序，这些记录的的记录，若经过排序，这些记录的相相对次序对次序仍然保持不变，即在原序列中，仍然保持不变，即在原序列中，ki=kj且且ri在在rj之之前，前，而在排序后的序列中，而在排序后的序列中，ri一定在一定在rj之前之前，则称这种，则称这种排序算法是排序算法是稳定的稳定的；否则称为；否则称为不稳定的不稳定的。学号学号姓名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明64920003汤

4、晓影汤晓影8586687278排序算法的稳定性：排序算法的稳定性：8.18.18.18.1概概概概 述述述述 1.1.排序的基本概念排序的基本概念排序的基本概念排序的基本概念 待排序序列中的记录已按关键码待排序序列中的记录已按关键码排好序排好序。待排序序列中记录的排列顺序与排好待排序序列中记录的排列顺序与排好序的顺序序的顺序正好相反正好相反。学号学号姓名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明64920003汤晓影汤晓影85866872788.18.18.18.1概概概概 述述述述 1.1.排序的基本概念排序的基本概念排序的基本概念排序的基本概念正序：正

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

6、序的基本概念排序的基本概念1.1.内排序：内排序：2.2.外排序：外排序：2.2.内排序算法内排序算法内排序算法内排序算法 1.插入排序插入排序 2.交换排序交换排序 3.选择排序选择排序 4.归并排序归并排序直接插入排序直接插入排序希尔排序希尔排序冒泡排序冒泡排序快速排序快速排序简单选择排序简单选择排序堆排序堆排序8.18.18.18.1概概概概 述述述述 排排序序基基本本过过程程:是是一一个个逐逐步步扩扩大大记记录录的的有有序序序序列列长长度度的过程的过程3.3.排序的基本过程排序的基本过程排序的基本过程排序的基本过程有序序列区无序序列区有序序列区无序序列区一趟排序一趟排序:将无序序列区里

7、一个或几个记录合并到有序序列的过程为一趟排序，有序序列长度增加1个或几个8.18.18.18.1概概概概 述述述述 4.4.排序算法的存储结构排序算法的存储结构排序算法的存储结构排序算法的存储结构从操作角度看，排序是从操作角度看，排序是线性结构线性结构的一种操作，待排序的一种操作，待排序记录可以用记录可以用顺序顺序存储结构或存储结构或链接链接存储结构存储。存储结构存储。假定假定2：将待排序的记录序列将待排序的记录序列排序为排序为升序升序序列。序列。rn+1 假定假定1 1：待排序记录：待排序记录采用采用顺序顺序存储结构，关键码为存储结构，关键码为整整型型，且记录只有关键码，且记录只有关键码一个

8、一个数据项。数据项。8.18.18.18.1概概概概 述述述述 10 15 24 6 12 35 40 980 1 2 3 4 5 6 7 8内排序算法内排序算法内排序算法内排序算法 1.插入排序插入排序 2.交换排序交换排序 3.选择排序选择排序 4.归并排序归并排序直接插入排序直接插入排序希尔排序希尔排序冒泡排序冒泡排序快速排序快速排序简单选择排序简单选择排序堆排序堆排序8.18.18.18.1概概概概 述述述述 8.28.28.28.2插入排序插入排序插入排序插入排序插入排序的主要操作是插入排序的主要操作是插入插入，其基本思想是：，其基本思想是：每次将一个每次将一个待排序的记录待排序的记

9、录按其关键码的大小插按其关键码的大小插入到一个已经排好序的入到一个已经排好序的有序序列有序序列中，中，直到直到全部全部记录排好序为止。记录排好序为止。举例:有序序列 2,待排序记录 3,6,11）直接插入排序）直接插入排序2）希尔排序）希尔排序基本思想基本思想：在插入第：在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1个记录已经排好序。个记录已经排好序。直接插入排序直接插入排序直接插入排序直接插入排序有序序列有序序列无序序列无序序列r r1r r2r ri-1r rir rnr ri+1r r1r r2r ri-1r rir rnr ri+1有序序列有序序列无序序列无序序列8.2

10、8.28.28.2插入排序插入排序插入排序插入排序直接插入排序过程示例直接插入排序过程示例直接插入排序过程示例直接插入排序过程示例 r 0 1 2 3 4 5 62121181825252222101025*25*2121第一趟18182222101025*25*252525252222212125252222212110102525*25252222212110102525*252522222121181810101818101025*25*第二趟1818第四趟18182525*第三趟第五趟算法稳定吗？2121算法思想？i从第2个数到第n个数 将第i个数插入到有序序列中的合理位置8.28.2

11、8.28.2插入排序插入排序插入排序插入排序共多少趟？对于对于riri，如何查找它的，如何查找它的插入位置插入位置?如何如何实现插入实现插入？直接插入排序直接插入排序直接插入排序直接插入排序需解决的关键问题需解决的关键问题?无序序列无序序列202025252121181826261)将ri暂存在r02)j=i-1；/从第i-1记录开始查找3)当rjr0时，循环做 rj后移一个位置,j-4)rj+1=r0 /将r0插入到位置j+12222 0 1 2 3 4 5 2121ij2525j2222j21218.28.28.28.2插入排序插入排序插入排序插入排序直接插入排序直接插入排序直接插入排序直

12、接插入排序无序序列无序序列202025251010181825252222 0 1 2 3 4 5 1010ij2525222220201010jr0的作用的作用?暂存单元暂存单元,监视哨监视哨 对于对于riri，如何查找它的，如何查找它的插入位置插入位置?如何如何实现插入实现插入？需解决的关键问题需解决的关键问题?1)将ri暂存在r02)j=i-1；/从第i-1记录开始查找3)当rjr0时，循环做 rj后移一个位置,j-4)rj+1=r0 /将r0插入到位置j+1jj8.28.28.28.2插入排序插入排序插入排序插入排序void insertSort(int r,int n)for(i=2

13、;i=n;i+)r0=ri;for(j=i-1;r0r0时，循环做：时，循环做：rj后移一个位置后移一个位置,j-1.4 rj+1=r08.28.28.28.2插入排序插入排序插入排序插入排序直接插入排序过程示例直接插入排序过程示例直接插入排序过程示例直接插入排序过程示例 r 0 1 2 3 4 5 62121181825252222101025*25*212121212525i=218182222101025*25*2525i=318182222101025*25*22222525222221211010252522222121101025252525*2525222221211010252

14、5*2525222221211818101018181818101025*25*i=41818i=618182525*i=5252521218.28.28.28.2插入排序插入排序插入排序插入排序直接插入排序练习直接插入排序练习直接插入排序练习直接插入排序练习 12 5 9 20 6 31 248.28.28.28.2插入排序插入排序插入排序插入排序直接插入排序练习直接插入排序练习直接插入排序练习直接插入排序练习 12 5 9 20 6 31 24初始序列 5 12 9 20 6 31 24第一趟 5 9 12 20 6 31 24第二趟 5 9 12 20 6 31 24第三趟 5 6 9

15、12 20 31 24第四趟第五趟 5 6 9 12 20 31 24第六趟 5 6 9 12 20 24 318.28.28.28.2插入排序插入排序插入排序插入排序1.基本操作基本操作。内排序在排序过程中的基本操作：。内排序在排序过程中的基本操作：比较比较：关键码之间的比较；：关键码之间的比较；移动移动：记录从一个位置移动到另一个位置。：记录从一个位置移动到另一个位置。2.辅助存储空间辅助存储空间。辅助存储空间是指在数据规模一定的条件下，除了存辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要放待排序记录占用的存储空间之外，执行算法所需要的其他存储

16、空间。的其他存储空间。3.算法本身的复杂程度算法本身的复杂程度。排序算法的性能排序算法的性能排序算法的性能排序算法的性能8.28.28.28.2插入排序插入排序插入排序插入排序直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析最好情况下：最好情况下：1 12 23 34 45 5时间复杂度为时间复杂度为O(n)。比较次数：比较次数：n-1移动次数：移动次数：2(n-1)1 12 23 34 45 52 21 12 23 34 45 53 31 12 23 34 45 54 41 12 23 34 45 55 5（正序）（正序）8.28.28.28.

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

18、度为时间复杂度为O(n)。8.28.28.28.2插入排序插入排序插入排序插入排序平均平均情况下（随机排列）：情况下（随机排列）：直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析时间复杂度为时间复杂度为O(n2)。比较次数：比较次数：移动次数：移动次数：4)1)(4(-+=nnn2=i4)1)(2(2-+=nnnii2（21+i）8.28.28.28.2插入排序插入排序插入排序插入排序空间性能：空间性能：需要一个记录的辅助空间。需要一个记录的辅助空间。直接插入排序算法是一种直接插入排序算法是一种稳定稳定的排序算法。的排序算法。直接插入排序算法性能

19、分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法简单、容易实现，适用于待排序直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。记录基本有序或待排序记录较小时。当待排序的记录个数较多时，大量的比较和移动操当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的作使直接插入排序算法的效率降低效率降低。8.28.28.28.2插入排序插入排序插入排序插入排序希尔排序希尔排序希尔排序希尔排序改进的着眼点：改进的着眼点：（1）由于直接插入排序算法简单，在待排序记录数）由于直接插入排序算法简单，在待排序记录数量量n较小较小时效

20、率也很高。时效率也很高。（2 2）若待排序记录按关键码）若待排序记录按关键码基本有序基本有序时，直接插入时，直接插入排序的效率可以大大提高；排序的效率可以大大提高；2 21 13 35 54 43 32 21 18.28.28.28.2插入排序插入排序插入排序插入排序（1）应如何分割待排序记录，才能保证整个序列逐步）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？向基本有序发展？（2）子序列内如何进行直接插入排序？）子序列内如何进行直接插入排序？需解决的关键问题需解决的关键问题?基本思想：基本思想：将整个待排序记录将整个待排序记录分割分割成若干个成若干个子序列子序列，在在子序列内子序

21、列内分别进行分别进行直接插入排序直接插入排序，待整个序列中的，待整个序列中的记录记录基本有序基本有序时，对时，对全体记录全体记录进行直接插入排序。进行直接插入排序。希尔排序希尔排序希尔排序希尔排序20 18 19,6 5 7,1 3 220 18 19 6 5 7 1 3 28.28.28.28.2插入排序插入排序插入排序插入排序希尔排序希尔排序希尔排序希尔排序子序列的构成不能是简单地子序列的构成不能是简单地“逐段分割逐段分割”，而是将，而是将相相距某个距某个“增量增量”的记录的记录组成一个子序列。组成一个子序列。逐渐逐渐缩短缩短“增量增量”，当缩短为，当缩短为1 1时就是对全体记录进时就是对

22、全体记录进行排序。行排序。10102 26 615159 91 18 820204 4111110102 26 615159 91 18 820204 41111d=3基本思想：基本思想：将整个待排序记录将整个待排序记录分割分割成若干个子序列，成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的在子序列内分别进行直接插入排序，待整个序列中的记录记录基本有序基本有序时，对全体记录进行直接插入排序。时，对全体记录进行直接插入排序。8.28.28.28.2插入排序插入排序插入排序插入排序希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例 1 2 3 4 5 6

23、 7 8 9404021212525494925*25*1616初始序列初始序列303008081313d=42121252525*25*30304949080840401616131325252 21 125*25*303008084949131316164040d=2131325252 21 1080825*25*16163030494940402525212125*25*303008081313161640404949d=1080825252121131325*25*16163030404049490808252513131616212125*25*404030304949每隔d-1个增

24、量记录分为一组每组内采用直接插入排序8.28.28.28.2插入排序插入排序插入排序插入排序算法稳定吗？解决方法：解决方法：将相隔某个将相隔某个“增量增量”的记录组成一个子序列。的记录组成一个子序列。增量应如何取？增量应如何取？希尔最早提出的方法是希尔最早提出的方法是d1=n/2，di+1=di/2。关键问题关键问题(1)(1)应如何分割待排序记录？应如何分割待排序记录？算法描述：算法描述：for(d=n/2;d=1;d=d/2)以以d为增量，进行组内直接插入排序；为增量，进行组内直接插入排序；8.28.28.28.2插入排序插入排序插入排序插入排序希尔插入排序过程示例希尔插入排序过程示例希尔

25、插入排序过程示例希尔插入排序过程示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始序列初始序列303008081313d=42121252525*25*30304949080840401616131325252 21 125*25*303008084949131316164040每隔d分为一组在整个序列中，前在整个序列中，前d个记录分别是个记录分别是d个子序列中的第一个记个子序列中的第一个记录，所以从第录，所以从第d+1个记录开始进行插入。个记录开始进行插入。for(i=d+1;ir0，循环做：rj后移一位j-r0插入到位置j+1将插入数据ri暂存

26、入r0j=i-d当rjr0且j0，循环做：ri后移d位 j=j-d;r0插入到位置j+d直接插入排序：希尔排序：8.28.28.28.2插入排序插入排序插入排序插入排序解决方法：解决方法：在插入记录在插入记录ri时，自时，自ri-d起往前跳跃式（跳跃幅起往前跳跃式（跳跃幅度为度为d）搜索待插入位置，并且搜索待插入位置，并且r0只是暂存单元，只是暂存单元，不是哨兵。当搜索位置不是哨兵。当搜索位置0，表示插入位置已找到。，表示插入位置已找到。在搜索过程中，记录后移也是跳跃在搜索过程中，记录后移也是跳跃d个位置。个位置。在整个序列中，前在整个序列中，前d个记录分别是个记录分别是d个子序列中的第个子序

27、列中的第一个记录，所以从第一个记录，所以从第d+1个记录开始进行插入。个记录开始进行插入。关键问题关键问题(2)子序列内如何进行直接插入排序？子序列内如何进行直接插入排序？8.28.28.28.2插入排序插入排序插入排序插入排序算法描述：算法描述：for(i=d+1;i0&r0=1;d=d/2)/以以d为增量为增量,组内直接插入排序组内直接插入排序 for(i=d+1;i0&r0rj)rj+d=rj;/记录后移记录后移d个位置个位置 j=j-d;/比较同一子序列的前一个记录比较同一子序列的前一个记录 rj+d=r0;希尔插入排序希尔插入排序8.28.28.28.2插入排序插入排序插入排序插入排

28、序希尔排序练习希尔排序练习希尔排序练习希尔排序练习 12 5 9 20 6 31 24初始序列第一趟结果d=3第二趟结果d=2第三趟结果d=112 5 9 20 6 31 246 5 9 20 12 31 245 6 9 12 20 24 31初始化：d=3，d=2 d=18.28.28.28.2插入排序插入排序插入排序插入排序希尔排序算法的时间性能希尔排序算法的时间性能希尔排序算法的时间性能是所取希尔排序算法的时间性能是所取增量增量的函数，而到目的函数，而到目前为止尚未有人求得一种最好的增量序列。前为止尚未有人求得一种最好的增量序列。研究表明，希尔排序的研究表明，希尔排序的时间性能时间性能在

29、在O(n2)和和O(nlog2n)之间。当之间。当n在某个特定范围内，希尔排序所需的比较在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为次数和记录的移动次数约为O(n1.3)。希尔排序希尔排序不稳定不稳定 希尔排序开始时希尔排序开始时增量较大增量较大，每个子序列中的，每个子序列中的记录个数记录个数较少较少，从而排序速度较快；当，从而排序速度较快；当增量较小增量较小时，虽然每个时，虽然每个子序列中子序列中记录个数较多记录个数较多，但整个序列已，但整个序列已基本有序基本有序，排，排序速度也较快。序速度也较快。8.28.28.28.2插入排序插入排序插入排序插入排序第八章第八章第八章第八

30、章 排序技术排序技术排序技术排序技术本章的基本内容是：本章的基本内容是：排序的基本概念排序的基本概念插入排序插入排序交换排序交换排序选择排序选择排序归并排序归并排序 交换排序的主要操作是交换排序的主要操作是交换交换，其主要思想是：，其主要思想是：在待排序列中选在待排序列中选两个两个记录，将它们的关键码相记录，将它们的关键码相比较，如果比较，如果反序反序（即排列顺序与排序后的次序（即排列顺序与排序后的次序正好相反），则正好相反），则交换交换它们的存储位置。它们的存储位置。8.38.38.38.3交换排序交换排序交换排序交换排序反序则反序则 交换交换rirj1）冒泡排序）冒泡排序2）快速排序）快速

31、排序起泡排序起泡排序起泡排序起泡排序基本思想：基本思想：两两比较两两比较相邻相邻记录的关键码，如果记录的关键码，如果反序反序则交换，直到没有反序的记录为止。则交换，直到没有反序的记录为止。rj rj+1 ri+1 rn-1 rn 无序区无序区 有序区有序区 1ji-1 已经位于最终位置已经位于最终位置反序则交换反序则交换8.38.38.38.3交换排序交换排序交换排序交换排序0505989812126969383853538181起泡排序过程示例起泡排序过程示例起泡排序过程示例起泡排序过程示例 05059898121269693838535381810505989812126969383853

32、5381810505989812126969383853538181总共n-1趟一共做多少趟？for(i=1;i=n-1;i+)for(j=1;jrj+1)rjrj+1;第i趟的比较范围：从1到（n-i）8.38.38.38.3交换排序交换排序交换排序交换排序1 2 3 4 5 6 70505989812126969383853538181起泡排序过程示例起泡排序过程示例起泡排序过程示例起泡排序过程示例 050598981212696938385353818105059898121269693838535381810505989812126969383853538181提问：一定需要做n-1趟

33、？如果在一趟排序过程中没有进行过交换操作,则排序结束。8.38.38.38.3交换排序交换排序交换排序交换排序解决方法：解决方法：在在每一趟起泡排序每一趟起泡排序之前，令之前，令exchange的的初值为初值为0。在在排序过程中，只要有记录交换，用排序过程中，只要有记录交换，用exchange记录交记录交换发生的位置换发生的位置。这样，在一趟排序结束后，只有。这样，在一趟排序结束后，只有当当exchange的值不为的值不为0才需要继续做下一趟冒泡排序。才需要继续做下一趟冒泡排序。关键问题关键问题1)1)：如何判别起泡排序的结束？如何判别起泡排序的结束？int exchange=n;while(

34、exchange)exchange=0;for(j=1;jrj+1)rjrj+1;exchange=j;for(i=1;i=n-1;i+)for(j=1;jrj+1)rjrj+1;8.38.38.38.3交换排序交换排序交换排序交换排序0505989812126969383853538181起泡排序过程示例起泡排序过程示例起泡排序过程示例起泡排序过程示例 050598981212696938385353818105059898121269693838535381810505989812126969383853538181提问：每趟排序只能使待排序范围减1吗？8.38.38.38.3交换排序交换

35、排序交换排序交换排序0505989812126969787881813030起泡排序过程示例起泡排序过程示例起泡排序过程示例起泡排序过程示例 05059898121230306969787881810505989812123030696978788181如果最后一次交换如果最后一次交换是是(位置位置j)(位置位置j+1)，位置位置j以后的所有记录以后的所有记录均已经有序，均已经有序，即下一趟的待排序范围缩短为即下一趟的待排序范围缩短为1到到jjj+18.38.38.38.3交换排序交换排序交换排序交换排序j关键问题关键问题 2 2）：如何确定）：如何确定每趟每趟起泡排序的范围？起泡排序的范围？

36、解决方法：解决方法：变量变量exchange记载的是这趟排序中记载的是这趟排序中最后一次交换的位最后一次交换的位置置，而，而下一趟的排序范围下一趟的排序范围是是1到到exchange。int exchange=n;while(exchange)bound=exchange;exchange=0;for(j=1;jrj+1)rjrj+1;exchange=j;int exchange=n;while(exchange)exchange=0;for(j=1;jrj+1)rjrj+1;exchange=j;8.38.38.38.3交换排序交换排序交换排序交换排序void BubbleSort(int

37、 r,int n)exchange=n;/初始的排序范围是所有记录初始的排序范围是所有记录 while(exchange)bound=exchange;exchange=0；for(j=1;jrj+1)rjrj+1；exchange=j；起泡排序算法起泡排序算法起泡排序算法起泡排序算法8.38.38.38.3交换排序交换排序交换排序交换排序起泡排序练习起泡排序练习起泡排序练习起泡排序练习 12 5 9 20 6 31 24初始序列第一趟结果第二趟结果第三趟结果第四趟结果5 9 12 6 20 24 315 9 6 12 20 24 31 5 6 9 12 20 24 315 6 9 12 20

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

39、 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)。稳定算法稳定算法8.38.38.38.3交换排序交换排序交换排序交换排序内排序算法内排序算法内排序算法内排序算法 1.插入排序插入排序 2.交换排序交换排序 3.选择排序选择排序 4.归并排序归并排序直接插

40、入排序直接插入排序希尔排序希尔排序冒泡排序冒泡排序快速排序快速排序简单选择排序简单选择排序堆排序堆排序8.18.18.18.1概概概概 述述述述 快速排序快速排序快速排序快速排序 首先选一个首先选一个轴值轴值（即（即比较的基准比较的基准），通过），通过一趟排序将待排序记录一趟排序将待排序记录分割分割成独立的成独立的两两部分，前一部部分，前一部分记录的关键码均分记录的关键码均小于或等于小于或等于轴值，后一部分记录的轴值，后一部分记录的关键码均关键码均大于或等于大于或等于轴值，然后分别对这轴值，然后分别对这两部分重复两部分重复上述方法上述方法，直到整个序列有序。，直到整个序列有序。举例举例:38

41、27 55 50 33 30 49 65 30 27 33 38 50 55 49 6527 30 33 38 49 50 55 6527 30 33 38 49 50 55 658.38.38.38.3交换排序交换排序交换排序交换排序算法思想：算法思想：快速排序的基本思想快速排序的基本思想快速排序的基本思想快速排序的基本思想如何选择轴值？如何选择轴值？如何实现如何实现分割分割（称一次划分）？（称一次划分）？如何处理分割得到的两个待排序子序列？如何处理分割得到的两个待排序子序列？如何判别快速排序的如何判别快速排序的结束结束？需解决的关键问题需解决的关键问题?举例:38 27 55 50 33

42、30 49 65 30 27 33 38 50 55 49 658.38.38.38.3交换排序交换排序交换排序交换排序选择轴值的方法：选择轴值的方法：1.使用使用第一个记录第一个记录的关键码；的关键码；2.选取序列选取序列中间记录中间记录的关键码；的关键码；3.比较序列中比较序列中第一个记录第一个记录、最后一个记录最后一个记录和和中间中间记录记录的关键码，取关键码的关键码，取关键码居中居中的作为轴值并调换的作为轴值并调换到第一个记录的位置；到第一个记录的位置；4.随机随机选取轴值。选取轴值。关键问题关键问题：如何选择轴值？如何选择轴值？选取不同轴值的后果：选取不同轴值的后果：决定两个子序列的

43、长度，期望子序列的长度最好相等。决定两个子序列的长度，期望子序列的长度最好相等。8.38.38.38.3交换排序交换排序交换排序交换排序举例:38 27 55 50 33 30 49 65 30 27 33 38 50 55 49 6527275050383849495555关键问题关键问题：如何实现一次划分？如何实现一次划分？每个数和轴值做比较，比轴值大的数放后面，比轴值小的每个数和轴值做比较，比轴值大的数放后面，比轴值小的数放前面。数放前面。关键在于数和轴值交换，从前、后两端开始，逐渐向中间关键在于数和轴值交换，从前、后两端开始，逐渐向中间轴值逼近的过程。轴值逼近的过程。8.38.38.3

44、8.3交换排序交换排序交换排序交换排序3333272750503838494955553333关键问题关键问题：如何实现一次划分？如何实现一次划分？8.38.38.38.3交换排序交换排序交换排序交换排序1）当轴值在前面时，从后往前扫描，后面数逐个和轴值比较，第一个比轴值）当轴值在前面时，从后往前扫描，后面数逐个和轴值比较，第一个比轴值小的数和轴值换，小的数放在轴值的前面，轴值就位于待排序区域的后面小的数和轴值换，小的数放在轴值的前面，轴值就位于待排序区域的后面2）当轴值在后面时，从前往后扫描，前面数逐个和轴值比较，第一个比轴值）当轴值在后面时，从前往后扫描，前面数逐个和轴值比较，第一个比轴值

45、大的数和轴值换，大的数放在轴值的后面，轴值就位于待排序区域的前面大的数和轴值换，大的数放在轴值的后面，轴值就位于待排序区域的前面3）当扫描到轴值，轴值就完成了一次划分）当扫描到轴值，轴值就完成了一次划分272750503838494955553333272750503838494955553333每个数和轴值做比较，比轴值大的数放后面，比轴值小的数放前面。每个数和轴值做比较，比轴值大的数放后面，比轴值小的数放前面。关键在于数和轴值交换，从前后两端开始，逐渐向中间轴值逼近的过程。关键在于数和轴值交换，从前后两端开始，逐渐向中间轴值逼近的过程。272750503838494955553333完成一

46、次划分O(n)3030656527275050383849495555ji38385555关键问题关键问题：如何实现一次划分？如何实现一次划分？jjiiijiji=0,j=n-11)j从后往前从后往前扫扫描描,找比轴值找比轴值小小的第一个数的第一个数,和和轴值交换轴值交换2)i从前往后从前往后扫扫描描,找比轴值找比轴值大大的第一个数的第一个数,和和轴值交换轴值交换8.38.38.38.3交换排序交换排序交换排序交换排序333330303838656527275050494955553333303065652727505049493333关键问题关键问题：如何实现一次划分？如何实现一次划分？i=

47、0,j=n-11)j从后往前从后往前扫描扫描,找比轴值找比轴值小小的第的第一个数一个数,和轴值交和轴值交换换2)i从前往后从前往后扫描扫描,找比轴值找比轴值大大的第的第一个数一个数,和轴值交和轴值交换换直到直到i=j结束，完结束，完成一次划分，即成一次划分，即轴值的位置轴值的位置8.38.38.38.3交换排序交换排序交换排序交换排序38385555ij303065652727505049493333j38383333303065652727505049495555iji38385050303027273333656549495555ijj解决方法：解决方法：设待划分的序列是设待划分的序列是r

48、s rt，设参数设参数i，j分别指向子分别指向子序列左、右两端的下标序列左、右两端的下标s和和t，令令rs为轴值，为轴值，（1）j从后从后向前向前扫描，直到扫描，直到rjri，将将rj移动到移动到ri的位置的位置(rj与与ri交换交换)，使关键码小（同轴值相比），使关键码小（同轴值相比）的记录移动到前面去；的记录移动到前面去；（2）i从前从前向后向后扫描，直到扫描，直到rirj，将将ri移动到移动到rj的位置的位置(ri与与rj交换交换)，使关键码大（同轴值比较），使关键码大（同轴值比较）的记录移动到后面去；的记录移动到后面去；（3）重复上述过程，直到）重复上述过程，直到i=j。关键问题关键问

49、题：如何实现一次划分？如何实现一次划分？8.38.38.38.3交换排序交换排序交换排序交换排序关键问题关键问题：如何实现一次划分？如何实现一次划分？算法描述：算法描述：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-;/将较大记录交换到后面将较大记录交换到后面 return i;/i为轴值的最终位

50、置为轴值的最终位置1)j从后往前从后往前扫描扫描,找比轴值找比轴值小小的的第一个数第一个数,和轴值交换和轴值交换2)i从前往后从前往后扫描扫描,找比轴值找比轴值大大的的第一个数第一个数,和轴值交换和轴值交换直到直到i=j结束，完成一次划分，结束，完成一次划分，即轴值的位置即轴值的位置 38 27 55 13 49 13 27 55 38 498.38.38.38.3交换排序交换排序交换排序交换排序解决方法：解决方法：对分割得到的对分割得到的两个子序列两个子序列递归地递归地执行快速执行快速排序。排序。关键问题关键问题：如何处理分割得到的两个待排序子序列？：如何处理分割得到的两个待排序子序列？30