算法ppt课件--第9章(内排序).ppt

《算法ppt课件--第9章(内排序).ppt》由会员分享，可在线阅读，更多相关《算法ppt课件--第9章(内排序).ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、North China Electric Power University第九章第九章 内排序内排序 基本概念基本概念 插入排序插入排序 冒泡排序冒泡排序 选择排序选择排序 计数排序计数排序 希尔排序希尔排序 堆排序堆排序 快速排序快速排序 合并排序合并排序 基数排序基数排序North China Electric Power University 设含有设含有n n个记录的文件个记录的文件RR1 1, R, R2 2, , ，R Rn n , , 其相其相应的关键字为应的关键字为KK1 1, K, K2 2, , ，K Kn n ，需确定一种排列，需确定一种排列P(1),P(2),P(1),

2、P(2),P(n),P(n),使其相应的关键字满足如下的递使其相应的关键字满足如下的递增增( (或递减或递减) )关系：关系：K KP(1)P(1) K KP(2)P(2) K KP(3)P(3) K KP(n)P(n)即，使上述文件成为一个按其关键字线性有序的即，使上述文件成为一个按其关键字线性有序的文件文件RRP(1)P(1) , R , RP(2)P(2) , , ，R RP(n)P(n) , ,这样一种运算称为这样一种运算称为排序。排序。9.1 9.1 基本概念基本概念 如果在排序期间具有相同关键字的记录的如果在排序期间具有相同关键字的记录的相对位置不变，则称此方法是相对位置不变，则称

3、此方法是稳定的稳定的。排序：排序：排序的稳定性：排序的稳定性：North China Electric Power University即，即，1) 1) K K(i)(i) K K (i+1) (i+1) (1 (1 i n-1)i n-1) 2) 2)若在输入文件中若在输入文件中ij,ij,且且K Ki i =K =K j j , ,则在经过排序后则在经过排序后 的文件中仍的文件中仍R Ri i先于先于R Rj j排序排序内排序：整个排序过程都在内存进行的排序。内排序：整个排序过程都在内存进行的排序。外排序：当文件很大以至于内存不足以存放全部记录，外排序：当文件很大以至于内存不足以存放全部

4、记录，在排序过程中需要对外存进行存取访问。在排序过程中需要对外存进行存取访问。 例如：例如：将下列关键字序列将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 7552, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 9714, 23, 36, 49, 52, 58, 61 ,75, 80, 97North China Electric Power University内部排序的方法内部排序的方法 在排序的过程中，参与排序的记录序列中存在两在排序的

5、过程中，参与排序的记录序列中存在两个区域：有序区和无序区。个区域：有序区和无序区。 内部排序的过程是一个逐步扩大记录的有序序列内部排序的过程是一个逐步扩大记录的有序序列长度的过程。长度的过程。 使有序区中记录的数目增加一个或几个的操作称为使有序区中记录的数目增加一个或几个的操作称为一趟一趟排序。排序。存放待排序数据的数据结构：存放待排序数据的数据结构：typedef struct int key; datatype otheritem; /其他域其他域 records;typedef struct records Listn+1;North China Electric Power Unive

6、rsity逐步扩大记录有序序列长度的方法大致有下列几类：逐步扩大记录有序序列长度的方法大致有下列几类：1.1.插入类插入类 : :将无序子序列中的一个或几个记录将无序子序列中的一个或几个记录“插入插入”到有序到有序序列中，从而增加记录的有序子序列的长度；序列中，从而增加记录的有序子序列的长度；2.2.交换类交换类 : :通过通过“交换交换”无序序列中的记录从而得到其中关键无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；增加记录的有序子序列的长度；3.3.选择类选择类 : :从

7、记录的无序子序列中从记录的无序子序列中“选择选择”关键字最小或最关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；的有序子序列的长度；4.4.归并类归并类 : :通过通过“归并归并”两个或两个以上的记录有序子序列，两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度；逐步增加记录有序序列的长度；5.5.其它方法。其它方法。North China Electric Power University内内 排排 序序插入类排序插入类排序直接插入排序直接插入排序折半插入排序折半插入排序希尔排序希尔排序交换类排

