数据结构及算法排序ppt课件.ppt

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

2、2, , kn，排序是将这些记录排列成顺排序是将这些记录排列成顺序为序为rs1, rs2, , rsn的一个序列，使得相应的的一个序列，使得相应的关键码关键码满满足足非递减关系非递减关系ks1ks2ksn（称为称为升序升序）或非递增关系）或非递增关系ks1ks2ksn（称为称为降序降序）。）。1.排序的基本概念排序的基本概念学号学号姓名姓名高数高数英语英语0002李李 明明640001王王 军军850003汤晓影汤晓影85726878学号学号姓名姓名高数高数英语英语0001王王 军军850002李李 明明640003汤晓影汤晓影856872788.18.1概概 述述 假定在待排序的记录集中，存

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

4、的基本概念排序的基本概念 待排序序列中的记录已按关键码待排序序列中的记录已按关键码排好序排好序。 待排序序列中记录的排列顺序与排好待排序序列中记录的排列顺序与排好序的顺序序的顺序正好相反正好相反。学号学号姓名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明64920003汤晓影汤晓影85866872788.18.1概概 述述 1.排序的基本概念排序的基本概念正序：正序：逆序（反序）：逆序（反序）：排序的分类排序的分类 在排序的整个过程中，待排序的所有记录在排序的整个过程中，待排序的所有记录全部被放置在内存中全部被放置在内存中,不需要访问外存不需要访问外存 由于待

5、排序的记录个数太多，由于待排序的记录个数太多，不能同时放不能同时放置在内存置在内存，而需要将一部分记录放置在内存，另一部，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在分记录放置在外存上，整个排序过程需要在内外存之内外存之间多次交换数据间多次交换数据才能得到排序的结果。才能得到排序的结果。8.18.1概概 述述 1.排序的基本概念排序的基本概念1.1.内排序：内排序：2.2.外排序：外排序：2.内排序算法内排序算法 1. 插入排序插入排序 2. 交换排序交换排序 3. 选择排序选择排序 4. 归并排序归并排序直接插入排序直接插入排序希尔排序希尔排序冒泡排序冒泡排序快

6、速排序快速排序简单选择排序简单选择排序堆排序堆排序8.18.1概概 述述 排序基本过程排序基本过程: :是一个逐步扩大记录的有序序列长度是一个逐步扩大记录的有序序列长度的过程的过程3.排序的基本过程排序的基本过程有序序列区无序序列区有序序列区无序序列区一趟排序一趟排序:将无序序列区里一个或几个记录合并到有序序列的过程为一趟排序，有序序列长度增加1个或几个8.18.1概概 述述 4.排序算法的存储结构排序算法的存储结构从操作角度看，排序是从操作角度看，排序是线性结构线性结构的一种操作，待排序的一种操作，待排序记录可以用记录可以用顺序顺序存储结构或存储结构或链接链接存储结构存储。存储结构存储。假定

7、假定2：将待排序的记录序列将待排序的记录序列排序为排序为升序升序序列。序列。 rn+1 假定假定1 1：待排序记录：待排序记录采用采用顺序顺序存储结构，关键码为存储结构，关键码为整整型型，且记录只有关键码，且记录只有关键码一个一个数据项。数据项。8.18.1概概 述述 10 15 24 6 12 35 40 980 1 2 3 4 5 6 7 8内排序算法内排序算法 1. 插入排序插入排序 2. 交换排序交换排序 3. 选择排序选择排序 4. 归并排序归并排序直接插入排序直接插入排序希尔排序希尔排序冒泡排序冒泡排序快速排序快速排序简单选择排序简单选择排序堆排序堆排序8.18.1概概 述述 8.

