数据结构-内部排序

1、本章主要内容：本章主要内容： 主要介绍以下各种内部排序方法的基本思想、算主要介绍以下各种内部排序方法的基本思想、算法特点、排序过程及时间复杂度分析。法特点、排序过程及时间复杂度分析。本章重点：本章重点：1.1.掌握各种排序方法中的高效方法掌握各种排序方法中的高效方法( (插入排序的希尔排序插入排序的希尔排序、交换排序的快速排序、选择排序的堆排序、归并排序、交换排序的快速排序、选择排序的堆排序、归并排序) )；2.2.掌握各种排序方法的掌握各种排序方法的时间复杂度时间复杂度；3.3.理解排序方法理解排序方法“稳定稳定”和和“不稳定不稳定”的含义。的含义。 第十章第十章 内部排序内部排序第十章第十

2、章 内部排序内部排序 10.1 10.1 概概 述述 10.2 10.2 插入排序插入排序 10.3 10.3 快速排序快速排序 10.4 10.4 选择排序选择排序 10.5 10.5 归并排序归并排序 10.6 10.6 基数排序基数排序 10.7 10.7 各种排序方法的比较各种排序方法的比较 10.1 10.1 概概 述述一、排序的定义一、排序的定义二、二、一些排序的术语一些排序的术语一、一、排序的定义排序的定义 10.1 概概 述述 排序排序是计算机程序设计中的一种重要操作，它的功能是将是计算机程序设计中的一种重要操作，它的功能是将一个数据元素一个数据元素( (或记录或记录) )的任

3、意序列，重新排列成一个按关键字的任意序列，重新排列成一个按关键字有序的序列。排序的目的之一是方便数据查找。有序的序列。排序的目的之一是方便数据查找。 对排序下一个对排序下一个确切的定义确切的定义：假设含假设含n n个记录的序列为：个记录的序列为：RR1 1，R R2 2，R Rn n 其相应的关键字序列为：其相应的关键字序列为：KK1 1，K K2 2，K Kn n 需确定需确定1 1，2 2，n n的一种排列的一种排列p p1 1，p p2 2，p pn n，使其相应，使其相应的关键字满足如下的非递减的关键字满足如下的非递减( (或非递增或非递增) )关系：关系： KpKp1 1KpKp2

4、2KpKpn n使使RR1 1，R R2 2，R Rn n 成为关键字有序的序列：成为关键字有序的序列： RpRp1 1，RpRp2 2，RpRpn n 这种操作称为排序。这种操作称为排序。 二、一些排序的术语二、一些排序的术语 10.110.1 概概 述述1. 1. 排序方法的稳定与不稳定排序方法的稳定与不稳定 在排序过程中，有若干记录的在排序过程中，有若干记录的关键字相等关键字相等，即，即K Ki i=K=Kj j(1in(1in，1 1jn1 1jn，ij) ij) ，在排序前后，含相等，在排序前后，含相等关键字的记录的相对位置保持不变，即排序前关键字的记录的相对位置保持不变，即排序前R

5、 Ri i在在R Rj j之前，之前，排序后排序后R Ri i仍在仍在R Rj j之前，称这种排序方法是之前，称这种排序方法是稳定的稳定的； 反之，若可能使排序后的序列中反之，若可能使排序后的序列中R Ri i在在R Rj j之后，称所用排之后，称所用排序方法是序方法是不稳定的不稳定的。 2. 2. 内部排序和外部排序内部排序和外部排序 内部排序内部排序如果在排序过程中，只使用计算机的如果在排序过程中，只使用计算机的内存存放待排序所有记录，称这种排序为内部排序。内存存放待排序所有记录，称这种排序为内部排序。( (或或对内存中的记录进行的排序对内存中的记录进行的排序) )。 外部排序外部排序如果

6、待排序的文件较大，排序期间文如果待排序的文件较大，排序期间文件的全部记录不能同时存放在计算机的内存里，要借助件的全部记录不能同时存放在计算机的内存里，要借助计算机的外存才能完成排序，称之为计算机的外存才能完成排序，称之为“外部排序外部排序”。 在外部排序过程中，记录必须在计算机的内存和外在外部排序过程中，记录必须在计算机的内存和外存之间移动。这样，内外存之间的数据交换次数就成为存之间移动。这样，内外存之间的数据交换次数就成为影响外部排序速度的主要因素。影响外部排序速度的主要因素。 二、一些排序的术语二、一些排序的术语 10.110.1 概概 述述3. 3. 排序方法的种类排序方法的种类 (1)

7、(1)按排序过程中依据不同的原则分为五大类：按排序过程中依据不同的原则分为五大类：插入排序、交插入排序、交换排序、选择排序、归并排序和基数排序。换排序、选择排序、归并排序和基数排序。(2)(2)按时间复杂度划分为三类按时间复杂度划分为三类： 简单排序方法简单排序方法：其时间复杂度为：其时间复杂度为O(nO(n2 2) )，该方法是，该方法是，属于简单排序的排序方法包括：除希尔排序的属于简单排序的排序方法包括：除希尔排序的插入排序、冒泡插入排序、冒泡排序和简单排序。排序和简单排序。 先进先进( (高效高效) )的排序方法的排序方法：其时间复杂度为：其时间复杂度为O(nlogn)O(nlogn)，