8、序交换类排序冒泡排序冒泡排序快速排序快速排序选择类排序选择类排序选择排序选择排序堆排序堆排序归并类排序归并类排序归并排序归并排序其他排序其他排序计数排序计数排序基数排序基数排序North China Electric Power University9.2 9.2 计数排序计数排序对每个记录计算文件中有多少个其它记录的关键字大于对每个记录计算文件中有多少个其它记录的关键字大于该记录的关键字值，从而找到该记录的正确排序位置。该记录的关键字值，从而找到该记录的正确排序位置。key info count设一个记录有三个域：设一个记录有三个域：关键字域关键字域该记录的其他信息域该记录的其他信息域计数域

9、计数域排序算法的思想：排序算法的思想：North China Electric Power University for(i=1;in;i+) for(j=i+1;j=n;j+) if (Ri.key)Rj.key) Ri.count= Ri.count+1; else Rj.count=Rj.count+1;void countsort(List R, int n) for(i=1;i=n;i+) Ri.count=1; /对所有元素的对所有元素的countcount域置域置1 1； 算法如下：算法如下：North China Electric Power University设文件有设文件

10、有n n个记录，则外循环：个记录，则外循环：i=1i=1时，内循环要做时，内循环要做n-1n-1次比较；次比较；i=2i=2时，内循环要做时，内循环要做n-2n-2次比较；次比较；i=n-1i=n-1时，内循环要做时，内循环要做1 1次比较；次比较；总的比较次数为总的比较次数为(n-1)+(n-2)+(n-1)+(n-2)+1=n(n-1)/2+1=n(n-1)/2算法性能分析：算法性能分析： 所以，算法所需时间为所以，算法所需时间为O(nO(n2 2) )，由于不需要记录移，由于不需要记录移动和额外空间，同时算法简单，当动和额外空间，同时算法简单，当n n较小时，可采用较小时，可采用本算法。

11、本算法。North China Electric Power University例例 关键字序列关键字序列4646，5555，1313，4242，4444，1717，0505，7070关键字关键字46465555131342424444171705057070初始化初始化1 11 11 11 11 11 11 11 1i=1i=13 31 12 22 22 22 22 21 1i=2i=23 32 23 33 33 33 33 31 1i=3i=33 32 27 73 33 33 34 41 1i=4i=43 32 27 75 53 34 45 51 1i=5i=53 32 27 75 54

12、 45 56 61 1i=6i=63 32 27 75 54 46 67 71 1i=7i=73 32 27 75 54 46 68 81 1North China Electric Power University9.3 9.3 直接插入排序直接插入排序假设在排序过程中，记录序列假设在排序过程中，记录序列R1.nR1.n的状态为：的状态为： 则一趟插入排序的基本思想为：将记录则一趟插入排序的基本思想为：将记录RiRi插入到有插入到有序子序列序子序列R1.i-1R1.i-1中，使记录的有序序列从中，使记录的有序序列从R1.i-R1.i-11变为变为R1.iR1.i。显然，完成这个显然，完成这个

13、“插入插入”需分三步进行：需分三步进行：1 1查找查找RiRi的插入位置的插入位置j+1j+1；2 2将将Rj+1.i-1Rj+1.i-1中的记录后移一个位置；中的记录后移一个位置；3 3将将RiRi复制到复制到Rj+1Rj+1的位置上。的位置上。North China Electric Power University直接插入排序直接插入排序：利用顺序查找实现利用顺序查找实现“在在R1.i-1R1.i-1中中查找查找RiRi的插入位置的插入位置”的插入排序。的插入排序。注意直接插入排序算法的三个要点：注意直接插入排序算法的三个要点： 1. 从从Ri-1起向前进行顺序查找，监视哨设置在起向前进

14、行顺序查找，监视哨设置在R0； R0= Ri； 设置设置“哨兵哨兵” j=i-1; while(R0.keyRj.key) j=j-1; / 从后往前找从后往前找 Return(j+1); 返回返回Ri的插入位置为的插入位置为j+12. 对于在查找过程中找到的那些关键字不小于对于在查找过程中找到的那些关键字不小于Ri.key的记的记 录，并在查找的同时实现记录向后移动；录，并在查找的同时实现记录向后移动； while(R0.keyRj.key) Rj+1=Rj; j=j-1;3. i = 2，3，, n, 实现整个序列的排序。实现整个序列的排序。North China Electric Pow

