《数据结构排序》PPT课件.ppt

《《数据结构排序》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构排序》PPT课件.ppt（164页珍藏版）》请在三一办公上搜索。

1、1,第9章 排序,2,目 录,9.1 基本概念,9.2 插入排序,9.3 交换排序,9.5 归并排序,退出,9.4 选择排序,3,91 基本概念,排序:是计算机程序设计中的一项重要操作，其功能是指一个数据元素集合或序列重新排列成一个按数据元素某个数据项值有序的序列。排序码(关键码):排序依据的数据项。稳定排序:排序前与排序后相同关键码元素间的位置关系，保持一致的排序方法。不稳定排序:排序前与排序后相同关键码元素间的相对位置发生改变的排序方法。排序分为两类：（1）内排序:指待排序列完全存放在内存中所进行的排序。内排序大致可分为五类：插入排序、交换排序、选择排序、归并排序和分配排序。本章主要讨论内

2、排序。（2）外排序：指排序过程中还需访问外存储器的排序。为了以后讨论方便，我们直接将排序码写成一个一维数组的形式，并且在没有声明的情形下，所有排序都按排序码的值递增排列。,4,9.2 插入排序,基本思想：每次将一个待排序的元素，按其关键字的大小插入到前面已经排好序的子文件的适当位置，直到全部记录插入完成为止。,9.2.1 直接插入排序 直接插入排序的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有

3、序表。,5,例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。它的直接插入排序的执行过程如下：,直接插入排序举例,6,void D-InsertSort(datatype R,int n)/*待排序的n个元素放在数组R中，用直接插入法进行排序*/for(i=2;i=n;i+)/*i控制第i-1次插入,最多进行n-1次插入*/if(Ri.keyRi-1.key)/*小于时,需将Ri插入有序表*/R0=Ri;/*为统一算法设置监视哨*/for(j=i-1;R0.keyRj.key;j-)Rj+1=Rj;/*元素后移*/Rj+1=R0;/*将放在R0中的第i个元素插入到有序表中

4、*/,直接插入排序算法,7,直接插入排序的效率分析,首先从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。从时间分析，首先外层循环要进行n-1次插入,每次插入最少比较一次(正序),移动0次;最多比较i次(包括同监视哨R0的比较),移动i1次(逆序)(i=2,3,n)。因此，直接插入排序的时间复杂度为O（n2）。直接插入算法的元素移动是顺序的，该方法是稳定的。,8,9.2.2 希尔排序(缩小增量排序),希尔排序的基本思想：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入

5、排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上有较大提高。,9,八个元素的关键码分别为：91，67，35，62，29，72，46，57，希尔排序算法的执行过程为：,希尔排序过程举例,10,希尔排序算法,void ShellSort(datatype R,int d,int t)/*按增量序列d0、d1、d2、dt-1对顺序表R1、R2、Rn作希尔排序，注意d0、d1、d2、dt-1 除1之外不能有公因子，且dt-1必须为1*/for(k=0;k0)/*插入到正确位置*/,11,希尔排序的效率分析,虽然我们给出的算法是三层循环，最外层循环为l

6、og2n数量级，中间的for循环是n数量级的，内循环远远低于n数量级，因为当分组较多时，组内元素较少；此循环次数少；当分组较少时，组内元素增多，但已接近有序，循环次数并不增加。因此，希尔排序的时间复杂性在O（nlog2n）和O（n2）之间，大致为O（n1.3）。由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同排序码元素的原始顺序，因此希尔排序是不稳定的。,12,9.3 交换排序 主要是通过排序表中两个记录关键码的比较，若与排序要求相逆（不符合升序或降序），则将两者交换。,9.3.1 冒泡排序,冒泡排序的基本思想：通过对待排序序列从前向后，依次比较相邻元素的排序码，若发现逆