8、属于，属于此排序方法的有：此排序方法的有：快速排序、堆排序、归并排序快速排序、堆排序、归并排序。其中。其中的排序方法。的排序方法。 基数排序方法基数排序方法：其时间复杂度为：其时间复杂度为O(dO(d* *n)n)，该方法是，该方法是。 二、一些排序的术语二、一些排序的术语 10.110.1 概概 述述 二、一些排序的术语二、一些排序的术语 10.110.1 概概 述述4. 4. 效率分析效率分析 (1)(1)时间复杂度：关键字的比较次数和记录移动次数。时间复杂度：关键字的比较次数和记录移动次数。 (2)(2)空间复杂度：执行算法所需的附加存储空间。空间复杂度：执行算法所需的附加存储空间。5

9、5排序的基本操作排序的基本操作 排序的基本操作主要有两种：排序的基本操作主要有两种： (1)(1)比较两个关键字大小比较两个关键字大小 (2)(2)根据比较的结果将记录从一个位置移到另一个位置。根据比较的结果将记录从一个位置移到另一个位置。 二、一些排序的术语二、一些排序的术语 10.110.1 概概 述述6 6排序记录的存储方式排序记录的存储方式 (1) (1) 采用顺序表，采用顺序表，相邻的记录，存储位置也相邻，记录相邻的记录，存储位置也相邻，记录的次序关系由其存储位置决定，实现排序必须借助移动记录。的次序关系由其存储位置决定，实现排序必须借助移动记录。 (2) (2) 采用静态链表，采用

10、静态链表，记录之间的次序关系由指针指示，记录之间的次序关系由指针指示，则实现排序不需要移动记录，仅需修改指针即可。这种方式则实现排序不需要移动记录，仅需修改指针即可。这种方式下实现的排序又称表排序。下实现的排序又称表排序。 (3)(3)待排序记录本身存储在一组地址连续的存储单元内，待排序记录本身存储在一组地址连续的存储单元内，同时另设一个指示各记录存储位置的地址向量，在排序同时另设一个指示各记录存储位置的地址向量，在排序过程过程中不移动记录本身，而移动地址向量中这些记录的中不移动记录本身，而移动地址向量中这些记录的“地址地址”，在排序结束之后再按照地址向量中的值调整记录的存储位置，在排序结束之

11、后再按照地址向量中的值调整记录的存储位置，这种方式下实现的排序又称地址排序。这种方式下实现的排序又称地址排序。10.2 10.2 插入排序插入排序一、一、插入排序概述插入排序概述二、二、直接插入排序直接插入排序三、三、折半插入排序折半插入排序四、四、希尔排序希尔排序(Shell)(Shell)一、一、插入排序概述插入排序概述1 1插入排序思想插入排序思想 插入排序的基本思想是，每一次只考虑一个待排序的插入排序的基本思想是，每一次只考虑一个待排序的元素，同已排序的元素作比较，在比较完毕之后，把待排序元素，同已排序的元素作比较，在比较完毕之后，把待排序的元素放到合适的位置，然后再选下一个待排序的元

12、素。的元素放到合适的位置，然后再选下一个待排序的元素。10.210.2插插入入排排序序2 2插入排序的基本算法插入排序的基本算法假设所有待排序的元素在数组假设所有待排序的元素在数组rnrn之内。之内。(1)(1)初始状态初始状态 排序开始之前，整个数组排序开始之前，整个数组r r被划分被划分两个部分：有序区两个部分：有序区和无序区。和无序区。 有序区有序区内存放的是已排好顺序的元素；内存放的是已排好顺序的元素； 无序区无序区内存放的是尚未排好顺序的元素内存放的是尚未排好顺序的元素。 初始时，有序区只有初始时，有序区只有1 1个元素个元素r1r1。 无序区里的元素是无序区里的元素是r2 r2 r

13、nrn。(2)(2)终态终态 在排序操作完成之后，在有序区中包含整个数组在排序操作完成之后，在有序区中包含整个数组r r，而，而在无序区内则为空。整个状态称为终态。在无序区内则为空。整个状态称为终态。一、一、插入排序概述插入排序概述10.210.2插插入入排排序序(3)(3)基本操作步骤基本操作步骤a.a.首先从无序区中取一个记录，通常是第一个记录；首先从无序区中取一个记录，通常是第一个记录；b.b.然后将其同有序区中的元素比较，并按其关键字值大然后将其同有序区中的元素比较，并按其关键字值大小，把该记录插入到有序区中的适当位置，这样有序区小，把该记录插入到有序区中的适当位置，这样有序区中始终保

14、持有序性；中始终保持有序性；c.c.再从无序区中取一个记录，重复再从无序区中取一个记录，重复b.b.操作，直到终态。操作，直到终态。一、一、插入排序概述插入排序概述10.210.2插插入入排排序序 直接插入排序是一种最简单的排序方法。它的基本操直接插入排序是一种最简单的排序方法。它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增个新的、记录数增1 1的有序表。的有序表。 1 1排序思想排序思想 2 2算法算法 将序列中的第将序列中的第1 1个记录看成是一个有序的子序列个记录看成是一个有序的子序列; ;从第从第2 2个记

