第8章排序(1)

1、第八章第八章 排序技术排序技术本章的基本内容是：本章的基本内容是：排序的基本概念排序的基本概念插入排序插入排序 交换排序交换排序 选择排序选择排序归并排序归并排序 概概 述述 排序：排序：给定一组给定一组记录记录的集合的集合 r r1 1, , r r2 2, , , , r rn n ，其其相应的关键码分别为相应的关键码分别为 k k1 1, , k k2 2, , , , k kn n ，排序是将排序是将这些记录排列成顺序为这些记录排列成顺序为 r rs s1 1, , r rs s2 2, , , , r rsnsn 的一个的一个序列，使得相应的关键码满足序列，使得相应的关键码满足k k

2、s s1 1k ks s2 2k ksnsn（称为升序）或称为升序）或k ks s1 1k ks s2 2k ksnsn（称为降序）。称为降序）。正序：正序：待排序序列中的记录已按关键码排好序。待排序序列中的记录已按关键码排好序。逆序（反序）：逆序（反序）：待排序序列中记录的排列顺序与排好待排序序列中记录的排列顺序与排好序的顺序正好相反。序的顺序正好相反。排序的基本概念排序的基本概念排序算法的稳定性：排序算法的稳定性：假定在待排序的记录集中，存在假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的多个具有相同键值的记录，若经过排序，这些记录的相对次序相对次序仍然保持不变，

3、即在原序列中，仍然保持不变，即在原序列中，k ki i= =k kj j且且r ri i在在r rj j之前，而在排序后的序列中，之前，而在排序后的序列中，r ri i仍在仍在r rj j之前，则称这之前，则称这种排序算法是稳定的；否则称为不稳定的。种排序算法是稳定的；否则称为不稳定的。 概概 述述 排序的基本概念排序的基本概念学号学号姓名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明64920003汤晓影汤晓影8586687278概概 述述 排序的基本概念排序的基本概念单键排序：单键排序：根据一个关键码进行的排序；根据一个关键码进行的排序；多键排序：多键排序

4、：根据多个关键码进行的排序。根据多个关键码进行的排序。学号学号姓名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明64920003汤晓影汤晓影8586687278按学号排序按学号排序单键排序单键排序按成绩（高数英语思想品德）排序按成绩（高数英语思想品德）排序多键排序多键排序概概 述述 排序的基本概念排序的基本概念设关键码分别为设关键码分别为k k1 1, , k k2 2, , , , k km m，多键排序多键排序有两种方法有两种方法 依次对记录进行依次对记录进行m m次排序，第一次按次排序，第一次按k k1 1排序，第二次排序，第二次按按k k2 2排序，依

5、此类推。这种方法要求各趟排序所用的算排序，依此类推。这种方法要求各趟排序所用的算法是稳定的；法是稳定的； 将关键码将关键码k k1 1, , k k2 2, , , , k km m分别视为字符串依次首尾连分别视为字符串依次首尾连接在一起，形成一个新的字符串，然后，对记录序列按接在一起，形成一个新的字符串，然后，对记录序列按新形成的字符串排序。新形成的字符串排序。多键排序多键排序单键排序单键排序排序的分类排序的分类1. 内排序：内排序：在排序的整个过程中，待排序的所有记录在排序的整个过程中，待排序的所有记录全部被放置在内存中全部被放置在内存中2. 外排序外排序：由于待排序的记录个数太多，不能同

6、时放由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。间多次交换数据才能得到排序的结果。概概 述述 排序的基本概念排序的基本概念本章主要讲内排序本章主要讲内排序排序的分类排序的分类1. 基于比较：基于比较：基本操作基本操作关键码的关键码的比较比较和记录和记录的的移动移动。2. 不基于比较不基于比较：根据关键码的分布特征。根据关键码的分布特征。概概 述述 排序的基本概念排序的基本概念基于比较的内

7、排序基于比较的内排序1. 1. 插入排序插入排序2. 2. 交换排序交换排序3. 3. 选择排序选择排序4. 4. 归并排序归并排序1. 基本操作基本操作内排序在排序过程中的基本操作：内排序在排序过程中的基本操作：比较比较：关键码之间的大小比较；：关键码之间的大小比较；移动移动：记录从一个位置移动到另一个位置。：记录从一个位置移动到另一个位置。 2. 辅助存储空间辅助存储空间。辅助存储空间是指在数据规模一定的条件下，除了存辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。的其他存储空间。3.

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