15、er University排序算法如下：排序算法如下：void insort(List r, int n)/r为给定的表，其记录为为给定的表，其记录为ri，i=0，1，n，x为暂存单元。为暂存单元。 for (i=2; i=n; i+) r0=ri; /r0作为标志位作为标志位 j=i-1; while (r0.keyrj.key) rj+1=rj; j-; /j从从i-1至至0，rj.key与与ri.key进行比较进行比较 rj+1=r0; /insortNorth China Electric Power University排序的时间分析：排序的时间分析： 实现排序的基本操作有两个：实现

16、排序的基本操作有两个：（1 1）“比较比较”序列中两个关键字的大小；序列中两个关键字的大小；（2 2）“移动移动”记录。记录。对于直接插入排序：对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：最好的情况（关键字在记录序列中顺序有序）：最坏的情况（关键字在记录序列中逆序有序）：最坏的情况（关键字在记录序列中逆序有序）：“比较比较”的次数：的次数：“移动移动”的次数：的次数： 总的说来，直接插入排序所需进行关键字间的比较次数和记录移总的说来，直接插入排序所需进行关键字间的比较次数和记录移动的次数均为动的次数均为n n2 2/4/4，所以直接插入排序的时间复杂度为，所以直接插入排序的时间

17、复杂度为O(nO(n2 2) )。“比较比较”的次数：的次数：“移动移动”的次数：的次数： 2(n-1)North China Electric Power University9.4 9.4 折半插入排序折半插入排序 排序算法的思想：排序算法的思想：由于直接插入排序的内循由于直接插入排序的内循环环( (从从1 1到到i-1)i-1)的查找的查找( (或说是比较或说是比较) )是在是在( (部分部分) )有有序表的环境下进行的，所以内循环用序表的环境下进行的，所以内循环用“折半查找折半查找法法”，比用顺序查找法快。，比用顺序查找法快。North China Electric Power Uni

18、versity算法描述如下：算法描述如下：void binsort(List r, int n) for(i=2;i=n;i+) r0=ri;low=1; high=i-1; while(low=high) m=(low+high)/2; if r0.keyrm.key high=m-1; else low=m+1; for (j=i-1;j=low;j-) rj+1=rj;/把从第把从第low起到第起到第i-1各记录后移各记录后移 rlow=r0;/将第将第i个记录插入个记录插入 /binsort North China Electric Power University9.5 9.5 冒泡

19、排序冒泡排序排序算法的思想：排序算法的思想：比较比较k k1 1和和k k2 2, , 如果这些关键字的值不符合排序顺如果这些关键字的值不符合排序顺序序, , 就交换就交换k k1 1和和k k2 2；然后对记录；然后对记录k k2 2和和k k3 3, k, k3 3和和k k4 4等等进行相同的工等等进行相同的工作。直到作。直到k kn-1n-1和和k kn n为止为止, , 到此得到一个最大到此得到一个最大( (或最小或最小) )关键字值存在关键字值存在k kn n的位置上的位置上( (通常将通常将此过程叫做一趟此过程叫做一趟) )。重复这个过程。重复这个过程, ,就得到在位就得到在位置

20、置k kn-1n-1,k,kn-2n-2等处的适当记录等处的适当记录, , 使得所有记录最终被排好序。使得所有记录最终被排好序。 例如例如: :将将5 5个记录的关键字个记录的关键字7,4,8,3,97,4,8,3,9进行冒泡排序。排序后进行冒泡排序。排序后k1k2k1k2knkn (n=5) (n=5)。7 4 4 3 34 7 3 4 4 8 3 7 7 73 8 8 8 89 9 9 9 9 因为到第四趟就没有交因为到第四趟就没有交换的偶对了换的偶对了, ,所以整个排序所以整个排序结束。结束。North China Electric Power University算法描述如下算法描述如

21、下:void bubblesort(List r,int n) for (m=1;m=n;m+) scanf(“%d”,rm); k=n; do all=T; /all=T,标志没有交换的标志没有交换的 ;all= F,标志有交换的标志有交换的 for (m=1;mri) max=rm; rm=ri; ri=max; all=F; k-; while(all=F)&(k!=1)冒泡排序的结束条件为：最后一趟没有进行冒泡排序的结束条件为：最后一趟没有进行“交换交换”。冒泡排序是一种冒泡排序是一种稳定的稳定的排序算法。排序算法。North China Electric Power Universi