8、28.2插入排序插入排序插入排序的主要操作是插入排序的主要操作是插入插入，其基本思想是：，其基本思想是：每次将一个每次将一个待排序的记录待排序的记录按其关键码的大小插按其关键码的大小插入到一个已经排好序的入到一个已经排好序的有序序列有序序列中，中，直到直到全部全部记录排好序为止。记录排好序为止。举例: 有序序列 2 , 待排序记录 3,6,11）直接插入排序）直接插入排序2）希尔排序）希尔排序基本思想基本思想：在插入第：在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1个记录已经排好序。个记录已经排好序。 8.2.1直接插入排序直接插入排序有序序列有序序列无序序列无序序列12i-1

9、ini+112i-1ini+1有序序列有序序列无序序列无序序列8.28.2插入排序插入排序r 0 1 2 3 4 5 6第一趟第二趟第四趟第三趟第五趟算法稳定吗？算法思想？i从第2个数到第n个数 将第i个数插入到有序序列中的合理位置8.28.2插入排序插入排序共多少趟？ 对于对于riri，如何查找它的，如何查找它的插入位置插入位置?如何如何实现插入实现插入？直接插入排序直接插入排序需解决的关键问题需解决的关键问题?无序序列无序序列1)将ri暂存在r02) j=i-1；/从第i-1记录开始查找3)当rjr0时，循环做 rj后移一个位置,j-4)rj+1=r0 /将r0插入到位置j+1 0 1 2

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