15、录起逐个进行插入，直至整个序列变成按关键个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。整个排序过程为进行字非递减有序序列为止。整个排序过程为进行n-1n-1趟插入。趟插入。同时后移记录。同时后移记录。二、二、直接排序概述直接排序概述10.210.2插插入入排排序序3 3算法描述算法描述void InsertSort(Sqlist &L)void InsertSort(Sqlist &L) for(i=2;i=L.length;+i) for(i=2;i=L.length;+i) L.r0=L.ri; / L.r0=L.ri; /设置哨兵设置哨兵 for(j=i-1;L.r0

16、.keyL.rj.key;-j)for(j=i-1;L.r0.keyL.rj.key;-j) L.rj+1=L.rj; / L.rj+1=L.rj; /记录后移记录后移 L.rj+1=L.r0; /L.rj+1=L.r0; /插入到正确位置插入到正确位置 二、二、直接排序概述直接排序概述10.210.2插插入入排排序序例例1 1 直接插入排序的过程。直接插入排序的过程。初始关键字：初始关键字： ( (4949) ) 3838 65 97 76 13 27 65 97 76 13 27 4949 i=2: ( i=2: (3838) () (3838 4949) ) 6565 97 76 13

17、27 97 76 13 27 4949 i=3: ( i=3: (6565) () (38 4938 49 6565) ) 9797 76 13 27 76 13 27 4949 i=4: ( i=4: (9797) () (38 49 6538 49 65 9797) ) 7676 13 27 13 27 4949 i=5: (i=5: (7676) () (38 49 6538 49 65 7676 97 97) ) 1313 27 27 4949 i=6: ( i=6: (1313) () (1313 38 49 65 76 9738 49 65 76 97) ) 27 27 4949

18、i=7: ( i=7: (2727) () (1313 27 27 38 49 65 76 9738 49 65 76 97) ) 4949 i=8: ( i=8: (4949) () (13 27 38 4913 27 38 49 4949 65 76 9765 76 97) )二、二、直接排序概述直接排序概述10.210.2插插入入排排序序 4. 4. 算法分析算法分析 (1)(1)稳定性稳定性 直接插入排序是直接插入排序是的排序方法。的排序方法。 (2)(2)算法效率算法效率 a.a.时间复杂度时间复杂度 时间复杂度为时间复杂度为。 b.b.空间复杂度空间复杂度 它只需要一个记录的辅助空

19、间，它只需要一个记录的辅助空间，O(1)O(1)。 二、二、直接排序概述直接排序概述10.210.2插插入入排排序序三、折半插入排序三、折半插入排序 从减少从减少“比较比较”和和“移动移动”两种操作的次数考虑，两种操作的次数考虑，折半插入排序折半插入排序是是直接插入排序直接插入排序的一种改进方法。的一种改进方法。1 1折半插入排序思想折半插入排序思想 由于插入排序的基本操作是在由于插入排序的基本操作是在有序表有序表中进行查找和中进行查找和插入，在有序表中用插入，在有序表中用折半查找折半查找方法可以提高查找效率，方法可以提高查找效率，利用折半查找的方法来进行插入排序可以减少比较次数，利用折半查找

20、的方法来进行插入排序可以减少比较次数，从而提高整个算法的执行效率。从而提高整个算法的执行效率。 10.210.2插插入入排排序序2.2.算法描述算法描述void BInsertSort(Sqlist &L)void BInsertSort(Sqlist &L) for(i=2;i=L.length;+i) for(i=2;i=L.length;+i) L.r0=L.ri; / L.r0=L.ri; /将将L.riL.ri暂存到暂存到L.r0L.r0 low=1;high=i-1;low=1;high=i-1; while(low=high) while(low=high) m=(low+hig

21、h)/2; m=(low+high)/2; if(L.r0.keyL.rm.key) high=m-1; if(L.r0.key=high+1;-j) for(j=i-1;j=high+1;-j) L.rj+1=L.rj; / L.rj+1=L.rj; /记录后移记录后移 L.rhigh+1=L.r0; /L.rhigh+1=L.r0; /插入到正确位置插入到正确位置 三、折半插入排序三、折半插入排序10.210.2插插入入排排序序3 3算法分析算法分析(1)(1)稳定性稳定性折半排序是折半排序是排序方法。排序方法。(2)(2)算法效率算法效率时间复杂度仍为时间复杂度仍为O(nO(n2 2)

22、)。空间复杂度为空间复杂度为O(1)O(1)，附加存储空间同直接插入排序。，附加存储空间同直接插入排序。三、折半插入排序三、折半插入排序10.210.2插插入入排排序序四、希尔排序四、希尔排序(Shell)(Shell) 又称又称“缩小增量排序缩小增量排序”，属于插入排序类的方法，但在，属于插入排序类的方法，但在时间效率上较前几种排序方法有较大的改进时间效率上较前几种排序方法有较大的改进。1.1.基本思想基本思想 在直接插入排序中，当在直接插入排序中，当n n较小时，排序的效率比较高。较小时，排序的效率比较高。 希尔排序方法希尔排序方法是先将待排序记录是先将待排序记录分割成为若干子序列分割成为