22、ty时间分析时间分析: :最好的情况（关键字在记录序列中顺序有序）：只需进行最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡一趟起泡“比较比较”的次数：的次数：“移动移动”的次数：的次数：n-10 最坏的情况（关键字在记录序列中逆序有序）：需进行最坏的情况（关键字在记录序列中逆序有序）：需进行 n-1n-1趟起泡趟起泡“比较比较”的次数：的次数： “移动移动”的次数：的次数： North China Electric Power University9.6 9.6 希尔排序希尔排序 基本思想：基本思想：对待排序记录序列先作对待排序记录序列先作“宏观宏观”调整，调整，再作再作“微观微观

23、”调整。所谓调整。所谓“宏观宏观”调整，指的是，调整，指的是，“跳跳跃式跃式”的插入排序。即：将记录序列分成若干子序列，的插入排序。即：将记录序列分成若干子序列，每个子序列分别进行插入排序每个子序列分别进行插入排序, ,待整个序列中的记录待整个序列中的记录“基本有序基本有序”时，再对全体记录进行一次直接插入排序。时，再对全体记录进行一次直接插入排序。假设将假设将n n个记录分成个记录分成d d个子序列，则这个子序列，则这d d个子序列分别为：个子序列分别为： R1 R1，R1+dR1+d，R1+2dR1+2d，R1+kd R1+kd R2 R2，R2+dR2+d，R2+2dR2+2d，R2+k

24、d R2+kd Rd Rd，R2dR2d，R3dR3d，RkdRkd ，R(k+1)d R(k+1)d 其中，其中，d d称为增量，它的值在排序过程中从大到小逐渐缩小，称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为直至最后一趟排序减为1 1。North China Electric Power University例如：例如：第二趟希尔排序，设增量d = 3第三趟希尔排序，设增量d = 1North China Electric Power University希尔排序的算法描述如下希尔排序的算法描述如下:void ShellInsert (List r,int d) /本

25、算法对直接插入算法作了以下修改：本算法对直接插入算法作了以下修改：/ 1. 前后记录位置的增量是前后记录位置的增量是d，而不是，而不是1；/ 2. r0只是暂存单元，不是哨兵。当只是暂存单元，不是哨兵。当j=0时，插入位置已找到。时，插入位置已找到。 for(i=d+1;i=n;i+) if ( ri 0) and (r0 rj) rj+d = rj; /记录后移，查找插入位置记录后移，查找插入位置 j=j-d; rj+d = r0;/插入插入 for (i=2;i= n ; i+) r0=ri; j=i-1; while ( r0.keyrj.key) rj+1=rj; j=j-1; rj+

26、1=r0; North China Electric Power UniversityVoid Shell_sort (List r, int dlta, int t); /按增量序列按增量序列dlta0.t-1对顺序表对顺序表r作希尔排序作希尔排序 for(k=0;k=t;k+) ShellInsert(r, dltak); North China Electric Power University 先取定一个两项之间的距离先取定一个两项之间的距离d d1 1(n,(n,其中其中n n为整个为整个表的长度表的长度),),反复比较每两个相距反复比较每两个相距d d1 1的项的项, ,直到以直到

27、以d d1 1为距为距离划分的组排序好为止离划分的组排序好为止( (至此一趟排序完成至此一趟排序完成);); 然后取然后取d d2 2dd1 1, ,再继续以再继续以d d2 2为距离反复比较每两个为距离反复比较每两个相距为相距为d d2 2的项的项, , ,依此类推依此类推. .取每个取每个d di+1i+1 d di i, ,直到直到d dt t=1=1为止。为止。例如例如, ,假设文件中假设文件中8 8个记录的关键字个记录的关键字, ,我们不采用顺序比较我们不采用顺序比较, ,而是而是先从第一个关键字开始每隔先从第一个关键字开始每隔4 4个关键字进行比较个关键字进行比较; ;同理第二个也

28、同理第二个也从隔从隔4 4个关键字进行比较个关键字进行比较, ,第三个第三个, ,第四个第四个, ,依次做下去依次做下去. .题题中选中选d1=4,d1=4,从小到大排序从小到大排序: :例例North China Electric Power University初始初始d1=446 55 13 42 94 17 05 70 55与与1713与与05第一趟后结果第一趟后结果46 17 05 42 94 55 13 70 46与与0594与与1346与与13第二趟后结果第二趟后结果d2=205 17 13 42 46 55 94 70 13,4613,46分分别交换两别交换两次次 05 13