11、or(j=i-1; r0r0时，循环做：时，循环做： rj后移一个位置后移一个位置,j- 1.4 rj+1=r08.28.2插入排序插入排序r 0 1 2 3 4 5 6i = 2i = 3i = 4i = 6i = 58.28.2插入排序插入排序12 5 9 20 6 31 248.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 12 20 31 24第四趟第五趟 5 6 9 12 20 31 24第六趟 5 6 9 12 20 24

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

13、排序算法性能分析直接插入排序算法性能分析最好情况下：最好情况下： 时间复杂度为时间复杂度为O(n)。比较次数：比较次数：n-1移动次数：移动次数：2(n-1) （正序）（正序）8.28.2插入排序插入排序直接插入排序算法性能分析直接插入排序算法性能分析最好最好情况下（正序）：情况下（正序）： 比较次数：比较次数：n-1移动次数：移动次数：2(n-1) 最坏最坏情况下（逆序）：情况下（逆序）： 时间复杂度为时间复杂度为O(n2)。比较次数：比较次数：移动次数：移动次数：2) 1)(2(2- -+ += = = =nnini2) 1)(4(1- -+ += =+ + nnin2= =i）（时间复杂

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

15、现，适用于待排直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。序记录基本有序或待排序记录较小时。当待排序的记录个数较多时，大量的比较和移动当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的操作使直接插入排序算法的效率降低效率降低。8.28.2插入排序插入排序8.2.2希尔排序希尔排序改进的着眼点：改进的着眼点：（1）由于直接插入排序算法简单，在待排序记录数）由于直接插入排序算法简单，在待排序记录数量量n较小较小时效率也很高。时效率也很高。 （2 2）若待排序记录按关键码）若待排序记录按关键码基本有序基本有序时，直接插入时，直接插入排序的效率可以大大提

16、高；排序的效率可以大大提高；8.28.2插入排序插入排序（1）应如何分割待排序记录，才能保证整个序列逐步）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？向基本有序发展？（2）子序列内如何进行直接插入排序？）子序列内如何进行直接插入排序？需解决的关键问题需解决的关键问题?基本思想：基本思想：将整个待排序记录将整个待排序记录分割分割成若干个成若干个子序列子序列，在在子序列内子序列内分别进行分别进行直接插入排序直接插入排序，待整个序列中的，待整个序列中的记录记录基本有序基本有序时，对时，对全体记录全体记录进行直接插入排序。进行直接插入排序。8.2.2希尔排序希尔排序20 18 19 ,6

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

18、全体记录进行直接插入排序。时，对全体记录进行直接插入排序。8.28.2插入排序插入排序希尔插入排序过程示例希尔插入排序过程示例 1 2 3 4 5 6 7 8 9初始序列初始序列d = 4d = 2d = 1每隔d-1个增量记录分为一组每组内采用直接插入排序8.28.2插入排序插入排序算法稳定吗？解决方法：解决方法：将相隔某个将相隔某个“增量增量”的记录组成一个子序列。的记录组成一个子序列。增量应如何取？增量应如何取？希尔最早提出的方法是希尔最早提出的方法是d1=n/2，di+1=di/2。关键问题关键问题(1)(1)应如何分割待排序记录？应如何分割待排序记录？算法描述：算法描述：for (d

19、=n/2; d=1; d=d/2) 以以d为增量，进行组内直接插入排序；为增量，进行组内直接插入排序；8.28.2插入排序插入排序希尔插入排序过程示例希尔插入排序过程示例 1 2 3 4 5 6 7 8 9初始序列初始序列d = 4每隔d分为一组在整个序列中，前在整个序列中，前d个记录分别是个记录分别是d个子序列中的第一个记个子序列中的第一个记录，所以从第录，所以从第d+1个记录开始进行插入。个记录开始进行插入。for(i=d+1;ir0，循环做： rj后移一位j-r0插入到位置j+1将插入数据ri暂存入r0j=i-d当rjr0且j0，循环做： ri后移d位 j=j-d;r0插入到位置j+d直

20、接插入排序：希尔排序：8.28.2插入排序插入排序解决方法：解决方法：在插入记录在插入记录ri时，自时，自ri-d起往前跳跃式（跳跃幅起往前跳跃式（跳跃幅度为度为d）搜索待插入位置，并且搜索待插入位置，并且r0只是暂存单元，只是暂存单元，不是哨兵。当搜索位置不是哨兵。当搜索位置0，表示插入位置已找到。，表示插入位置已找到。在搜索过程中，记录后移也是跳跃在搜索过程中，记录后移也是跳跃d个位置。个位置。在整个序列中，前在整个序列中，前d个记录分别是个记录分别是d个子序列中的个子序列中的第一个记录，所以从第第一个记录，所以从第d+1个记录开始进行插入。个记录开始进行插入。关键问题关键问题( (2)

21、)子序列内如何进行直接插入排序？子序列内如何进行直接插入排序？8.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.2插入排序插入排序12 5 9 20 6 31 24初始序列第一趟结果d=3第二趟结果d=2第三趟结果d=112 5 9 20 6 31 246 5 9 2

22、0 12 31 245 6 9 12 20 24 31初始化：d=3， d=2 d=18.28.2插入排序插入排序希尔排序算法的时间性能希尔排序算法的时间性能希尔排序算法的时间性能是所取希尔排序算法的时间性能是所取增量增量的函数，而到目的函数，而到目前为止尚未有人求得一种最好的增量序列。前为止尚未有人求得一种最好的增量序列。研究表明，希尔排序的研究表明，希尔排序的时间性能时间性能在在O(n2)和和O(nlog2n)之间。当之间。当n在某个特定范围内，希尔排序所需的比较在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为次数和记录的移动次数约为O(n1.3 ) 。希尔排序希尔排序不稳定不

23、稳定 希尔排序开始时希尔排序开始时增量较大增量较大，每个子序列中的，每个子序列中的记录个数记录个数较少较少，从而排序速度较快；当，从而排序速度较快；当增量较小增量较小时，虽然每个时，虽然每个子序列中子序列中记录个数较多记录个数较多，但整个序列已，但整个序列已基本有序基本有序，排，排序速度也较快。序速度也较快。 8.28.2插入排序插入排序第八章第八章 排序技术排序技术本章的基本内容是：本章的基本内容是：排序的基本概念排序的基本概念插入排序插入排序交换排序交换排序选择排序选择排序归并排序归并排序 交换排序的主要操作是交换排序的主要操作是交换交换，其主要思想是：，其主要思想是：在待排序列中选在待排

24、序列中选两个两个记录，将它们的关键码相记录，将它们的关键码相比较，如果比较，如果反序反序（即排列顺序与排序后的次序（即排列顺序与排序后的次序正好相反），则正好相反），则交换交换它们的存储位置。它们的存储位置。 8.38.3交换排序交换排序反序则反序则 交换交换1）冒泡排序）冒泡排序2）快速排序）快速排序8.3.18.3.1起泡排序起泡排序基本思想：基本思想：两两比较两两比较相邻相邻记录的关键码，如果记录的关键码，如果反反序序则交换，直到没有反序的记录为止。则交换，直到没有反序的记录为止。 rj rj+1 ri+1 rn- -1 rn 无序区无序区 有序区有序区 1ji- -1 已经位于最终位置

25、已经位于最终位置反序则交换反序则交换8.38.3交换排序交换排序起泡排序过程示例起泡排序过程示例 总共n-1趟一共做多少趟？for(i=1;i=n-1;i+) for(j=1;jrj+1) rjrj+1; 第i趟的比较范围：从1到（n-i）8.38.3交换排序交换排序1 2 3 4 5 6 7起泡排序过程示例起泡排序过程示例 提问：一定需要做n-1趟？如果在一趟排序过程中没有进行过交换操作,则排序结束。8.38.3交换排序交换排序解决方法：解决方法：在在每一趟起泡排序每一趟起泡排序之前，令之前，令exchange的的初值为初值为0。在在排序过程中，只要有记录交换，用排序过程中，只要有记录交换，

26、用exchange记录交记录交换发生的位置换发生的位置。这样，在一趟排序结束后，只有。这样，在一趟排序结束后，只有当当exchange的值不为的值不为0才需要继续做下一趟冒泡排序。才需要继续做下一趟冒泡排序。关键问题关键问题1)1)：如何判别起泡排序的结束？如何判别起泡排序的结束？int exchange=n;while( (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.3交换排序交换排序起泡排序过程示例起泡排序过程示例 提问：每趟排

27、序只能使待排序范围减1吗？8.38.3交换排序交换排序起泡排序过程示例起泡排序过程示例 如果最后一次交换如果最后一次交换是是(位置位置j)(位置位置j+1)，位置位置j以后的所有记录以后的所有记录均已经有序，均已经有序，即下一趟的待排序范围缩短为即下一趟的待排序范围缩短为1到到jjj+18.38.3交换排序交换排序j关键问题关键问题 2 2）：如何确定）：如何确定每趟每趟起泡排序的范围？起泡排序的范围？解决方法：解决方法： 变量变量exchange记载的是这趟排序中记载的是这趟排序中最后一次交换的位最后一次交换的位置置，而，而下一趟的排序范围下一趟的排序范围是是1到到exchange。int

28、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.3交换排序交换排序void BubbleSort( (int r , int n) ) exchange=n; /初始的排序范围是所有记录初始的排序范围是所有记录 while ( (exchange) ) bound=exchange; exc

29、hange=0； for ( (j=1; jrj+1) ) rjrj+1； exchange=j； 起泡排序算法起泡排序算法8.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 24 318.38.3交换排序交换排序起泡排序的时间性能分析起泡排序的时间性能分析最好情况：最好情况：比较次数：比较次数：n-1移动次数：移动次数：0 时间复杂度为时间复杂度为O(n)。8.38.3交换排序交换排序（正序）（正序）最坏情况

30、（反序）：最坏情况（反序）：起泡排序的时间性能分析起泡排序的时间性能分析最好情况（正序）：最好情况（正序）：比较次数：比较次数：n-1移动次数：移动次数：0 时间复杂度为时间复杂度为O(n)；时间复杂度为时间复杂度为O(n2)。比较次数：比较次数：移动次数：移动次数：2) 1(1- -= = = =nn(n-i)n-1i2) 1(1- -= = = =n3n3(n-i)n-1i平均情况：平均情况：时间复杂度为时间复杂度为O(n2)。稳定算法稳定算法8.38.3交换排序交换排序内排序算法内排序算法 1. 插入排序插入排序 2. 交换排序交换排序 3. 选择排序选择排序 4. 归并排序归并排序直接

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

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

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

34、38 27 55 50 33 30 49 65 30 27 33 38 50 55 49 65关键问题：关键问题：如何实现一次划分？如何实现一次划分？每个数和轴值做比较，比轴值大的数放后面，比轴值小的每个数和轴值做比较，比轴值大的数放后面，比轴值小的数放数放前面。前面。关键关键在于数和轴值在于数和轴值交换，从前、后两端开始，逐渐向中间交换，从前、后两端开始，逐渐向中间轴值逼近的过程。轴值逼近的过程。8.38.3交换排序交换排序关键问题：关键问题：如何实现一次划分？如何实现一次划分？8.38.3交换排序交换排序1）当）当轴值在前面时，从后往前扫描轴值在前面时，从后往前扫描，后面，后面数逐个和轴值

35、比较数逐个和轴值比较，第一个比，第一个比轴值轴值小的数和轴值换，小的数放在轴值的前面，轴值就位于待排序区域的后面小的数和轴值换，小的数放在轴值的前面，轴值就位于待排序区域的后面2）当）当轴值在后面时，从前往后扫描轴值在后面时，从前往后扫描，前面数逐个和轴值比较，第一个比，前面数逐个和轴值比较，第一个比轴值轴值大的数和轴值换，大的数放在轴值的后面，轴值就位于待排序区域的前面大的数和轴值换，大的数放在轴值的后面，轴值就位于待排序区域的前面3）当扫描到轴值，轴）当扫描到轴值，轴值就完成了一次划分值就完成了一次划分每个数和轴值做比较，比轴值大的数放后面，比轴值小的数放前面每个数和轴值做比较，比轴值大的

36、数放后面，比轴值小的数放前面。关键关键在于数和轴值交换，从前后两端开始，逐渐向中间轴值逼近的过程。在于数和轴值交换，从前后两端开始，逐渐向中间轴值逼近的过程。完成一次划分O(n)ji关键问题：关键问题：如何实现一次划分？如何实现一次划分？jjiiijiji=0,j=n-11) j从后往前从后往前扫扫描描,找比轴值找比轴值小小的第一个数的第一个数,和和轴值交换轴值交换2) i从前往后从前往后扫扫描描,找比轴值找比轴值大大的第一个数的第一个数,和和轴值交换轴值交换8.38.3交换排序交换排序关键问题：关键问题：如何实现一次划分？如何实现一次划分？i=0,j=n-11) j从后往前从后往前扫描扫描,