7、序则交换，使排序码较大的元素逐渐从前部移向后部。因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志swap判断元素是否进行过交换。从而减少不必要的比较。,13,0 1 2 3 4 5 6 7 8,49,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,14,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,97,97,76,76,13,13,27,27,49,49,15,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,97,97,76,7

8、6,13,13,27,27,49,49,16,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,97,97,76,76,13,13,27,27,49,49,17,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,97,97,76,76,13,13,27,27,49,49,18,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,76,97,76,97,13,13,27,27,49,49,19,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,76,97,76,97,13,13,27,27,49,49,20,0

9、 1 2 3 4 5 6 7 8,49,38,49,38,65,65,76,97,76,13,97,13,27,27,49,49,21,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,76,97,76,13,97,13,27,27,49,49,22,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,76,97,76,13,27,13,27,97,49,49,23,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,76,97,76,13,27,13,27,97,49,49,24,0 1 2 3 4 5 6 7 8,49,38,4

10、9,38,65,65,76,97,76,13,27,13,27,49,97,49,25,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,76,13,27,49,97,38,49,65,76,13,27,49,97,26,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,76,13,27,49,97,38,49,65,76,13,27,49,97,27,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,76,13,27,49,97,38,4

11、9,65,76,13,27,49,97,28,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,76,13,27,49,97,38,49,65,76,13,27,49,97,29,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,76,13,27,49,97,38,49,65,13,76,27,49,97,30,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,76,13,27,49,97,38,49,65,13,76,27,49,97,3

12、1,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,76,13,27,49,97,38,49,65,13,27,76,49,97,32,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,76,13,27,49,97,38,49,65,13,27,76,49,97,33,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,76,13,27,49,97,38,49,65,13,27,49,76,97,34,0 1 2 3 4 5 6 7 8,3

13、8,49,65,76,13,27,49,97,38,49,65,13,27,49,76,97,38,49,65,13,27,49,76,97,35,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,13,27,49,76,97,38,49,65,13,27,49,76,97,36,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,13,27,49,76,97,38,49,65,13,27,49,76,97,37,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,9

14、7,38,49,65,13,27,49,76,97,38,49,13,65,27,49,76,97,38,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,13,27,49,76,97,38,49,13,65,27,49,76,97,39,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,13,27,49,76,97,38,49,13,27,65,49,76,97,40,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,13,27,49,7

15、6,97,38,49,13,27,65,49,76,97,41,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,65,13,27,49,76,97,38,49,13,27,49,65,76,97,42,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,13,27,49,65,76,97,38,49,13,27,49,65,76,97,43,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,13,27,49,65,76,97,38,49,13,27,49,6

16、5,76,97,44,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,13,27,49,65,76,97,38,13,49,27,49,65,76,97,45,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,13,27,49,65,76,97,38,13,49,27,49,65,76,97,46,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,49,13,27,49,65,76,97,38,13,27,49,49,65,76,97,47,0 1 2 3 4

17、5 6 7 8,38,49,65,76,13,27,49,97,38,49,13,27,49,65,76,97,38,13,27,49,49,65,76,97,48,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,13,27,49,49,65,76,97,38,13,27,49,49,65,76,97,49,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,13,27,49,49,65,76,97,13,38,27,49,49,65,76,97,50,0 1 2 3 4 5 6 7 8,38,49,65,76,1

18、3,27,49,97,38,13,27,49,49,65,76,97,13,38,27,49,49,65,76,97,51,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,13,27,49,49,65,76,97,13,27,38,49,49,65,76,97,52,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,38,13,27,49,49,65,76,97,13,27,38,49,49,65,76,97,53,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,13,27,38,4

19、9,49,65,76,97,13,27,38,49,49,65,76,97,54,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,13,27,38,49,49,65,76,97,13,27,38,49,49,65,76,97,55,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,13,27,38,49,49,65,76,97,13,27,38,49,49,65,76,97,56,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,13,27,38,49,49,65,76,97,13,27,3