23、若干子序列，分别在分别在子序列中进行直接插入排序子序列中进行直接插入排序，待整个序列中的记录，待整个序列中的记录“基本有序基本有序”时，再对全体记录进行一次直接排序。时，再对全体记录进行一次直接排序。10.210.2插插入入排排序序 子序的分割不是简单的子序的分割不是简单的“逐段分割逐段分割”，而是将待排序，而是将待排序的记录按照的记录按照某个增量某个增量d d分成若干子序列，将相隔分成若干子序列，将相隔d d的记录组的记录组成一个子序列。在成一个子序列。在子序列中进行直接插入排序子序列中进行直接插入排序。随着增量。随着增量d d的逐步变小，各子序列中的记录逐渐增多，各子序列中的逐步变小，各子

24、序列中的记录逐渐增多，各子序列中的记录随着的记录随着d d的减小而趋于有序。当增量减小到的减小而趋于有序。当增量减小到1 1时，已达时，已达到基本有序，再进行直接排序，排序就完成了。到基本有序，再进行直接排序，排序就完成了。 在希尔排序中关键字较小的记录不是一步一步的前移，在希尔排序中关键字较小的记录不是一步一步的前移，而是而是跳跃式的前移跳跃式的前移，因此效率提高。，因此效率提高。 四、希尔排序四、希尔排序(Shell)(Shell)10.210.2插插入入排排序序 2. 2. 算法算法 (1)(1)按距离按距离d d将待排序数组将待排序数组r r 分成若干个小组，等距离分成若干个小组，等距

25、离者在同一个组中，初始距离为者在同一个组中，初始距离为d d1 1； (2)(2)在每个小组中进行直接插入排序；在每个小组中进行直接插入排序； (3)(3)修改距离，选一个小于上次距离修改距离，选一个小于上次距离d d1 1的距离的距离d d2 2； (4)(4)重复重复(1)(1)、(2)(2)和和(3)(3)，直到直到d=1d=1为止为止。四、希尔排序四、希尔排序(Shell)(Shell)10.210.2插插入入排排序序3. 3. 举例举例 例例2 2初始关键字：初始关键字： 49 38 65 97 76 13 27 49 55 04第一次：第一次： d d1 1= = n/2n/2 =

26、5=5分成分成5 5组：组：49,13，38,27，65,49，97,55，76,04各组排序后：各组排序后： 13 27 49 55 04 49 38 65 97 76第二次：第二次：d2= d1/2 =3分成分成3 3组：组：13,55,38,76，27,04,65，49,49,97排序后：排序后： 13 04 49 38 27 49 55 65 97 76第三次：第三次：d d3 3=2=2 分成分成2 2组组：13,49,27,55,97，04,38,49,65,76排序后：排序后：13 04 27 38 49 49 55 65 97 76第四次：第四次：d4=1 04 13 27 3