37、找比轴值找比轴值小小的第的第一个数一个数,和轴值交和轴值交换换2) i从前往后从前往后扫描扫描,找比轴值找比轴值大大的第的第一个数一个数,和轴值交和轴值交换换直到直到i=j结束，完结束，完成一次划分，即成一次划分，即轴值的位置轴值的位置8.38.3交换排序交换排序ijjijiijj解决方法：解决方法：设待划分的序列是设待划分的序列是rs rt，设参数设参数i，j分别指向子分别指向子序列左、右两端的下标序列左、右两端的下标s和和t，令令rs为轴值，为轴值，（1）j从后从后向前向前扫描，直到扫描，直到rjri，将将rj移动到移动到ri的位置的位置(rj与与ri交换交换)，使关键码小（同轴值相比），

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

39、/初始化初始化 while (ij) while (ij & ri= rj) j-； /右侧扫描右侧扫描 if (ij) rirj; i+; /将较小记录交换到前面将较小记录交换到前面 while (ij & ri= rj) i+； /左侧扫描左侧扫描 if (ij) rjri; j-; /将较大记录交换到后面将较大记录交换到后面 return i; /i为轴值的最终位置为轴值的最终位置1)j从后往前从后往前扫描扫描,找比轴值找比轴值小小的的第一个数第一个数,和轴值交换和轴值交换2)i从前往后从前往后扫描扫描,找比轴值找比轴值大大的的第一个数第一个数,和轴值交换和轴值交换直到直到i=j结束，完