20、8,49,49,65,76,97,57,冒泡排序算法的实现void Bubble-sort(datatype R,int n)int i,j,swap;/*当swap为0则停止排序*/for(i=1;iRj+1.key)/*发生逆序*/R0=Rj;Rj=Rj+1;Rj+1=R0;swap=1;/*交换，并标记发生了交换*/if(swap=0)break;,58,冒泡排序的效率分析 从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n)/2，因此

21、冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法。,59,9.3.2 快速排序(分区交换排序),快速排序（Quick Sorting）是迄今为止所有内排序算法中速度最快的一种。它的基本思想是：任取待排序序列中的某个元素作为标准（也称为支点、界点，一般取第一个元素），通过一次划分，将待排元素分为左右两个子序列，左子序列元素的排序码均小于基准元素的排序码，右子序列的排序码则大于或等于基准元素的排序码，然后分别对两个子序列继续进行划分，直至每一个序列只有一个元素为止。最后得到的序列便是有序序列。

22、,第1趟 27 38 13 49 76 97 65 49,第2趟 13 27 38 49 49 65 76 97,第3趟 13 27 38 49 4965 76 97,最后结果 13 27 38 49 49 65 76 97,假设：49 38 65 97 76 13 27 49,60,一次划分的具体过程,1low指向待划分区域首元素，high指向待划分区域尾元素;2R0=Rlow(为了减少数据的移动,将作为标准的元素暂存 到R0中，最后再放入最终位置);3.high从后往前移动直到Rhigh.key=R0.key;6.Rhigh=Rlow,high-;7.goto 3;8.直到low=high

23、时，Rlow=R0(即将作为标准的元素放到 其最终位置)。概括地说,一次划分就是从表的两端交替地向中间进行扫描,将小的放到左边,大的放到右边,作为标准的元素放到中间。,61,完成一趟排序：(27 38 13)49(76 97 65 50),分别进行快速排序：(13)27(38)49(50 65)76(97),快速排序结束：13 27 38 49 50 65 76 97,27,27,65,65,13,13,97,97,快速排序的排序过程,62,一次划分的具体过程示例,如：将序列 49、38、65、97、76、13、27、49 一次划分的过程为：,一次划分的具体过程为：,1.low指向待划分区域首

24、元素，high指向待划分区 域尾元素;,63,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,一次划分的具体过程示例,如：将序列 49、38、65、97、76、13、27、49 一次划分的过程为：,一次划分的具体过程为：1.low指向待划分区域首元素，high指向待划分区 域尾元素;2.R0=Rlow(为了减少数据的移动,将作为标准 的元素暂存 到R0中,最后再放入最终位置);,64,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,4

25、9,49,界点,一次划分的具体过程示例,如：将序列 49、38、65、97、76、13、27、49 一次划分的过程为：,一次划分的具体过程为：1.low指向待划分区域首元素，high指向待划分区 域尾元素;2.R0=Rlow(为了减少数据的移动,将作为标准 的元素暂存 到R0中,最后再放入最终位置);3.high从后往前移动直到Rhigh.keyR0.key;,65,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,66,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,7

26、6,13,13,27,27,49,49,49,界点,67,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,68,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,69,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,70,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,2