29、17 42 46 55 70 94 第三趟后结果第三趟后结果d3=11313与与17179494与与7070North China Electric Power UniversityNorth China Electric Power University9.7 9.7 选择排序选择排序 基本思想：基本思想：首先在首先在n n个记录中选择一个具有最小或个记录中选择一个具有最小或最大关键字的记录，将选出的记录与记录集合中的第一最大关键字的记录，将选出的记录与记录集合中的第一个记录交换位置。然后在个记录交换位置。然后在r2r2至至rnrn中选择一个最小或中选择一个最小或最大的值与最大的值与r2r2

30、交换位置，交换位置，依此类推，直至，依此类推，直至rn-1rn-1和和rnrn比较完毕。比较完毕。void slsort(List r,int n)/每次从每次从rj(j=i+1,n)中选了最小值，与中选了最小值，与ri(i=1,2,n-1)交换，进行分类交换，进行分类 for (i=1;i=n-1;i+) /共进行共进行n-1趟排序趟排序 m=i; for (j=i+1;j=n;j+) if (rj.keyrm.key) m=j; /m指示关键字最小的记录的序号指示关键字最小的记录的序号 if (m!=i) x=ri; ri=rm; rm=x; North China Electric Po

31、wer University例例 关键字序列关键字序列055055，5555，6060，1313，0505，9494，1717，70,70,利利用选择排序算法进行排序。用选择排序算法进行排序。关键字关键字r1r1055055r2r25555r3r36060r4r41313r5r50505r6r69494r7r71717r8r87070i=1,m=5i=1,m=50505555560601313055055949417177070i=2,m=4i=2,m=40505131360605555055055949417177070i=3,m=7i=3,m=70505131317175555055055

32、949460607070i=4,m=4i=4,m=40505131317175555055055949460607070i=5,m=5i=5,m=50505131317175555055055949460607070i=6,m=7i=6,m=70505131317175555055055606094947070i=7,m=8i=7,m=80505131317175555055055606070709494不稳定不稳定North China Electric Power University算法的复杂性分析：算法的复杂性分析：当选则第一个最小值时需进行当选则第一个最小值时需进行n-1n-1次比较

33、，选第二个最次比较，选第二个最小值时需进行小值时需进行n-2n-2次比较，次比较，选，选n-1n-1个最小值时需进个最小值时需进行行n-(n-1)n-(n-1)次比较，次比较，所以总的比较次数为所以总的比较次数为(n-1)+(n-2)+(n-1)+(n-2)+2+1=n(n-1)/2+2+1=n(n-1)/2故排序故排序n n个记录需要时间为个记录需要时间为O(nO(n2 2) )。由于执行一次交换，需三次移动记录，最多交换由于执行一次交换，需三次移动记录，最多交换n-1n-1次，次，故最多移动次数为故最多移动次数为3(n-1)3(n-1)North China Electric Power

34、UniversityNorth China Electric Power University9.8 9.8 堆排序堆排序1.定义：定义：堆是由堆是由n个记录的线性序列个记录的线性序列R1, R2, ，Rn; 其关键字其关键字序列序列k1,k2, ，kn,满足下列特性时，称之为堆。满足下列特性时，称之为堆。或或 若将此数列看成是一棵完全二叉树的顺序存储表示，则堆或若将此数列看成是一棵完全二叉树的顺序存储表示，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左、右子树不空时，根结点的值小于并且当左、右子树不空时，根结

35、点的值小于(或大于或大于)左、右子树左、右子树根结点的值。根结点的值。下列两个序列为堆，对应的完全二叉树如下图下列两个序列为堆，对应的完全二叉树如下图96，83，27，38，11，099683273811 091236248547305391kik2ikik2i+1kik2ikik2i+1大根堆大根堆小根堆小根堆12，36，24，85，47，30，53，91North China Electric Power University1) 1) 首先将一个关键字集合用完全二叉树的形式排列首先将一个关键字集合用完全二叉树的形式排列; ; 如给定关键字集合为如给定关键字集合为46,55,13,42,9