40、成一次划分，结束，完成一次划分，即轴值的位置即轴值的位置 38 27 55 13 49 13 27 55 38 498.38.3交换排序交换排序解决方法：解决方法：对分割得到的对分割得到的两个子序列两个子序列递归地递归地执行快速执行快速排序。排序。关键问题：如何处理分割得到的两个待排序子序列？关键问题：如何处理分割得到的两个待排序子序列？ ijij8.38.3交换排序交换排序解决方法：解决方法：若待排序列中若待排序列中只有一个记录只有一个记录，显然已有序，否则进，显然已有序，否则进行一次划分后，再分别对分割所得的两个子序列进行一次划分后，再分别对分割所得的两个子序列进行快速排序（即递归处理）。

41、行快速排序（即递归处理）。 关键问题：关键问题：如何判别快速排序的结束？如何判别快速排序的结束？ ij8.38.3交换排序交换排序快速排序的过程快速排序的过程 第一趟第二趟第三趟8.38.3交换排序交换排序void QuickSort (int r , int first, int end )/在序列在序列 firstend中递归地进行快速排序中递归地进行快速排序 if (first end) pivotpos = Partition (r, first, end ); QuickSort (r, first, pivotpos-1); QuickSort (r, pivotpos+1, en

42、d ); 算法描述：算法描述：关键问题：关键问题：如何判别快速排序的结束？如何判别快速排序的结束？ 38 27 55 13 49 13 27 38 55 49pivotpos8.38.3交换排序交换排序12 5 9 20 6 31 24初始序列第一趟结果第二趟结果第三趟结果6 5 9 12 20 31 245 6 9 12 20 31 245 6 9 12 20 24 318.38.3交换排序交换排序i=0,j=n-11)j从后往前从后往前扫描扫描,找比轴值找比轴值小小的第一个数的第一个数,和轴值交换和轴值交换2)i从前往后从前往后扫描扫描,找比轴值找比轴值大大的第一个数的第一个数,和轴值交换