27、7,49,49,49,界点,71,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,概括地说,一次划分就是从表的两端交替地向中间进行扫描,将小的放到左边,大的放到右边,作为标准的元素放到中间。,72,快速排序算法,void Quick_Sort(datatype R,int s,int t)/*对Rs到Rt的元素进行排序*/if(s=R0.key)high-;if(lowhigh)Rlow=Rhigh;low+;while(lowhigh/*返回界点元素所在的位置*/,将表一分为二,对左子序列进行快速排序,对右子

28、序列进行快速排序,在右端扫描,把比界点小的元素放到界点前面,在左端扫描,把比界点大的元素放到界点后面,快速排序的递归树,快速排序的递归过程可用一棵二叉树形象地给出。下图为待排序列49、38、65、97、76、13、27、49 所对应的快速排序递归调用过程的二叉树(简称为快速排序递归树)。,从快速排序算法的递归树可知,快速排序的趟数取决于递归树的高度。,74,快速排序的时间复杂度,如果每次划分对一个对象定位后，该对象的左子序列与右子序列的长度相同,则下 一步将是对两个长度减半的子序列进行排序,这是最理想的情况。假设n是2的幂，n=2k,(k=log2n),假设支点位置位于序列中间，这样 划分的子

29、区间大小基本相等。n+2(n/2)+4(n/4)+.+n(n/n)=n+n+.+n=n*k=n*log2n 因此，快速排序的最好时间复杂度为O（nlog2n）。而且在理论上已经证明，快速排序的平均时间复杂度也为O（nlog2n）。实验结果表明:就平均计算时间而言,快速排序是所有内排序方法中最好的一个。在最坏的情况,即待排序对象序列已经按其排序码从小到大排好序的情况下,其递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列(蜕化为冒泡排序)。必须经过n-1 趟才能把所有对象定位,而且第 i 趟需要经过 n-i 次排序码比较才能找到第 i 个对象的安放位置，总的排序码比较次数将达到,因此

30、，快速排序的最坏时间复杂度为O(n2)。,75,快速排序的空间复杂度及稳定性,快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。最大递归调用层次数与递归树的高度一致。理想情况为 log2(n+1)；最坏情况即待排序对象序列已经按其排序码从小到大排好序的情况下,其递归树成为单支树,深度为n。因此，快速排序最好的空间复杂度为O（log2n）,最坏的空间复杂度为O(n)(即快速排序所需用的辅助空间)。,快速排序是一种不稳定的排序方法。可用3,2,2序列来验证。,76,9.4 选择排序,两种常见的选择排序,简单选择排序堆排序,基本原理:将待排序的元素分为已排序(初始为空)和未排序两组，依次

31、将未排序的元素中值最小的元素放入已排序的组中。,77,9.4.1 简单选择排序,在一组元素Ri到Rn中选择具有最小关键码的元素若它不是这组元素中的第一个元素，则将它与这组元素中的第一个元素对调。除去具有最小关键字的元素，在剩下的元素中重复第(1)、(2)步，直到剩余元素只有一个为止。,简单选择排序的基本过程为：,78,初始状态,第1趟,第2趟,第3趟,第4趟,第5趟,第6趟,第7趟,简单选择排序示例,简单选择排序过程为：(1)在一组元素Ri到Rn中选择具有最小关键码的元素(2)若它不是这组元素中的第一个元素，则将它与这组元素中的第一个元素对调。(3)除去具有最小关键字的元素，在剩下的元素中重复

32、第(1)、(2)步，直到剩余元素只有一个为止。,79,Void Select-Sort(datatype R,int n)/*对R1到Rn的元素进行排序*/for(i=1;in;i+)k=i;for(j=i+1;j=n;j+)if(Rj.keyRk.key)k=j;if(k!=i)R0=Rk;Rk=Ri;Ri=R0;,进行n-1趟排序,简单选择排序算法,80,简单选择排序的效率分析,2.最好情况：序列为正序时，移动次数为0，最坏情况：序列为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。3.由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序

33、方法。例如,给定排序码为3，7，3，2，1，排序后的结果为1，2，3，3，7。,1.无论初始状态如何，在第i 趟排序中选择最小关键码的元素，需做n-i次比较，因此总的比较次数为：,(即时间复杂度),81,选择排序堆排序的引入,堆排序是简单选择排序的改进。用直接选择排序从n个记录中选出关键字值最小的记录要做n-1次比较，然后从其余n-1个记录中选出最小者要作n-2次比较。显然，相邻两趟中某些比较是重复的。为了避免重复比较，可以采用树形选择排序比较。,82,(a)求出最小关键字3(b)求出次小关键字11图 8.8 树形选择排序,83,树形选择排序总的比较次数为O(nlog2 n)，与直接选择排序比

34、较，减少了比较次数，但需要增加额外的存储空间存放中间比较结果和排序结果。,选择排序堆排序的引入,84,堆排序1堆的定义,n个元素的序列 k1，k2，kn，当且仅当满足 kik2i kik2i（1）kik2i+1 或(2)kik2i+1（i=1,2,n/2）称之为堆。,若将此排序码按顺序组成一棵完全二叉树，则（1）称为小顶堆（二叉树的所有结点值小于或等于左右孩子的值），（2）称为大顶堆（二叉树的所有结点值大于或等于左右孩子的值）。,小顶堆和大顶堆示例,86,2堆排序的基本思想,（1）建初始堆 将排序码k1，k2，k3，kn表示成一棵完全二叉树，然后从第n/2 个排序码(即树的最后一个非终端结点)

35、开始筛选，使由该结点作根结点组成的子二叉树符合堆的定义，然后从第n/2-1个排序码重复刚才操作，直到第一个排序码止。这时候，该二叉树符合堆的定义，初始堆已经建立。,（2）堆排序 将堆中第一个结点（二叉树根结点）和最后一个结点的数据进行交换（k1与kn），再将k1kn-1重新建堆，然后k1和kn-1交换，再将k1kn-2重新建堆，然后k1和kn-2交换，如此重复下去，每次重新建堆的元素个数不断减1，直到重新建堆的元素个数仅剩一个为止。这时堆排序已经完成，则排序码k1，k2，k3，kn已排成一个有序序列。,87,堆排序的两大步骤,堆排序过程分为两大步骤:(1)根据初始输入数据形成初始堆;(2)通过

36、一系列的元素交换和重新调整堆进行排序。,88,堆排序的关键问题,堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？,89,堆排序的关键问题,第二个问题解决方法筛选方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。第一个问题解决方法建堆方法：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选。,90,堆排序示例(以大顶堆为例),

37、60 2,40 4,8 3,12 6,root,1 2 3 4 5 6 7,3060 840701210,叶子结点，符合堆的的定义。,建立初始堆(把放在数组里的元素的序列看成是一 棵完全二叉树,对该二叉树进行调整,使之成为堆),91,堆排序示例(以大顶堆为例),60 2,40 4,8 3,12 6,root,1 2 3 4 5 6 7,3060 840701210,叶子结点，符合堆的的定义。,不合堆的定义，需调整。即建立大堆。建立的第一个大堆的堆顶的下标为 n/2,(1)建立初始堆(把放在数组里的元素的序列看成是一 棵完全二叉树,对该二叉树进行调整,使之成为堆),92,60 2,40 4,12

38、 3,8 6,root,1 2 3 4 5 6 7,306012 4070 810,叶子结点，符合堆的的定义。,不合堆的定义，需调整。即建立大堆。建立的第一个大堆的堆顶的下标为 n/2,堆排序示例(以大顶堆为例),(1)建立初始堆(把放在数组里的元素的序列看成是一 棵完全二叉树,对该二叉树进行调整,使之成为堆),93,60 2,40 4,12 3,8 6,root,1 2 3 4 5 6 7,306012 4070 810,不合堆的定义，需调整。建立以R 2 为堆顶的大堆。,堆排序示例(以大顶堆为例),(1)建立初始堆(把放在数组里的元素的序列看成是一 棵完全二叉树,对该二叉树进行调整,使之成

39、为堆),94,70 2,40 4,12 3,8 6,root,1 2 3 4 5 6 7,307012 4060 810,不合堆的定义，需调整。建立以 R 2 为堆顶的大堆。,堆排序示例(以大顶堆为例),(1)建立初始堆(把放在数组里的元素的序列看成是一 棵完全二叉树,对该二叉树进行调整,使之成为堆),95,70 2,40 4,12 3,8 6,root,1 2 3 4 5 6 7,307012 4060 810,不合堆的定义,需调整。建立以R 1 为堆顶的堆。,堆排序示例(以大顶堆为例),(1)建立初始堆(把放在数组里的元素的序列看成是一 棵完全二叉树,对该二叉树进行调整,使之成为堆),96

40、,30 2,40 4,12 3,8 6,root,1 2 3 4 5 6 7,703012 4060 810,不合堆的定义,需调整。建立以R 1 为堆顶的堆。,堆排序示例(以大顶堆为例),(1)建立初始堆(把放在数组里的元素的序列看成是一 棵完全二叉树,对该二叉树进行调整,使之成为堆),97,7060124030 610,1 2 3 4 5 6 7,60 2,40 4,12 3,6 6,root,堆排序示例(以大顶堆为例),(1)建立初始堆(把放在数组里的元素的序列看成是一 棵完全二叉树,对该二叉树进行调整,使之成为堆),98,7060124030 610,60 2,40 4,12 3,6 6

41、,root,1 2 3 4 5 6 7,堆排序示例(以大顶堆为例),(2)堆排序,99,1060124030 670,NO NEED TO CONSIDER AGAIN(就位),1 2 3 4 5 6 7,60 2,40 4,12 3,6 6,root,70 7,堆排序示例(以大顶堆为例),(2)堆排序,100,6040121030 670,1 2 3 4 5 6 7,40 2,10 4,12 3,6 6,root,70 7,堆排序示例(以大顶堆为例),(2)堆排序,101,6040121030 670,1 2 3 4 5 6 7,40 2,10 4,12 3,6 6,root,70 7,堆排

42、序示例(以大顶堆为例),(2)堆排序,102,6401210306070,1 2 3 4 5 6 7,40 2,10 4,12 3,60 6,root,70 7,堆排序示例(以大顶堆为例),(2)堆排序,103,40301210 66070,1 2 3 4 5 6 7,30 2,10 4,12 3,60 6,root,70 7,堆排序示例(以大顶堆为例),(2)堆排序,104,40301210 66070,1 2 3 4 5 6 7,30 2,10 4,12 3,60 6,root,70 7,堆排序示例(以大顶堆为例),(2)堆排序,105,6301210406070,1 2 3 4 5 6

43、7,30 2,10 4,40 5,12 3,60 6,root,70 7,堆排序示例(以大顶堆为例),(2)堆排序,106,301012 6406070,1 2 3 4 5 6 7,10 2,6 4,40 5,12 3,60 6,root,70 7,堆排序示例(以大顶堆为例),(2)堆排序,107,301012 6406070,1 2 3 4 5 6 7,10 2,6 4,40 5,12 3,60 6,root,70 7,堆排序示例(以大顶堆为例),(2)堆排序,108,6101230406070,1 2 3 4 5 6 7,10 2,30 4,40 5,12 3,60 6,root,70 7

44、,堆排序示例(以大顶堆为例),(2)堆排序,109,1210 630406070,1 2 3 4 5 6 7,10 2,30 4,40 5,6 3,60 6,root,70 7,堆排序示例(以大顶堆为例),(2)堆排序,110,1210 630406070,1 2 3 4 5 6 7,10 2,30 4,40 5,6 3,60 6,root,70 7,(2)堆排序,堆排序示例(以大顶堆为例),111,6101230406070,1 2 3 4 5 6 7,10 2,30 4,40 5,12 3,60 6,root,70 7,堆排序示例(以大顶堆为例),(2)堆排序,112,10 6123040

45、6070,1 2 3 4 5 6 7,6 2,30 4,40 5,12 3,60 6,root,70 7,堆排序示例(以大顶堆为例),(2)堆排序,113,10 61230406070,1 2 3 4 5 6 7,6 2,30 4,40 5,12 3,60 6,root,70 7,堆排序示例(以大顶堆为例),(2)堆排序,114,6101230406070,ALL ELEMENTS ARE SORTED,1 2 3 4 5 6 7,10 2,30 4,40 5,12 3,60 6,root,70 7,堆排序示例(以大顶堆为例),(2)堆排序,115,3.堆排序算法(以大顶堆为例),void h

46、eapsort(int x,int n)for(i=n/2;i=1;i-)HeapAdjust(R,i,n);for(i=n;i1;i-)R0=R1;R1=Ri;Ri=R0;HeapAdjust(R,1,i-1);,void HeapAdjust(datatype R,int s,int t)rc=Rs;/*用rc暂存RS*/i=s;j=2*i;while(jRj.key)j=j+1;if(rc.keyRj.key)break;else Ri=Rj;/*j号元素上移*/i=j;j=2*i;Ri=rc;/*将rc中的元素放到Ri中*/,将第1个到第i-1个元素调整成一个堆,寻找结点i的大孩子j,

47、116,HeapAdjust算法的执行过程,算法HeapAdjust的作用是将以第s个结点为根的完全二叉树调整成一个大顶堆,其前提是以第s个结点左、右孩子为根的完全二叉树已经是大顶堆。假定s=1,算法 HeapAdjust 的作用是将以第1个结点为根的完全二叉树调整成一个大顶堆,其前提是以第2、3个结点为根的完全二叉树已经是大顶堆(如下图),其调整过程为：,85,24,47,35,32,12,20,27,30,15,36,16,rc,i,j,s,117,HeapAdjust算法的执行过程,算法HeapAdjust的作用是将以第s个结点为根的完全二叉树调整成一个大顶堆,其前提是以第s个结点左、右

48、孩子为根的完全二叉树已经是大顶堆。假定s=1,算法 HeapAdjust 的作用是将以第1个结点为根的完全二叉树调整成一个大顶堆,其前提是以第2、3个结点为根的完全二叉树已经是大顶堆(如下图),其调整过程为：,j,85,24,47,35,32,12,20,27,30,15,36,16,rc,i,s,118,HeapAdjust算法的执行过程,算法HeapAdjust的作用是将以第s个结点为根的完全二叉树调整成一个大顶堆,其前提是以第s个结点左、右孩子为根的完全二叉树已经是大顶堆。假定s=1,算法 HeapAdjust 的作用是将以第1个结点为根的完全二叉树调整成一个大顶堆,其前提是以第2、3个

49、结点为根的完全二叉树已经是大顶堆(如下图),其调整过程为：,i,85,36,24,47,35,32,12,20,27,30,15,16,rc,i,j,s,119,HeapAdjust算法的执行过程,算法HeapAdjust的作用是将以第s个结点为根的完全二叉树调整成一个大顶堆,其前提是以第s个结点左、右孩子为根的完全二叉树已经是大顶堆。假定s=1,算法 HeapAdjust 的作用是将以第1个结点为根的完全二叉树调整成一个大顶堆,其前提是以第2、3个结点为根的完全二叉树已经是大顶堆(如下图),其调整过程为：,i,85,36,24,47,35,32,12,20,27,15,30,16,rc,s,

50、120,HeapAdjust算法的执行过程,算法HeapAdjust的作用是将以第s个结点为根的完全二叉树调整成一个大顶堆,其前提是以第s个结点左、右孩子为根的完全二叉树已经是大顶堆。假定s=1,算法 HeapAdjust 的作用是将以第1个结点为根的完全二叉树调整成一个大顶堆,其前提是以第2、3个结点为根的完全二叉树已经是大顶堆(如下图),其调整过程为：,i,可见,HeapAdjust的执行过程是先用rc暂存RS,然后以元素的移动代替元素间的直接交换。这样做可大大减少所需执行的语句,提高算法的效率。如直接交换3(5)次需执行9(15)个语句,而采用这种方法仅需执行5(7)个语句。在排序算法中