9、数据项。一、插入排序一、插入排序 插入排序的主要操作是插入排序的主要操作是插入插入，其基本思，其基本思想是：每次将一个待排序的记录按其关键想是：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序为止列中，直到全部记录排好序为止。基本思想基本思想：在插入第：在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1个记录已经排好序。个记录已经排好序。 1、直接插入排序、直接插入排序插入排序插入排序有序序列有序序列无序序列无序序列12i-1ini+112i-1ini+1基本思想基本思想：在插入第：在插入第 i（i1）个

10、记录时，前面的）个记录时，前面的 i-1个记录已经排好序。个记录已经排好序。 （1）如何构造初始的有序序列？）如何构造初始的有序序列？（2）如何查找待插入记录的插入位置）如何查找待插入记录的插入位置?直接插入排序直接插入排序插入排序插入排序需解决的关键问题需解决的关键问题?r 0 1 2 3 4 5 6插入排序插入排序i = 2i = 3i = 4i = 6i = 5r0的作用的作用?暂存单元暂存单元监视哨监视哨解决方法：解决方法：将第将第1 1个记录看成是初始有序表，然后从第个记录看成是初始有序表，然后从第2 2个记录起个记录起依次插入到这个有序表中，直到将第依次插入到这个有序表中，直到将第

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

12、0有两个作用：有两个作用：1. 1. 进入循环之前暂存了进入循环之前暂存了riri的的值，使得不致于因记录的后移值，使得不致于因记录的后移而丢失而丢失riri的内容；的内容；2. 2. 在查找插入位置的循环中充在查找插入位置的循环中充当当哨兵哨兵。插入排序插入排序算法描述：算法描述：r0=ri; j=i-1; while (r0rj) rj+1=rj; j-;void insertSort (int r , int n) for (i=2; i=n; i+) r0=ri; /将无序区的第将无序区的第1个元素存放到岗哨中个元素存放到岗哨中 j=i-1;/j是有序区最后一个数据的下标是有序区最后一

13、个数据的下标 while (r0=1; d=d/2) 以以d为增量，进行组内直接插入排序；为增量，进行组内直接插入排序；解决方法：解决方法：在插入记录在插入记录riri时，自时，自ri-dri-d起往前跳跃式（跳跃起往前跳跃式（跳跃幅度为幅度为d d）搜索待插入位置，并且搜索待插入位置，并且r0r0只是暂存单元，只是暂存单元，不是哨兵。当搜索位置不是哨兵。当搜索位置0 0，表示插入位置已找到。，表示插入位置已找到。在搜索过程中，记录后移也是跳跃在搜索过程中，记录后移也是跳跃d d个位置。个位置。在整个序列中，前在整个序列中，前d d个记录分别是个记录分别是d d个子序列中的第个子序列中的第一个

14、记录，所以从第一个记录，所以从第d+1d+1个记录开始进行插入。个记录开始进行插入。插入排序插入排序关键问题关键问题( (2) )子序列内如何进行直接插入排序？子序列内如何进行直接插入排序？算法描述：算法描述：for (i=d+1; i0 & r0=1; d=d/2) for (i=d+1; i0 & r0rj) rj+d=rj; /记录后移记录后移d个位置个位置 j=j-d; /比较同一子序列的前一个记录比较同一子序列的前一个记录 rj+d=r0; 插入排序插入排序希尔排序算法的时间性能希尔排序算法的时间性能 希尔排序算法的时间性能是所取希尔排序算法的时间性能是所取增量增量的函数，而到的函数

15、，而到目前为止尚未有人求得一种最好的增量序列。目前为止尚未有人求得一种最好的增量序列。 研究表明，希尔排序的时间性能在研究表明，希尔排序的时间性能在O O( (n n2 2) )和和O O( (nlognlog2 2n n) )之间。当之间。当n n在某个特定范围内，希尔排序所在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为需的比较次数和记录的移动次数约为O O( (n n1 1.3 3 ) ) 。 插入排序插入排序 希尔排序开始时增量较大，每个子序列中的记录希尔排序开始时增量较大，每个子序列中的记录个数较少，从而排序速度较快；当增量较小时，虽然个数较少，从而排序速度较快；当增量较