43、和轴值交换直到直到i=j结束，完成一次划分，即结束，完成一次划分，即轴值的轴值的位置位置8.38.3交换排序交换排序思考思考:1 2 3 4 5第一趟：第一趟： 2 3 4 52 3 4 5第二趟：第二趟： 2 2 3 3 4 4 5 5第三趟：第三趟： 2 2 3 4 53 4 5第四趟：第四趟： 2 2 3 3 4 4 5 5快速排序的时间性能分析快速排序的时间性能分析例：例：38, 6,27, 55, 50, 13, 49的快速排序递归树如下：的快速排序递归树如下：3813505549627快速排序的递归执行过程可以用递归树描述。快速排序的递归执行过程可以用递归树描述。快速排序的时间性能

44、分析快速排序的时间性能分析8.38.3交换排序交换排序第一趟结果13 6 27 38 50 55 49 第二趟结果 6 13 27 38 49 50 55最好情况：最好情况：每一次划分对一个每一次划分对一个记录定位记录定位后，该记录的左侧子表与后，该记录的左侧子表与右侧子表的长度相同，为右侧子表的长度相同，为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)8.38.3交换排序交换排序最坏情况：最坏情况：每次划分只得到

45、一个比上一次划分每次划分只得到一个比上一次划分少一个记录少一个记录的子序的子序列（另一个子序列为空），为列（另一个子序列为空），为 O(n2)。最好情况：最好情况：每一次划分对一个记录定位后，该记录的左侧子表与每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为右侧子表的长度相同，为O(nlog2n)。快速排序的时间性能分析快速排序的时间性能分析平均情况：平均情况：为为O(nlog2n)。)() 1(21211nOnninni= =- -= =- - - -= =）（不稳定算法1,2,3,4,58.38.3交换排序交换排序5,7,3,2,2*内排序算法内排序算法 1. 插入排序

46、插入排序 2. 交换排序交换排序 3. 选择排序选择排序 4. 归并排序归并排序直接插入排序直接插入排序希尔排序希尔排序冒泡排序冒泡排序快速排序快速排序简单选择排序简单选择排序堆排序堆排序8.18.1概概 述述 选择排序的主要操作是选择排序的主要操作是选择选择，其主要思想是：，其主要思想是：每趟排序在每趟排序在当前待排序序列当前待排序序列中选出关键码中选出关键码最小最小的记录，添加到有序序列中。的记录，添加到有序序列中。 8.48.4选择排序选择排序有序序列有序序列12i-1ink无序序列无序序列ni+112i-1ii交换交换最小记录最小记录8.4.18.4.1简单选择排序简单选择排序基本思想

47、：基本思想：第第i 趟在趟在n- -i+1（i=1,2, ,n- -1）个记录中选个记录中选取取关键码最小关键码最小的记录作为有序序列中的的记录作为有序序列中的第第i个记录个记录。 举例：举例：21 25 49 28 16 08 08 25 49 28 16 218.48.4选择排序选择排序简单选择排序示例简单选择排序示例8.48.4选择排序选择排序简单选择排序示例简单选择排序示例for ( i=1; in; i+) /从第从第i个数到第个数到第n个数中，选出最小的数和第个数中，选出最小的数和第i个数换个数换总共执行多少总共执行多少趟？趟？每趟做什么？每趟做什么？8.48.4选择排序选择排序设

48、置一个整型变量设置一个整型变量index， Index初始为初始为i。rindex逐逐一和后面的数比较，记录在一趟比较过程中关键码一和后面的数比较，记录在一趟比较过程中关键码最最小的记录的下标。小的记录的下标。 关键问题：关键问题：如何在无序区（第如何在无序区（第i个数个数-第第n个数）中选个数）中选出关键码最小的记录？出关键码最小的记录？indexindex indexindex=i; for ( (j=i+1; j=n; j+) ) if ( (rjrindex) ) index=j;j8.48.4选择排序选择排序解决方法：解决方法：第第i趟简单选择排序的待排序区间是趟简单选择排序的待排序

49、区间是ri rn，则则ri是无序是无序区第一个记录，所以，将区第一个记录，所以，将index所记载的关键所记载的关键码码最小的记录与最小的记录与ri交换交换。关键问题：选出无序区（第关键问题：选出无序区（第i i个数个数- -第第n n个数）中关键个数）中关键码最小的记录后，和第码最小的记录后，和第i i个数交换个数交换算法描述：算法描述： if ( (index!=i) ) ririndex; 8.48.4选择排序选择排序void selectSort ( int r , int n) for ( i=1; in; i+) index=i; for (j=i+1; j=n; j+) if (

50、rjrindex) index=j; if (index!=i) ririndex; 简单选择排序算法简单选择排序算法8.48.4选择排序选择排序12 5 9 20 6 31 24初始序列第一趟结果第二趟结果第三趟结果5 12 9 20 6 31 24 5 6 9 20 12 31 24 5 6 9 20 12 31 24第四趟结果 5 6 9 12 20 31 24第五趟结果 5 6 9 12 20 31 24第六趟结果 5 6 9 12 20 24 31 8.48.4选择排序选择排序简单选择排序算法的性能分析简单选择排序算法的性能分析移动次数：移动次数：最好情况（正序）：最好情况（正序）：