36、4,17,05,7046,55,13,42,94,17,05,70组成的完全组成的完全二叉树如下：二叉树如下：4655134294 1705702. 建堆的过程：建堆的过程：North China Electric Power University2) )开始建堆：采用筛选法，逐步将大的关键字筛到堆底。开始建堆：采用筛选法，逐步将大的关键字筛到堆底。筛选法的思想是这样的：筛选法的思想是这样的： 假设集合假设集合r有有m个结点，从某个结点个结点，从某个结点i（第一次第一次 i=m/2 ）开始筛选开始筛选; 先看第先看第i个结点的左右子树，设第个结点的左右子树，设第i个结点的左子树为个结点的左子树

37、为kj ,右子树为右子树为kj+1。若。若kj kj则对调，小的上来大的则对调，小的上来大的下去。下去。 然后然后kj作为新的根结点，再对新的根结点的左右子树进作为新的根结点，再对新的根结点的左右子树进行判断。重复上述过程，直到某个结点的左或右子树根结点的行判断。重复上述过程，直到某个结点的左或右子树根结点的下标大于下标大于m为止。为止。North China Electric Power University第一次调用筛选法：第一次调用筛选法：m=8,i=m/2=4,m=8,i=m/2=4,从从i=4i=4开始，开始，看看k k4 4的左右子树，仅有左子的左右子树，仅有左子树，因此树，因此4

38、242与与7070比较，比较，42704205,1705,故沿右子树故沿右子树比较，比较，1305,1305,进行对调，此进行对调，此时时1313无左右子树，所以返回。无左右子树，所以返回。4655134294 170570North China Electric Power University051346, 55, 13, 42, 94, 17, 05, 7046, 55, 05, 42, 94, 17, 13, 70 先看第先看第i个结点的左右个结点的左右子树，设第子树，设第i个结点的左子树为个结点的左子树为kj ,右子树为右子树为kj+1。若。若kj kj则对调，小的则对调，小的上来大

39、的下去。上来大的下去。 然后然后kj作为新的根结点，作为新的根结点，再对新的根结点的左右子树进再对新的根结点的左右子树进行判断。重复上述过程，直到行判断。重复上述过程，直到某个结点的左或右子树根结点某个结点的左或右子树根结点的下标大于的下标大于m为止。为止。North China Electric Power University第三次调用筛选法：第三次调用筛选法：i=2, i=2, k k2 2=55,=55,因为因为42944294，所以沿左子，所以沿左子树筛选，树筛选，4255,4255,进行对调，此进行对调，此时时5555还有左子树还有左子树7070，因，因55705570，所以不变，

40、再向下所以不变，再向下7070无左右子无左右子树，所以返回，此时二叉树如树，所以返回，此时二叉树如右图所示。右图所示。4655054294 171370第四次调用筛选法：第四次调用筛选法：i=1, ki=1, k1 1=46,=46,因为因为05420542，所以沿右子树筛选，所以沿右子树筛选，0546,0546,进行对调，此时进行对调，此时4646还有左还有左右子树右子树17,1317,13，因，因13171317，所以再，所以再沿右子树筛选，沿右子树筛选，1346,1346,所以对调，所以对调，4646无左右子树，所以返回，此时无左右子树，所以返回，此时二叉树如右图所示。二叉树如右图所示。

41、4642055594 171370North China Electric Power University55424605461346, 42, 05, 55, 94, 17, 13, 7005, 42, 13, 55, 94, 17, 46, 70 先看第先看第i个结点的左右子个结点的左右子树，设第树，设第i个结点的左子树为个结点的左子树为kj ,右子树为右子树为kj+1。若。若kj kj则对调，小的上来则对调，小的上来大的下去。大的下去。 然后然后kj作为新的根结点，作为新的根结点，再对新的根结点的左右子树进再对新的根结点的左右子树进行判断。重复上述过程，直到行判断。重复上述过程，直到某

42、个结点的左或右子树根结点某个结点的左或右子树根结点的下标大于的下标大于m为止。为止。North China Electric Power University3. 建堆的算法建堆的算法void sift(List r, int k, int m)/对对m个结点的集合个结点的集合r从某个结点从某个结点i=k开始筛选，如果开始筛选，如果rjrj+1(j=2i)，则沿右，则沿右/分支筛，否则沿左分支筛。把关键字大的筛到堆底。分支筛，否则沿左分支筛。把关键字大的筛到堆底。 i=k; j=2*i; x=ri; ri=x;/将将x放在适当的位置放在适当的位置/sift North China Electr