16、小时，虽然每个子序列中记录个数较多，但整个序列已基本有序每个子序列中记录个数较多，但整个序列已基本有序，排序速度也较快。，排序速度也较快。 希尔排序是一种不稳定的排序算法希尔排序是一种不稳定的排序算法1. 1. 欲将序列（欲将序列（Q, H, C, Y, P, A, M, S, Q, H, C, Y, P, A, M, S, R, D, F, XR, D, F, X）中的关键码按字母升序重排，）中的关键码按字母升序重排，则初始步长为则初始步长为4 4的希尔排序一趟的结果是什的希尔排序一趟的结果是什么？（取么？（取d=4d=4）2. 以关键字序列（以关键字序列（256256，301301，751

17、751，129129，937937，863863，742742，694694，076076，438438）为例，）为例，分别写出执行直接插入和希尔排序算法的分别写出执行直接插入和希尔排序算法的各趟各趟排序结果，希尔排序（取排序结果，希尔排序（取d=5,3,1d=5,3,1）例49 38 65 97 76 13 27 48 55 4ji49133827一趟排序一趟排序： 13 27 48 55 4 49 38 65 97 76jiji274jiji5538jijiji二趟排序二趟排序： 13 4 48 38 27 49 55 65 97 76jiji6548ji9755ji7641 2 3 4

18、5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 10ji增量序列：增量序列：int d=5，3，1;交换排序的主要操作是交换排序的主要操作是交换交换，其主要思想是：，其主要思想是：在待排序列中选在待排序列中选两个两个记录，将它们的关键码相记录，将它们的关键码相比较，如果比较，如果反序反序（即排列顺序与排序后的次序（即排列顺序与排序后的次序正好相反），则正好相反），则交换交换它们的存储位置。它们的存储位置。 二、交换排序二、交换排序反序则交换反序则交换1 1、冒泡排序、冒泡排序基本思想：基本思想：两两比较两两比较相邻相邻记录的关键码，如果反记

19、录的关键码，如果反序则交换，直到没有反序的记录为止。序则交换，直到没有反序的记录为止。 rj rj+1 ri+1 rn- -1 rn 无序区无序区 有序区有序区 1ji- -1 已经位于最终位置已经位于最终位置反序则交换反序则交换交换排序交换排序冒泡排序过程示例冒泡排序过程示例 交换排序交换排序原有的冒泡排序算法原有的冒泡排序算法void BubbleSort(int r , int n) for(i=1;in;i+)/n个数，个数，n-1趟趟 for (j=1; jrj+1) t=rj;rj=rj+1; rj+1=t; 在一趟冒泡排序中，若有多个记录位于最终位置，在一趟冒泡排序中，若有多个记

20、录位于最终位置，应如何记载？应如何记载？ 如何确定冒泡排序的范围，使得已经位于最终位如何确定冒泡排序的范围，使得已经位于最终位置的记录不参与下一趟排序？置的记录不参与下一趟排序？ 如何判别冒泡排序的结束？如何判别冒泡排序的结束？交换排序交换排序需解决的关键问题需解决的关键问题?冒泡排序冒泡排序解决方法：解决方法：设变量设变量exchangeexchange记载记录交换的位置，则一趟排序后，记载记录交换的位置，则一趟排序后，exchangeexchange记载的一定是这一趟排序中记录的最后一次交记载的一定是这一趟排序中记录的最后一次交换的位置，且从此位置以后的所有记录均已经有序。换的位置，且从此

21、位置以后的所有记录均已经有序。交换排序交换排序关键问题：如何记载一趟排序过程中交换的多个记录？关键问题：如何记载一趟排序过程中交换的多个记录？交换交换交换交换交换交换交换排序交换排序关键问题：如何记载一趟排序过程中交换的多个记录？关键问题：如何记载一趟排序过程中交换的多个记录？算法描述：算法描述： if if （rjrj+1rjrj+1） rjrj+1 rjrj+1； exchange=j exchange=j； 解决方法：解决方法：设变量设变量exchangeexchange记载记录交换的位置，则一趟排序后，记载记录交换的位置，则一趟排序后，exchangeexchange记载的一定是这一趟

22、排序中记录的最后一次交记载的一定是这一趟排序中记录的最后一次交换的位置，且从此位置以后的所有记录均已经有序。换的位置，且从此位置以后的所有记录均已经有序。解决方法：解决方法：用用boundbound记住无序区的最后一个记录的位置，则每趟记住无序区的最后一个记录的位置，则每趟起泡排序的范围是起泡排序的范围是r1 - rboundr1 - rbound。在一趟排序后，从在一趟排序后，从exchangeexchange位置之后的记录一定是有位置之后的记录一定是有序的，所以序的，所以bound=exchangebound=exchange。交换排序交换排序关键问题：关键问题：如何确定起泡排序的范围如何