27、8 49 49 55 65 76 97四、希尔排序四、希尔排序(Shell)(Shell)10.210.2插插入入排排序序4 4算法描述算法描述void shellsort(Sqlist &L,int dlta,int t)void shellsort(Sqlist &L,int dlta,int t)/按增量序列按增量序列dlta0dlta0t-1 t-1 对顺序表对顺序表L L作希尔排序作希尔排序 for(k=0;kt;+k)for(k=0;kt;+k) ShellInsert(L, ShellInsert(L,dltakdltak);); void ShellInsert(&L,void

28、 ShellInsert(&L,&dk&dk) )for(i=for(i=dkdk+1;i=L.length;+i) +1;i=L.length;+i) /增量是增量是dkdk而不是而不是1 1 if (l.ri.keyL.ri- if (l.ri.key0& (L.r0.key0& (L.r0.keyL.r2L.r1L.r2，则将两个记录交换；依次类推，则将两个记录交换；依次类推，L.riL.ri与与Li+1Li+1比较，直比较，直至第至第n-1n-1个记录和第个记录和第n n个记录的关键字进行比较完毕。个记录的关键字进行比较完毕。 第第1 1趟比较结果将序列中趟比较结果将序列中关键字最大关

29、键字最大的记录的记录放置到最后放置到最后一个位置一个位置，称为，称为“沉底沉底”，而，而最小最小的则的则上浮一个位置上浮一个位置，如，如水泡在水中上浮，且水泡在水中上浮，且n n个记录比较个记录比较n-1n-1次。次。 第第i i 趟比较，将趟比较，将L.r1L.r1到到L.rn-i+1L.rn-i+1依次比较相邻两依次比较相邻两个记录的关键字，并在个记录的关键字，并在“逆序逆序”时交换相邻记录，结果时交换相邻记录，结果n-n-i+1i+1个记录中关键字最大的记录放置到个记录中关键字最大的记录放置到n-i+1n-i+1位置上。位置上。 n n个记录的整个排序过程需进行个记录的整个排序过程需进行

30、n-1n-1趟冒泡排序。趟冒泡排序。2. 图示：图示：第一轮：第一轮：a1 10a2 5a3 8a4 010 5 5 1051080108 810 5 810 0第二轮：第二轮： a1 5a2 8a3 0 10010 0沉低沉低上浮上浮5 58 858080 0 8沉低沉低上浮上浮第三轮：第三轮：a1 5a2 0 0 5结果：结果：a1 a2 a3 a4 0 5 8 104个数比较个数比较3轮轮，n个数比较个数比较n-1轮轮4个数比较个数比较3次次3个数比较个数比较2次次2个数比较个数比较1次次 一、冒泡排序一、冒泡排序10.310.3快快速速排排序序3.算法：算法：main()int a11

31、,i,j,t; printf(“input 10 numbers:n”); for(i=1;i=10;i+) scanf(“%d”,&ai); printf(“n”); for(i=1;i=9;i+) for(j=1;jaj+1) t=aj;aj=aj+1;aj+1=t; printf(“the sorted numbers:n”); for(i=1;i27 i(low) j(high)j一次交换一次交换 27 38 65 97 76 13 49 49 4913jji三次交换三次交换 27 38 13 97 76 49 65 494997四次交换四次交换 27 38 13 49 76 97 6

32、5 49i=j完成一趟排序完成一趟排序 27 38 13 49 76 97 65 49iijijj 二、快速排序二、快速排序10.310.3快快速速排排序序1 1算法描述算法描述int Partition(Sqlist &L,int low,int high)int Partition(Sqlist &L,int low,int high) pivotkey=L.rlow.key; pivotkey=L.rlow.key;L.r0=L.rlow;L.r0=L.rlow; while(lowhigh) while(lowhigh) while(low=pivotkey) while(low=pi

33、votkey) -high; -high; L.rlow L.rhigh; L.rlow L.rhigh; L.rlow =L.rhigh;L.rlow =L.rhigh; While(lowhigh&L.rlow.key=pivotkey) While(lowhigh&L.rlow.key=pivotkey) +low; +low; L.rlow L.rhigh; L.rlow L.rhigh; L.rhigh=L.rlow;L.rhigh=L.rlow; L.rlow=L.r0;L.rlow=L.r0; return low; return low; 二、快速排序二、快速排序10.310.

34、3快快速速排排序序递归的快速排序算法：递归的快速排序算法：void Qsort(Sqlist &L,int low,int high)void Qsort(Sqlist &L,int low,int high) if(lowhigh) if(lowhigh) pivotloc=Partition(L,low,high); / pivotloc=Partition(L,low,high); /确定枢轴位置确定枢轴位置 QSort(L,low,pivotloc-1);QSort(L,low,pivotloc-1); Qsort(L,pivotloc+1,high); Qsort(L,pivotlo

35、c+1,high); 二、快速排序二、快速排序10.310.3快快速速排排序序 5. 5. 算法分析算法分析 (1)(1)稳定性稳定性 快速排序是快速排序是的排序方法。的排序方法。 (2)(2)时间复杂度时间复杂度 快速排序的时间复杂度为快速排序的时间复杂度为O(nlogn)O(nlogn)数量级。数量级。 (3)(3)空间复杂度空间复杂度 由于快速排序是一个递归过程，需一个栈的附加空间，由于快速排序是一个递归过程，需一个栈的附加空间，栈的深度为栈的深度为O(logn)O(logn)。 二、快速排序二、快速排序10.310.3快快速速排排序序10.4 10.4 选择排序选择排序 一、简单选择排

36、序一、简单选择排序 二、二、堆排序堆排序 基本思想基本思想 每一次都在数组中选取关键字最小的一个记录，每一次都在数组中选取关键字最小的一个记录，送到已经排好序的记录序列的后面，直到完成整个排送到已经排好序的记录序列的后面，直到完成整个排序工作。即每一趟在序工作。即每一趟在n-i+1n-i+1个记录中选取关键字最小个记录中选取关键字最小的记录作为有序序列中第的记录作为有序序列中第i i个记录。个记录。10.4 10.4 选择排序选择排序10.4 10.4 选选择择排排序序一、简单选择排序一、简单选择排序1.1.基本思想基本思想 通过通过n-in-i次关键字的比较，在次关键字的比较，在n-i+1n

37、-i+1个记录中选出关个记录中选出关键字最小的记录，并和第键字最小的记录，并和第i i个记录交换。个记录交换。2.2.算法描述算法描述void SelectSort(Sqlist &L)void SelectSort(Sqlist &L) for(i=1;iL.length;+i) for(i=1;iL.length;+i) min=i;min=i; for(j=i+1;j=L.length;j+)for(j=i+1;j=L.length;j+) if(L.rj.keyL.rmin.key) if(L.rj.keyL.rmin.key) min=j; min=j; if(min!=i) if(

38、min!=i) t=L.rmin; t=L.rmin; L.rmin=L.ri; L.rmin=L.ri; L.ri=t; L.ri=t; 3. 3. 算法分析算法分析(1)(1)稳定性稳定性简单选择排序方法是简单选择排序方法是。(2)(2)时间复杂度时间复杂度为为O(nO(n2 2) )(3)(3)空间复杂度空间复杂度为为O(1)O(1)。 10.4 10.4 选选择择排排序序 二、堆排序二、堆排序 1. 1. 树形选择排序树形选择排序 树形选择排序又称树形选择排序又称锦标赛排序锦标赛排序，是一种按照锦标赛，是一种按照锦标赛的思想进行选择排序的方法。的思想进行选择排序的方法。 出发点出发点是

39、利用前一次比较的结果，减少是利用前一次比较的结果，减少“比较比较”的的次数次数。在。在n n个关键字中选出最小值，至少进行个关键字中选出最小值，至少进行n-1n-1次，次，在在n-1n-1个关键字中选择次小值并非一定要进行个关键字中选择次小值并非一定要进行n-2n-2次比较次比较，若能利用前若能利用前n-1n-1次比较所得信息，则可减少以后各趟选择次比较所得信息，则可减少以后各趟选择排序中所用的比较次数。排序中所用的比较次数。 每选择一个次小关键字仅需进行每选择一个次小关键字仅需进行 loglog2 2n n ( (树的深度树的深度-1)-1)次比较，时间复杂度为次比较，时间复杂度为O(nlo

40、gO(nlog2 2n)n)。但所需辅助存储空间较。但所需辅助存储空间较多。多。 n-1+(n-1)log2n10.4 10.4 选选择择排排序序 二、堆排序二、堆排序 2. 2. 堆排序堆排序(1)(1)堆的定义堆的定义 n n个元素的序列个元素的序列kk1 1,k,k2 2, ,k,kn n ，当且仅当满足下述关系，当且仅当满足下述关系时，称之为堆。时，称之为堆。 k ki ikk2i 2i k ki ikk2i2i k ki ikk2i+12i+1 k ki ikk2i+12i+1 若将用一维数组存储的序列看成是若将用一维数组存储的序列看成是一个完全二叉树一个完全二叉树，则，则完全二叉树

41、中的任意非叶结点的关键字值大完全二叉树中的任意非叶结点的关键字值大( (或小或小) )于它的左、于它的左、右孩子结点的值。这种数据结构即为堆。右孩子结点的值。这种数据结构即为堆。或或10.4 10.4 选选择择排排序序 二、堆排序二、堆排序 10.4 10.4 选选择择排排序序 二、堆排序二、堆排序22124030343650875087403036341222小顶堆小顶堆大顶堆大顶堆(2)(2)堆排序堆排序 在堆结构中输出在堆结构中输出堆顶最小值堆顶最小值( (或最大值或最大值) )后，使得后，使得剩余剩余n-1n-1个元素的序列重又建成一个堆个元素的序列重又建成一个堆，则得到，则得到n n

42、个元个元素中的素中的次小值次小值( (或次大值）或次大值）。如此反复执行，便能得到。如此反复执行，便能得到一个有序序列，这个过程称为一个有序序列，这个过程称为堆排序堆排序。 堆排序需解决堆排序需解决两个问题两个问题： a. a. 由一个无序序列建成一个堆。由一个无序序列建成一个堆。 b. b. 在输出堆顶元素之后，调整剩余元素成为一个在输出堆顶元素之后，调整剩余元素成为一个新的堆。新的堆。10.4 10.4 选选择择排排序序 二、堆排序二、堆排序(3)(3)堆排序的算法堆排序的算法a. a. 建立包含建立包含k k1 1,k,k2 2,k,k3 3, ,k kn n的堆。的堆。b. b. 输出

43、堆顶元素，采用输出堆顶元素，采用堆顶元素堆顶元素R R1 1与最后一个元素与最后一个元素R Rn n交交换，最大换，最大( (或最小或最小) )元素得到正确的排序位置，此时前元素得到正确的排序位置，此时前n-1n-1个元素不再满足堆的特性，需重建堆。个元素不再满足堆的特性，需重建堆。 c. c. 在在b.b.之后，新的堆顶之后，新的堆顶( (根结点根结点) )的左、右子树均为堆，的左、右子树均为堆，则仅需则仅需自上至下进行调整自上至下进行调整即可。即可。 这个自堆顶至叶子的调整过程为这个自堆顶至叶子的调整过程为“筛选筛选”。 将一个无序序列建堆的过程就是一个反复将一个无序序列建堆的过程就是一个

44、反复“筛选筛选”的的过程。过程。例例3 310.4 10.4 选选择择排排序序 二、堆排序二、堆排序例例3 3：对于一个无序序列对于一个无序序列4949，3838，6565，9797，7676，1313，2727，4949 进行堆排序。进行堆排序。 1)1)先建一个完全二叉树，先建一个完全二叉树，如图所示：如图所示： 2)2)进行反复的进行反复的“筛选筛选”。从最后一个非终端结点从最后一个非终端结点( (第第 n/2n/2 个元素个元素) )开始开始，将此结点与其左、右孩子比较，选出，将此结点与其左、右孩子比较，选出大的或小的作为此结点；依次对其前的非终端结点重复进大的或小的作为此结点；依次对

45、其前的非终端结点重复进行行“筛选筛选”操作。直到第操作。直到第1 1个元素个元素 ( (根结点根结点) )为最大或最小为最大或最小为止，堆建成。为止，堆建成。 10.4 10.4 选选择择排排序序 二、堆排序二、堆排序3)3)根结点就是排序的最大关键字或最小关键字，根结点就是排序的最大关键字或最小关键字，输出根结输出根结点，即将点，即将1313和和9797交换交换，再重复进行，再重复进行(2)(2)操作，直到整个序列操作，直到整个序列有序。有序。10.4 10.4 选选择择排排序序 二、堆排序二、堆排序 产生的是一个递减序列：产生的是一个递减序列：9797，7676，6565，4949，494

46、9，3838，2727，1313。 10.4 10.4 选选择择排排序序 二、堆排序二、堆排序作为小顶堆，产生的是一个递减序列。作为小顶堆，产生的是一个递减序列。作为大顶堆，产生的是一个递增序列。作为大顶堆，产生的是一个递增序列。(4)(4)算法描述算法描述typedef SqList HeapType;typedef SqList HeapType;void HeapAdjust(HeapType &H,int s,int m)void HeapAdjust(HeapType &H,int s,int m)rc=H.rs;rc=H.rs; for(j=2 for(j=2* *s;j=m;js

47、;j=m;j* *=2) =2) /沿沿keykey较小的孩子结点向下筛选较小的孩子结点向下筛选 if(jm&if(j0;-i) for(i=H.length/2;i0;-i) HeapAdjust(H,i,H.length); HeapAdjust(H,i,H.length); /建小顶堆建小顶堆 for(i=H.length;i1;-i) for(i=H.length;i1;-i) H.r1H.ri; H.r1H.ri; /堆顶记录和最后一个记录相互交换堆顶记录和最后一个记录相互交换 HeapAdjust(H,1,i-1); HeapAdjust(H,1,i-1); /调整小顶堆，自上而下

48、调整小顶堆，自上而下 (5)(5)算法分析算法分析a.a.堆排序是堆排序是的排序。的排序。b.b.时间复杂度为时间复杂度为O(nlogO(nlog2 2n)n)。c.c.空间复杂度为空间复杂度为O(1)O(1)。10.4 10.4 选选择择排排序序 二、堆排序二、堆排序 10.5 10.5 归并排序归并排序一、一、2-2-路归并排序思想路归并排序思想二、二、2-2-路归并排序的方法路归并排序的方法三、三、2-2-路归并步骤路归并步骤四、算法描述四、算法描述 10.5 10.5 归并排序归并排序1 1归并的含义将两个或两个以上的有序序列合并成一个有归并的含义将两个或两个以上的有序序列合并成一个有

49、序序列。序序列。2 2归并排序就是利用归并思想实现的排序，把多个有序表归并排序就是利用归并思想实现的排序，把多个有序表经过若干次归并，最终合并成一个有序表。经过若干次归并，最终合并成一个有序表。3. 3. 对两个有序序列进行归并，称为对两个有序序列进行归并，称为2-2-路归并。路归并。 10.5 10.5 归归并并排排序序一、一、2-2-路归并排序思想路归并排序思想 把一个有把一个有n n个元素的无序表的每一个元素都看成一个元素的无序表的每一个元素都看成一个有序表，个有序表，将两个有序子表（有序表）合并成一个有将两个有序子表（有序表）合并成一个有序子表，一次合并完成后，有序子区间的数目减少一序

50、子表，一次合并完成后，有序子区间的数目减少一半，而子表的长度增加一倍，当子表长度从半，而子表的长度增加一倍，当子表长度从1 1增加到增加到n n（元素个数）时，整个子表变为一个，则该子表中的（元素个数）时，整个子表变为一个，则该子表中的有序序列即为我们所需的排序结果。有序序列即为我们所需的排序结果。 (1)(1)将将n n个记录看成是个记录看成是n n个长度为个长度为1 1的有序子表；的有序子表；(2)(2) 将两两相邻的有序子表将两两相邻的有序子表n n进行归并，若进行归并，若n n为奇数，为奇数，则留下的一个子表直接进入下一次归并；则留下的一个子表直接进入下一次归并；(3)(3)重复步骤重

51、复步骤(2)(2)，直到归并成一个长度为，直到归并成一个长度为n n的有序表。的有序表。 10.5 10.5 归归并并排排序序一、一、2-2-路归并排序思想路归并排序思想 例例4 4 给定排序码给定排序码4646，5555，1313，4242，9494，0505，1717，7070，二路归并排序过程如图所示。二路归并排序过程如图所示。 10.5 10.5 归归并并排排序序二、二、2-2-路归并排序方法路归并排序方法 假设两个子表为假设两个子表为R1R1和和R2R2，这两个子表将被归并为，这两个子表将被归并为T T。归。归并过程为：并过程为： 首先把两个子表为首先把两个子表为R1R1和和R2R2

52、的第一个元素取出来进行比较；的第一个元素取出来进行比较；(1)(1) 将较小的元素放入将较小的元素放入T T；(2)(2) 取较小元素所在的子表的下一个元素与上一步较大的取较小元素所在的子表的下一个元素与上一步较大的元素比较；元素比较；(3)(3) 重复重复(1)(1)、(2)(2)，直到一个子表中的元素取完为止；，直到一个子表中的元素取完为止；(4)(4) 把还剩有元素的子表中的元素取出，依次放入把还剩有元素的子表中的元素取出，依次放入T T。 10.5 10.5 归归并并排排序序三、三、2-2-路归并排序的步骤路归并排序的步骤1 12-2-路归并算法路归并算法 将有序的将有序的SRi.mS

53、Ri.m和和SRm+1.nSRm+1.n归并为有序序列归并为有序序列TRi.nTRi.n。void Merge(RcdType SR,RcdType &TR,int i,int void Merge(RcdType SR,RcdType &TR,int i,int m,int n)m,int n) for(j=m+1,k=i;i=m&j=n;+k) for(j=m+1,k=i;i=m&j=n;+k) if LQ(SRi.key,SRj.key) TRk=SRi+; if LQ(SRi.key,SRj.key) TRk=SRi+; else TRk=SRj+; else TRk=SRj+; if

54、(i=m) TRk.n=SRi.m; if(i=m) TRk.n=SRi.m; if(j=n) TRk.n=SRj.n if(j=n) TRk.n=SRj.n 10.5 10.5 归归并并排排序序四、算法描述四、算法描述2.2.一趟归并排序一趟归并排序 上述算法是将相邻两个有序序列上述算法是将相邻两个有序序列2-2-路归并。而一趟归路归并。而一趟归并排序则调用并排序则调用mergemerge n/2hn/2h 次，将前后相邻且长度为次，将前后相邻且长度为h h的有的有序段进行两两归并，得到前后相邻、长度为序段进行两两归并，得到前后相邻、长度为2h2h的有序段。的有序段。3 3归并排序归并排序

55、整个归并排序就是调用整个归并排序就是调用“一趟归并一趟归并”过程若干次的过过程若干次的过程。第一趟归并时，有序子表长度为程。第一趟归并时，有序子表长度为1 1，每趟归并后有序，每趟归并后有序子表的长度为上一次长度的子表的长度为上一次长度的2 2倍，当有序子表的长度为倍，当有序子表的长度为n n时，时，2-2-路归并排序结束。路归并排序结束。 见图见图10.1310.13 10.5 10.5 归归并并排排序序四、算法描述四、算法描述递归算法：递归算法：void Msort(RcdType SR,RcdType &TR1,int s,int t)void Msort(RcdType SR,RcdT

56、ype &TR1,int s,int t) if(s= =t) TR1s=SRs; if(s= =t) TR1s=SRs; else else m=(s+t)/2; m=(s+t)/2; MSort(SR,TR2,s,m); MSort(SR,TR2,s,m); MSort(SR,TR2,m+1,t); MSort(SR,TR2,m+1,t); Merge(TR2,TR1,s,m,t); Merge(TR2,TR1,s,m,t); void MergeSort(SqList &L)void MergeSort(SqList &L) Msort(L.r,L.r,L.length); Msort(

57、L.r,L.r,L.length); 10.5 10.5 归归并并排排序序四、算法描述四、算法描述 二路归并排序的时间复杂度等于归并趟数与每一趟时二路归并排序的时间复杂度等于归并趟数与每一趟时间复杂度的乘积。而间复杂度的乘积。而归并趟数为归并趟数为 loglog2 2n n ( (当当 loglog2 2n n 为奇数为奇数时，则为时，则为 loglog2 2n n +1) +1)。因为每一趟归并就是将两两有序子。因为每一趟归并就是将两两有序子表合并成一个有序子表，而每一对有序子表归并时，记录表合并成一个有序子表，而每一对有序子表归并时，记录的比较次数均小于等于记录的移动次数（即由一个数组复的

58、比较次数均小于等于记录的移动次数（即由一个数组复制到另一个数组中的记录个数），而记录的移动次数等于制到另一个数组中的记录个数），而记录的移动次数等于这一对有序表的长度之和，所以，这一对有序表的长度之和，所以，每一趟归并的移动次数每一趟归并的移动次数均等于数组中记录的个数均等于数组中记录的个数n n，即每一趟归并的时间复杂度为，即每一趟归并的时间复杂度为O(n)O(n)。因此，。因此，二路归并排序的时间复杂度为二路归并排序的时间复杂度为O(nlogO(nlog2 2n)n)。 利用二路归并排序时，需要利用二路归并排序时，需要利用与待排序数组相同的利用与待排序数组相同的辅助数组作临时单元辅助数组作

59、临时单元，故该排序方法的，故该排序方法的空间复杂度为空间复杂度为O(n)O(n)，比前面介绍的其它排序方法占用的空间大。比前面介绍的其它排序方法占用的空间大。 10.5 10.5 归归并并排排序序五、算法分析五、算法分析 1 1稳定性稳定性 归并排序是归并排序是排序方法。排序方法。 2 2时间复杂度时间复杂度 为为O(nlogO(nlog2 2n)n)。 3 3空间复杂度空间复杂度 为为O(n)O(n)。 10.5 10.5 归归并并排排序序五、算法分析五、算法分析 10.6 10.6 基数排序基数排序一、多关键字的排序一、多关键字的排序二、链式基数排序二、链式基数排序 10.6 10.6 基

60、数排序基数排序 1. 1.基数排序不用进行记录关键字的比较和交换，基数排序不用进行记录关键字的比较和交换， 而是而是利用关键字的结构利用关键字的结构，通过，通过“分类分类”和和“收集收集”的办的办法法实现排序。实现排序。 2.2.基数排序将基数排序将多关键字排序的思想多关键字排序的思想用于单逻辑关键字用于单逻辑关键字的排的排序中。序中。 10.6 10.6 基基数数排排序序一、多关键字的排序一、多关键字的排序1 1多关键字排序思想多关键字排序思想 以扑克牌排序为例，讨论多关键字排序思想。以扑克牌排序为例，讨论多关键字排序思想。 任何一张扑克牌都有花色和面值两种属性，以花色任何一张扑克牌都有花色