43、ic Power University while (j=m) if (jrj+1.key) /左子树左子树右子树右子树 j+; /沿右筛沿右筛 if (x.keyrj.key) ri=rj; i=j; j=2*i; /将关键字小的换到将关键字小的换到i i位置，位置，x.keyx.key再准备与下一层的比较再准备与下一层的比较 else j=m+1; /强制跳出强制跳出while循环循环North China Electric Power University以上面建的堆为例以上面建的堆为例, ,说明重建堆的执行过程。说明重建堆的执行过程。输出输出050570r10542135594 174

44、6707042135594 1746051342175594 7046重建堆重建堆输出输出131346r14642175594 7005重建堆重建堆050570X05,42,13,55,94,17, 46,7013,42,17,55,94,70, 46,05134613704.4.堆排序过程堆排序过程North China Electric Power University131742465594 7005输出输出171770r113704246559405重建堆重建堆1713425546709405输出输出424294r117139455467005重建堆重建堆17,42,46,55,94,

45、70, 13,05X17701742,55,46,70,94,17, 13,0542944270North China Electric Power University42 17134655947005输出输出464670r142 171370559405重建堆重建堆4642 171355709405输出输出555594r14642 1713947005重建堆重建堆46,55,94,70,42,17, 13,05467046X55,70,94,46,42,17, 13,055594557070North China Electric Power University7094554642 17

46、1305输出输出707094r194554642 171305退出退出K K循环循环打印打印94949470554642 17130570,94,55,46,42,17, 13,0570947094,70,55,46,42,17, 13,05North China Electric Power University堆排序的过程：堆排序的过程：用拔尖的方法将堆顶输出用拔尖的方法将堆顶输出, ,把最后一个元把最后一个元素送到树根上素送到树根上, ,然后从然后从i=1i=1开始开始, ,调用筛选算法重新建堆调用筛选算法重新建堆, ,再将堆顶输出将最后一个送到树根再将堆顶输出将最后一个送到树根, ,再

47、重新建堆。如此反再重新建堆。如此反复复, ,直到得到最后全部排序好的关键字序列。直到得到最后全部排序好的关键字序列。算法描述如下：算法描述如下：void heapsort (List r, int n) /对对n个结点的集合个结点的集合r进行堆排序进行堆排序 for (i=n/2; i=1; i-) sift (r, i, n); /从第从第n/2个结点开始进行筛选建初始堆个结点开始进行筛选建初始堆/headsort for (k=n; k=2; k-) t=rk; rk=r1; r1=t; printf(“%d”,rk); sift(r,1,k-1); /重建堆重建堆printf(“%d”,

48、r1); /输出最后一个元素即最大元素输出最后一个元素即最大元素North China Electric Power UniversityNorth China Electric Power University1 1）对深度为）对深度为h h的堆，的堆，“筛选筛选”所需进行的关键字比较的所需进行的关键字比较的次次 数至多为数至多为2(h-1); 2(h-1); 5.5.堆排序的时间复杂度分析堆排序的时间复杂度分析2）对）对n个关键字，建成深度为个关键字，建成深度为 的堆，的堆， 所需进行的关键字比较的次数不超过：所需进行的关键字比较的次数不超过：h=(log2n+1)O(n)4n2j2nj*

49、22*2j*2) ih(2) ih(2*21h1jj1h1jj1h1j1hjh11hii11hi1iNorth China Electric Power University2（ log2(n-1)+ log2(n-2)+log22） 2n( log2n )共共n-2n-2项相加项相加因此，堆排序的时间复杂度为因此，堆排序的时间复杂度为O(nlognO(nlogn) )3）调整）调整“堆顶堆顶”n-1次，总共进行的关键字比较的次数次，总共进行的关键字比较的次数不不 超过：超过：North China Electric Power University例：关键字序列例：关键字序列33，2727，

50、3636，027 027 32736027已为初始堆已为初始堆输出输出3 3027r102727363输出输出027027此时为堆此时为堆36r136273027输出输出272736r1重建堆重建堆2736302736302727退出退出K K循环循环打印打印363636302727输出序列为：输出序列为：3 3，027027，2727，3636不稳定不稳定6.6.堆排序的稳定性分析堆排序的稳定性分析North China Electric Power UniversityNorth China Electric Power University9.9 9.9 快速排序快速排序 快速排序又称快