23、确定起泡排序的范围？交换交换交换交换交换交换解决方法：解决方法：用用boundbound记住无序区的最后一个记录的位置，则每趟记住无序区的最后一个记录的位置，则每趟起泡排序的范围是起泡排序的范围是r1 - rboundr1 - rbound。在一趟排序后，从在一趟排序后，从exchangeexchange位置之后的记录一定是有位置之后的记录一定是有序的，所以序的，所以bound=exchangebound=exchange交换排序交换排序关键问题：关键问题：如何确定起泡排序的范围如何确定起泡排序的范围？算法描述：算法描述：bound=exchange; bound=exchange; for

24、(j=1; jbound; j+)/for (j=1; jrj+1rjrj+1） rjrj+1 rjrj+1； exchange=j exchange=j； 解决方法：解决方法：在每一趟冒泡排序之前，令在每一趟冒泡排序之前，令exchangeexchange的初值为的初值为0 0，在，在以后的排序过程中，只要有记录交换，以后的排序过程中，只要有记录交换，exchangeexchange的的值就会大于值就会大于0 0。这样，在一趟比较完毕，就可以通过。这样，在一趟比较完毕，就可以通过exchangeexchange的值是否为的值是否为0 0来判别是否有记录交换，从而来判别是否有记录交换，从而判别

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

26、泡排序的结束。交换排序交换排序关键问题：关键问题：如何判别起泡排序的结束？如何判别起泡排序的结束？算法描述：算法描述：while (exchange) 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； 改进的冒泡排序算法改进的冒泡排序算法交换排序交换排序冒泡排序的时间性能分析冒泡排序的

27、时间性能分析最好情况（正序）：只有最好情况（正序）：只有1趟趟交换排序交换排序比较次数：比较次数：n-1移动次数：移动次数：0 时间复杂度为时间复杂度为O(n)。最坏情况（反序）：最坏情况（反序）：冒泡排序的时间性能分析冒泡排序的时间性能分析最好情况（正序）：最好情况（正序）：交换排序交换排序比较次数：比较次数：n-1移动次数：移动次数：0 时间复杂度为时间复杂度为O(n)；时间复杂度为时间复杂度为O(n2)。比较次数：比较次数：移动次数：移动次数：2) 1(1- -= = = =nn(n-i)n-1i2) 1(1- -= = = =n3n3(n-i)n-1i平均情况：平均情况：时间复杂度为时

28、间复杂度为O(n2)。方法稳定方法稳定2 2、快速排序、快速排序改进的着眼点：改进的着眼点：在冒泡排序中，记录的比较和移动是在冒泡排序中，记录的比较和移动是在在相邻相邻单元中进行的，记录每次交换只能上移或下移单元中进行的，记录每次交换只能上移或下移一个一个单元，因而总的比较次数和移动次数较多。单元，因而总的比较次数和移动次数较多。交换排序交换排序减少总的比较次数和移动次数减少总的比较次数和移动次数增大记录的比较和移动距离增大记录的比较和移动距离较大记录从前面直接移动到后面较大记录从前面直接移动到后面较小记录从后面直接移动到前面较小记录从后面直接移动到前面快速排序的基本思想快速排序的基本思想首先

29、选一个首先选一个轴值轴值（即比较的基准），通过一趟排序将（即比较的基准），通过一趟排序将待排序记录待排序记录分割分割成独立的两部分，前一部分记录的关成独立的两部分，前一部分记录的关键码均键码均小于或等于小于或等于轴值轴值，后一部分记录的关键码均，后一部分记录的关键码均大大于或等于于或等于轴值轴值，然后分别对这两部分重复上述方法，然后分别对这两部分重复上述方法，直到整个序列有序。直到整个序列有序。交换排序交换排序如何选择轴值？如何选择轴值？如何实现分割（称一次划分）？如何实现分割（称一次划分）？如何处理分割得到的两个待排序子序列？如何处理分割得到的两个待排序子序列？如何判别快速排序的结束？如何判

30、别快速排序的结束？需解决的关键问题需解决的关键问题?选择轴值（比较的基准）的方法：选择轴值（比较的基准）的方法：1. 1. 使用第一个记录的关键码；使用第一个记录的关键码；（要求掌握要求掌握）2. 2. 选取序列中间记录的关键码；选取序列中间记录的关键码；3. 3. 比较序列中第一个记录、最后一个记录和中间记比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换到第录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置；一个记录的位置；4. 4. 随机选取轴值。随机选取轴值。交换排序交换排序关键问题：关键问题：如何选择轴值？如何选择轴值？选取不同轴值的后果：选取

31、不同轴值的后果：决定两个子序列的长度，子序列的长度最好相等。决定两个子序列的长度，子序列的长度最好相等。交换排序交换排序关键问题：关键问题：如何实现一次划分？如何实现一次划分？ 用第一个记录的关键码作为轴值，将选定的轴值，用第一个记录的关键码作为轴值，将选定的轴值，通过比较和交换，将轴值移到某个位置，该位置左侧通过比较和交换，将轴值移到某个位置，该位置左侧的关键字都比轴值小，该位置右侧的关键字都比轴值的关键字都比轴值小，该位置右侧的关键字都比轴值大。大。ji交换排序交换排序一次划分一次划分jjiiijijjj例：例： 6 6 7 5 3 8 2 9 1 4 7 5 3 8 2 9 1 4 4

32、7 5 3 8 2 9 1 4 7 5 3 8 2 9 1 6 6 4 4 6 6 5 3 8 2 9 1 7 5 3 8 2 9 1 74 1 5 3 8 2 9 4 1 5 3 8 2 9 6 6 7 74 1 5 3 4 1 5 3 6 6 2 9 8 7 2 9 8 74 1 5 3 2 4 1 5 3 2 6 6 9 8 7 9 8 7一一趟趟快快速速排排序序示示意意图图6称称为为枢枢轴轴 第四次交换第四次交换 68 11 70 23 70 18 93 73 例：例： 70 73 70 23 93 18 11 68第一次交换第一次交换 68 73 70 23 93 18 11 70

33、第二次交换第二次交换 68 70 70 23 93 18 11 73ijiji 第三次交换第三次交换 68 11 70 23 93 18 70 73iij 第五次交换第五次交换 68 11 70 23 18 70 93 73i 完成一趟排序完成一趟排序 68 11 70 23 18 70 93 73解决方法：解决方法：设待划分的序列是设待划分的序列是rs rs rtrt，设参数设参数i i，j j分别指向分别指向子序列左、右两端的下标子序列左、右两端的下标s s和和t t，令令rsrs为轴值，为轴值，（1 1）j j从后从后向前向前扫描，直到扫描，直到rjrirjri，将将rjrj移动移动到到

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

35、rst, 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; /i为轴值记录的最终位置为轴值记录的最终位置解决方法：解决方法：对分割得到的两个子序列递归地执行快速排序。对分割得到的两个子序列递归地执行快速排序。交换排序交换排序关键问题：如何处理分割

36、得到的两个待排序子序列？关键问题：如何处理分割得到的两个待排序子序列？ ijij算法描述：算法描述：交换排序交换排序关键问题：如何处理分割得到的两个待排序子序列？关键问题：如何处理分割得到的两个待排序子序列？ void QuickSort (int r , int first, int end ) pivotpos = Partition (r, first, end ); /一次划分一次划分 QuickSort (r, first, pivotpos-1); /对前一个子序列进行快速排序对前一个子序列进行快速排序 QuickSort (r, pivotpos+1, end ); /对后一个子

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

38、ition (r, first, end ); QuickSort (r, first, pivotpos-1); QuickSort (r, pivotpos+1, end ); 算法描述：算法描述：交换排序交换排序关键问题：关键问题：如何判别快速排序的结束？如何判别快速排序的结束？ 最坏情况：最坏情况：每次划分只得到一个比上一次划分少一个记录的子序每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为列（另一个子序列为空），为O O( (n n2 2) )。最好情况：最好情况：每一次划分对一个记录定位后，该记录的左侧子表与每一次划分对一个记录定位后，该记录的左侧子表与右侧

39、子表的长度相同，为右侧子表的长度相同，为O O( (n nloglog2 2n n) )。快速排序的时间性能分析快速排序的时间性能分析交换排序交换排序平均情况：平均情况：为为O(nlog2n)。快速排序是较好的一种排序算法，但不稳定快速排序是较好的一种排序算法，但不稳定欲将序列（欲将序列（Q, H, C, Y, P, A, M, S, R, Q, H, C, Y, P, A, M, S, R, D, F, XD, F, X）中的关键码按字母升序重排，若）中的关键码按字母升序重排，若采用以第一个元素为轴值的快速排序法，采用以第一个元素为轴值的快速排序法，给出一趟排序的结果。给出一趟排序的结果。

40、练练 习习 选择排序的主要操作是选择排序的主要操作是选择选择，其主要思想是：，其主要思想是：每趟排序在当前待排序序列中选出关键码每趟排序在当前待排序序列中选出关键码最小最小的记录，添加到有序序列中。的记录，添加到有序序列中。 选择排序选择排序有序序列有序序列12i-1ink无序序列无序序列ni+112i-1ii交换交换最小记录最小记录1 1、简单选择排序、简单选择排序基本思想：基本思想：第第i i 趟在趟在n n- -i i+1+1（i i=1,2,=1,2, ,n n-1-1）个记录中个记录中选取关键码最小的记录作为有序序列中的第选取关键码最小的记录作为有序序列中的第i i个记录。个记录。

41、选择排序选择排序需解决的关键问题需解决的关键问题?如何在待排序序列中选出关键码最小的记录？如何在待排序序列中选出关键码最小的记录？如何确定待排序序列中关键码最小的记录在有如何确定待排序序列中关键码最小的记录在有序序列中的位置？序序列中的位置？ 简单选择排序示例简单选择排序示例最小者最小者 08交换交换21,08最小者最小者 16交换交换25,16最小者最小者 21交换交换49,21选择排序选择排序最小者最小者 25交换交换25,28最小者最小者 28不交换不交换选择排序选择排序简单选择排序示例简单选择排序示例无序区只有无序区只有一个记录一个记录解决方法：解决方法：设置一个整型变量设置一个整型变

42、量indexindex，用于记录在一趟比较的过程用于记录在一趟比较的过程中关键码最小的记录位置。中关键码最小的记录位置。 选择排序选择排序关键问题：关键问题：如何在无序区中选出关键码最小的记录？如何在无序区中选出关键码最小的记录？indexindex index算法描述：算法描述：index=i; for ( (j=i+1; j=n; j+) ) if ( (rjrindex) ) index=j;解决方法：解决方法：设置一个整型变量设置一个整型变量index，用于记录在一趟比较的过程用于记录在一趟比较的过程中关键码中关键码最小的记录位置。最小的记录位置。 关键问题：关键问题：如何在无序区中选

43、出关键码最小的记录？如何在无序区中选出关键码最小的记录？解决方法：解决方法：第第i趟简单选择排序的待排序区间是趟简单选择排序的待排序区间是ri rn，则则ri是无序是无序区第一个记录，所以，将区第一个记录，所以，将index所记载的关键所记载的关键码最小的记录与码最小的记录与ri交换交换。选择排序选择排序关键问题：如何确定关键问题：如何确定最小记录的最终位置？最小记录的最终位置？算法描述：算法描述： if ( (index!=i) ) ririndex; void selectSort ( int r , int n) for ( i=1; in; i+) /n-1趟趟 index=i; fo

44、r (j=i+1; j=n; j+)/在无序区中确定最小值的位置在无序区中确定最小值的位置 if (rjrindex) index=j; if (index!=i) ririndex; 简单选择排序算法简单选择排序算法选择排序选择排序简单选择排序算法的性能分析简单选择排序算法的性能分析移动次数：移动次数：最好情况（正序）：最好情况（正序）：0次次选择排序选择排序最坏情况：最坏情况：3(n-1)次次简单选择排序算法的性能分析简单选择排序算法的性能分析移动次数：移动次数：最好情况（正序）：最好情况（正序）：0次次选择排序选择排序空间性能：空间性能：需一个辅助空间（交换用的）。需一个辅助空间（交换用

45、的）。稳定性：稳定性：是一种稳定的排序算法。是一种稳定的排序算法。比较次数：比较次数：)() 1(21211nOnninni= =- -= =- - - -= =）（简单选择排序的时间复杂度为简单选择排序的时间复杂度为O(n2)。2 2、堆排序、堆排序改进的着眼点：改进的着眼点：如何如何减少减少关键码间的关键码间的比较比较次数。若次数。若能利用每趟比较后的结果，也就是在找出键值最小能利用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值较小的记录，则可减少后记录的同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过面的选择中所用的比较次数，从而提高整个排

46、序过程的效率。程的效率。选择排序选择排序减少关键码间的比较次数减少关键码间的比较次数查找最小值的同时，找出较小值查找最小值的同时，找出较小值堆的定义堆的定义堆是具有下列性质的堆是具有下列性质的完全二叉树完全二叉树：每个结点的值都：每个结点的值都小于或等于其左右孩子结点的值（称为小于或等于其左右孩子结点的值（称为小根堆小根堆），），或每个结点的值都大于或等于其左右孩子结点的值或每个结点的值都大于或等于其左右孩子结点的值（称为（称为大根堆大根堆）。）。选择排序选择排序182032364525385040281. 小根堆的根结点是小根堆的根结点是所有结点的最小者。所有结点的最小者。2. 较小结点靠近

47、根结较小结点靠近根结点，但不绝对。点，但不绝对。堆的定义堆的定义堆是具有下列性质的堆是具有下列性质的完全二叉树完全二叉树：每个结点的值都：每个结点的值都小于或等于其左右孩子结点的值（称为小于或等于其左右孩子结点的值（称为小根堆小根堆），），或每个结点的值都大于或等于其左右孩子结点的值或每个结点的值都大于或等于其左右孩子结点的值（称为（称为大根堆大根堆）。）。选择排序选择排序503845402836322018281. 大根堆的根结点是大根堆的根结点是所有结点的最大者。所有结点的最大者。2. 较大结点靠近根结较大结点靠近根结点，但不绝对。点，但不绝对。堆和序列的关系堆和序列的关系选择排序选择排序

48、将堆用顺序存储结构来存储，则堆对应一组序列。将堆用顺序存储结构来存储，则堆对应一组序列。5038454028363220182850 38 45 32 36 40 28 20 18 281 2 3 4 5 6 7 8 9 10采用顺序存储采用顺序存储基本思想：基本思想：首先将待排序的记录序列构造成一个大顶首先将待排序的记录序列构造成一个大顶堆，此时堆顶是所有记录的最大者，然后将它从堆中堆，此时堆顶是所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次移走，并将剩余的记录再调整成堆，这样又找出了次小的记录，以此类推，直到堆中只有一个记录小的记录，以此类推，直到堆中只有一

49、个记录选择排序选择排序堆排序堆排序需解决的关键问题需解决的关键问题?如何由一个无序序列建成一个堆（即初始建堆）？如何由一个无序序列建成一个堆（即初始建堆）？如何处理堆顶记录？如何处理堆顶记录？如何调整剩余记录，成为一个新堆（即重建堆）？如何调整剩余记录，成为一个新堆（即重建堆）？ 堆调整堆调整堆调整：堆调整：在一棵完全二叉树中，根结点的左右子树均是在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？堆，如何调整根结点，使整个完全二叉树成为一个堆？选择排序选择排序283632161825321618253628void sift ( int r , int k

50、, int m )/大顶堆大顶堆/要筛选结点的编号为要筛选结点的编号为k，堆中最后一个结点的编号为堆中最后一个结点的编号为m i=k; j=2*i; temp=ri; /将筛选记录暂存将筛选记录暂存 while (j=m ) /筛选还没有进行到叶子筛选还没有进行到叶子 /i是双亲下标，是双亲下标，j和和j+1是左右孩子下标是左右孩子下标 if (jm & rjrj) break; else ri=rj; i=j; j=2*j; ri=temp; /将筛选记录移到正确位置将筛选记录移到正确位置选择排序选择排序堆调整堆调整算法描述：算法描述：选择排序选择排序关键问题：关键问题：如何由一个无序序列建

51、成一个大顶堆？如何由一个无序序列建成一个大顶堆？282516321836163216282518362532162818362528323628161825算法描述：算法描述：for (i=n/2; i=1; i-) sift(r, i, n) ; 选择排序选择排序关键问题：关键问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？最后一个结点（叶子）的序号是最后一个结点（叶子）的序号是n，则最后一个分支结点即为结点则最后一个分支结点即为结点n的双亲，的双亲，其序号是其序号是n/2。依次判断非叶子结点，判断顺序从最后一个非叶子结点到根结点选择排序选择排序关键问题：关键问题：如何处理

52、堆顶记录？如何处理堆顶记录？32362816182536 28 32 25 18 161 2 3 4 5 6对对应应交换交换16 28 32 25 18 361 2 3 4 5 6对对应应321628361825算法描述：算法描述：r1rn-i+1; 选择排序选择排序关键问题：关键问题：如何处理堆顶记录？如何处理堆顶记录？解决方法：解决方法：第第 i 次处理堆顶是将堆顶记录次处理堆顶是将堆顶记录r1与序列中第与序列中第n-i+1个个记录记录rn-i+1交换。交换。321628361825选择排序选择排序关键问题：关键问题：如何调整剩余记录，成为一个新堆？如何调整剩余记录，成为一个新堆？1632

53、281636182518163632252816 28 32 25 18 361 2 3 4 5 6对对应应18 28 16 25 32 361 2 3 4 5 6对对应应32 28 16 25 18 361 2 3 4 5 6交换交换3232和和1818交换交换3232和和1616解决方法：解决方法：第第 i 次调整剩余记录，此时，剩余记录有次调整剩余记录，此时，剩余记录有n-i个，调整个，调整根结点至第根结点至第n-i个记录。个记录。选择排序选择排序关键问题：关键问题：如何调整剩余记录，成为一个新堆？如何调整剩余记录，成为一个新堆？算法描述：算法描述：sift(r, 1, n-i);堆排序

54、算法堆排序算法void HeapSort ( int r, int n) for (i=n/2; i=1; i-) /初建堆初建堆 sift(r, i, n) ; for (i=1; in; i+ ) r1rn- -i+1; /移走堆顶移走堆顶 sift(r, 1, n- -i); /重建堆重建堆 选择排序选择排序堆排序算法的性能分析堆排序算法的性能分析第第1个个for循环是初始建堆，需要循环是初始建堆，需要O(n)时间；时间；第第2个个for循环是输出堆顶重建堆，共需要取循环是输出堆顶重建堆，共需要取n-1次堆顶次堆顶记录，第记录，第 i 次取堆顶记录重建堆需要次取堆顶记录重建堆需要O(lo

55、g2i)时间，需时间，需要要O(nlog2n)时间；时间；因此整个时间复杂度为因此整个时间复杂度为O(nlog2n)，这是堆排序的这是堆排序的最好最好、最坏最坏和和平均平均的时间代价。的时间代价。选择排序选择排序归并排序归并排序归并排序的主要操作是归并排序的主要操作是归并归并，其主要思想是：，其主要思想是：将若干有序序列逐步归并，最终得到一个有序将若干有序序列逐步归并，最终得到一个有序序列。序列。 归并排序归并排序归并：归并：将两个或两个以上的有序序列合并成一个有序将两个或两个以上的有序序列合并成一个有序序列的过程。序列的过程。 基本思想：基本思想：将一个具有将一个具有n n个待排序记录的序列

56、看成个待排序记录的序列看成是是n n个长度为个长度为1 1的有序序列，然后进行两两归并，得的有序序列，然后进行两两归并，得到到n n/2/2个长度为个长度为2 2的有序序列，再进行两两归并，得的有序序列，再进行两两归并，得到到n n/4/4个长度为个长度为4 4的有序序列，的有序序列，直至得到一个，直至得到一个长度为长度为n n的有序序列为止。的有序序列为止。二路归并排序二路归并排序归并排序归并排序需解决的关键问题需解决的关键问题?如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？怎样完成一趟归并？怎样完成一趟归并？如何控制二路归并的结束？如何控制二路归并的结束？关键问题

57、：关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？归并排序归并排序602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60关键问题：关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？归并排序归并排序602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60归并可以就地进行吗归并可以就地进行吗?在归并过程中，可能会破坏原在归并过程中，可能会破坏原来的有序序列，所以，将归并来的有序序列，所以，将归并的

58、结果存入另外一个数组中。的结果存入另外一个数组中。 关键问题：关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？归并排序归并排序602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60关键问题：关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？归并排序归并排序602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60子序列的长度一定相等吗子序列的长度一定相等吗?关键问题：关键问题：如何将两个有序序列

59、合成一个有序序列？如何将两个有序序列合成一个有序序列？归并排序归并排序602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60关键问题：关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？归并排序归并排序设相邻的有序序列为设相邻的有序序列为rs rm和和rm+1 rt，归并，归并成一个有序序列成一个有序序列r1s r1t s m m+1 t r s t r1 ijkvoid Merge (int r , int r1 , int s, int m, int t ) i=s; j=m+1; k=s;

60、 while (i=m & j=t) if (ri=rj) r1k+=ri+; else r1k+=rj+; if (i=m) while (i=m) /收尾处理收尾处理 r1k+=ri+; /前一个子序列前一个子序列 else while (j=t) r1k+=rj+; /后一个子序列后一个子序列 归并排序归并排序关键问题：关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？算法描述：算法描述：s m m+1 t r s t r1 ijk归并排序归并排序关键问题：关键问题：怎样完成一趟归并？怎样完成一趟归并？602031544556520 605 3144 55