《数据结构之树和图算法幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构之树和图算法幻灯片.ppt（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第9章 排序数据结构之树和图算法第1页，共70页，编辑于2022年，星期六假设假设 Ki=Kj，且排序前序列中，且排序前序列中 Ri 领先于领先于 Rj；若在排序后的序列中若在排序后的序列中 Ri 仍领先于仍领先于 Rj，则称排序方法是，则称排序方法是稳定的稳定的。若在排序后的序列中若在排序后的序列中 Rj 仍领先于仍领先于 Ri，则称排序方法是，则称排序方法是不稳定的不稳定的。例，序列例，序列 3 15 8 8 6 9若排序后得若排序后得 3 6 8 8 9 15稳定的稳定的若排序后得若排序后得 3 6 8 8 9 15不稳定的不稳定的稳定排序与不稳定排序第2页，共70页，编辑于2022年，
2、星期六内部排序内部排序:指的是待排序记录存放在计算机指的是待排序记录存放在计算机随机存储器随机存储器中进中进行的排序过程。行的排序过程。外部排序外部排序:指的是待排序记录的数量很大，以致内存一次不指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对能容纳全部记录，在排序过程中尚需对外存外存进行访问的排序进行访问的排序过程。过程。内部排序与外部排序第3页，共70页，编辑于2022年，星期六排序的时间复杂性排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进
3、行的比较和移动次数越少，则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。第4页，共70页，编辑于2022年，星期六按照排序过程中所依据的原则的不同可以分类为按照排序过程中所依据的原则的不同可以分类为:插入排序插入排序 交换排序交换排序(快速排序快速排序)选择排序选择排序 归并排序归并排序 基数排序基数排序 二叉排序树排序二叉排序树排序内部排序第5页，共70页，编辑于2022年，星期六思想思想:利用有序表的插入操作进行排序利用有序表的插入操作进行排序有序表的插入有序表的插入:将一个记录插入到已排好序的有序表中，从而得将一个记
4、录插入到已排好序的有序表中，从而得到一个新的有序表。到一个新的有序表。例，序列例，序列 13 27 38 65 76 97 插入插入 4913 27 38 49 65 76 97插入排序直接插入排序第6页，共70页，编辑于2022年，星期六例，序列例，序列 49 38 65 97 76 13 27 初始，初始，S=49 ；38 49 初始，令第初始，令第 1 个元素作为初始有序表；个元素作为初始有序表；依次插入第依次插入第 2,3,k 个元素构造新的有序表；个元素构造新的有序表；直至最后一个元素；直至最后一个元素；38 49 65 38 49 65 97 38 49 65 76 97 13 3
5、8 49 65 76 97 13 27 38 49 65 76 97 直接插入排序算法主要应用直接插入排序算法主要应用比较比较和和移动移动两种操作。两种操作。直接插入排序算法描述第7页，共70页，编辑于2022年，星期六void insertsort(ElemType R,int n)/待排序元素用一个数组R表示，数组有n个元素 for(int i=1;i=0)&(tempRj)Rj+1=Rj;j-;/顺序比较和移动 Rj+1=temp;第8页，共70页，编辑于2022年，星期六直接插入排序的效率分析直接插入排序的效率分析从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。从时间分析，
6、首先外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i2次（逆序）（i=1，2，n-1）。Cmin=n-1 M min=2（n-1）Cmax=1+2+n-1=（n2-n）/2 M max=3+4+n+1=（n2+3n-4）/2Cave=（n2+n-2）/4 M max=（n2+7n-8）/4因此，直接插入排序的时间复杂度为O（n2）。直接插入算法的元素移动是顺序的，该方法是稳定的。第9页，共70页，编辑于2022年，星期六由于直接插入排序算法利用了有序表的插入操作，故由于直接插入排序算法利用了有序表的插入操作，故顺序查顺序查找找操作可以替换为操作可以替换为
7、折半查找折半查找操作。操作。例，序列例，序列 49 38 65 97 76 13 27 设已形成有序表设已形成有序表 38 49 65 97 76 插入元素插入元素 13折半插入排序第10页，共70页，编辑于2022年，星期六算法:void BinaryInsertSort(ElemType R,int n)for(int i=1;in;i+)/共进行n-1次插入 int left=0,right=i-1;ElemType temp=Ri;while(left=right)int middle=(left+right)/2;/取中点 if(temp=left;j-)Rj+1=Rj;/元素后移空
8、出插入位 Rleft=temp;第11页，共70页，编辑于2022年，星期六折半插入效率分析二分插入算法与直接插入算法相比，需要辅助空间与直接插入排序基本一致；时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏，两种方法的元素的移动次数相同，因此二分插入排序的时间复杂度仍为O(n2)。二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。第12页，共70页，编辑于2022年，星期六分析直接插入排序分析直接插入排序1.若待排序记录序列按关键字若待排序记录序列按关键字基本有序基本有序，则排序效率可大，则排序效率可大大提高；大提高；2.待排序记录总数越少，排序效率越高；
9、待排序记录总数越少，排序效率越高；希尔(shell)排序第13页，共70页，编辑于2022年，星期六思想思想:先将待排序记录序列分割成为若干子序列分别进行直接插入排序；先将待排序记录序列分割成为若干子序列分别进行直接插入排序；待整个序列中的记录基本有序后，再全体进行一次直接插入排序。待整个序列中的记录基本有序后，再全体进行一次直接插入排序。例，序列例，序列 49 38 65 97 76 13 27 48 55 4 19 第一趟排序第一趟排序49 13 1938 2765 4897 5576 413 19 4927 3848 6555 974 76第14页，共70页，编辑于2022年，星期六第二
10、趟排序第二趟排序13 19 4927 3848 6555 974 7613 55 38 7627 4 65 4948 19 9713 38 55 764 27 49 6519 48 97第三趟排序第三趟排序4 13 19 27 38 48 49 55 65 76 97第15页，共70页，编辑于2022年，星期六希尔排序的算法希尔排序的算法希尔排序的算法希尔排序的算法template void ShellSort(T Vector,int arrSize )T temp;int gap=arrSize/2;/gap是子序列间隔 while(gap!=0)/循环,直到gap为零 for(int i
11、=gap;i=gap;j-=gap)if(temp Vectorj-gap)Vectorj=Vectorj-gap;else break;Vectorj=temp;gap=(int)(gap/2);第16页，共70页，编辑于2022年，星期六希尔排序效率分析希尔排序的时间复杂性在O（nlog2n）和O（n2）之间，大致为O（n1.3）。第17页，共70页，编辑于2022年，星期六思想思想:通过不断比较相邻元素大小，进行交换来实现排序。通过不断比较相邻元素大小，进行交换来实现排序。首先将第一个元素与第二个元素比较大小，若为逆序，则交换；首先将第一个元素与第二个元素比较大小，若为逆序，则交换；然后
12、比较第二个元素与第三个元素的大小，若为逆序，则交换；然后比较第二个元素与第三个元素的大小，若为逆序，则交换；.直至比较第直至比较第 n-1 个元素与第个元素与第 n 个元素的大小，若为逆序，则交换；个元素的大小，若为逆序，则交换；第一趟排序第一趟排序:结果结果:关键字最大关键字最大的记录被交换至的记录被交换至最后最后一个元素位置上。一个元素位置上。交换排序冒泡排序第18页，共70页，编辑于2022年，星期六例，序列例，序列 49 38 76 13 2749 38 76 13 2738 49 13 27 38 4913 7627 76初初始始第第一一趟趟排排序序后后最大值最大值13 4927 4
13、9次大值次大值第第二二趟趟排排序序后后38 13 2713 2713 38 27 38第第三三趟趟排排序序后后第第四四趟趟排排序序后后第19页，共70页，编辑于2022年，星期六冒泡排序的算法实现冒泡排序的算法实现。void Bubblesort(ElemType R,int n)int flag=1;/当flag为0则停止排序 for (int i=1;i=i;j-)if(RjRj-1)/发生逆序 ElemType t=Rj;Rj=Rj-1;Rj-1=t;flag=1;/交换，并标记发生了交换 if(flag=0)return;第20页，共70页，编辑于2022年，星期六冒泡排序的效率分析冒
14、泡排序的效率分析从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n)/2，因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法。第21页，共70页，编辑于2022年，星期六冒泡排序的一种改进算法。冒泡排序的一种改进算法。思想思想:以以首记录首记录作为作为轴记录轴记录，从前、后双向扫描序列，通过交换，实现大，从前、后双向扫描序列，通过交换，
15、实现大值记录后移，小值记录前移，最终将轴记录安置在一个适当的位值记录后移，小值记录前移，最终将轴记录安置在一个适当的位置。置。(小值记录在前、大值记录在后小值记录在前、大值记录在后)轴记录轴记录将原序列分割成两部分，依次对前后两部分重新设定轴记录，继将原序列分割成两部分，依次对前后两部分重新设定轴记录，继而分别再进行快速排序。而分别再进行快速排序。直至整个序列有序。直至整个序列有序。交换排序快速排序第22页，共70页，编辑于2022年，星期六快排序（Quick Sort)快速排序实例n快排序算法思想第23页，共70页，编辑于2022年，星期六快排序（Quick Sort)|快排序-分割过程z快
16、排序是一个分治算法（也是第一个）z快排序的关键过程是每次递归的分割过程z分割问题描述：对一个序列，取它的一个元素作为轴，把所有小于轴的元素放在它的左边，大于它的元素放在它的右边z分割算法：用临时变量对轴备份取两个指针low和high，它们的初始值就是序列的两端下标，在整个过程中保证low不大于high移动两个指针l首先从high所指的位置向左搜索，找到第一个小于轴的元素,把这个元素放在low的位置l再从low开始向右，找到第一个大于轴的元素，把它放在high的位置第24页，共70页，编辑于2022年，星期六快排序（Quick Sort)|快排序-分割过程z分割算法：重复上述过程，直到low=h
17、igh，把轴放在low所指的位置这样所有大于轴的元素被放在右边，所有小于轴的元素被放在左边第25页，共70页，编辑于2022年，星期六快排序（Quick Sort)|快排序-分割过程38 65 97 76 13 27 4949lowlowhighhighpivot=49 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7highhigh38 65 97 76 13 4927lowlow27 38 97 76 13 4965highhigh27 38 97 76 65 4913lowlow27 38 13 76 65 4997highhigh49第26页，共70页，编辑于2022年，星
18、期六快排序（Quick Sort)|快排序-分割过程int Partition(T Array,int low,int high)T pivot=Arraylow;/while(low high)/在作为快排序的子程序时不用 while(low=pivot)high-;Arraylow=Arrayhigh;while(low high&Arraylow=pivot)low+;Arrayhigh=Arraylow;/在作为快排序的子程序时不用 Arraylow=pivot;return low;第27页，共70页，编辑于2022年，星期六快排序（Quick Sort)|快排序-算法z快排序算法是
19、个递归地对序列进行分割的过程，递归终止的条件是最终序列长度为1 0 1 2 3 4 5 6 70 1 2 3 4 5 6 749 38 65 97 76 13 27 49 76 97 65 4927 38 134949133827 49 65977613 17 38 49 76 9749 65第28页，共70页，编辑于2022年，星期六快排序（Quick Sort)|快排序-算法void QuickSort(T Array,int low,int high)int PivotLocation;if(low high)PivotLocation=Partition(Array,low,high)
20、;QuickSort(Array,low,PivotLocation-1);QuickSort(Array,PivotLocation+1,high);第29页，共70页，编辑于2022年，星期六3快速排序的效率分析快速排序的效率分析若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数n与二叉树深度h应满足log2nhlog2n+1，所以总的比较次数不会超过(n+1)log2n。因此，快速排序的最好时间复杂度应为O（nlog2n）。而且在理论上已经证明，快速排序的平均时间复杂度也为O（nlog2n）。若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二
21、叉树是一棵单分枝树，得到的非空子区间包含有n-i个(i代表二叉树的层数（1in）元素，每层划分需要比较n-i+2次，所以总的比较次数为（n2+3n-4）/2。因此，快速排序的最坏时间复杂度为O(n2)。快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。快速排序是一种不稳定的排序方法。第30页，共70页，编辑于2022年，星期六思想思想:每一趟都选出一个最大或最小的元素，并放在合适每一趟都选出一个最大或最小的元素，并放在合适当的位置。当的位置。简单选择排序简单选择排序 树形选择排序树形选择排序 堆排序堆排序选择排序第31页，共70页，编辑于20
22、22年，星期六思想思想:第第 1 趟选择趟选择:从从 1n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并和第 1 个记个记录交换。录交换。第第 2 趟选择趟选择:从从 2n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并和第 2 个记录交个记录交换。换。第第n-1趟选择趟选择:从从 n-1n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并和第 n-1 个记个记录交换。录交换。.简单选择排序第32页，共70页，编辑于2022年，星期六例，序列例，序列 49 38 97 65 76第第 1 趟选择趟选择:min38 49 97 6
23、5 76第第 2 趟选择趟选择:min38 49 97 65 76第第 3 趟选择趟选择:min38 49 65 97 76第第 4 趟选择趟选择:min38 49 65 76 97第33页，共70页，编辑于2022年，星期六直接选择排序的算法直接选择排序的算法template void SelectSort(T Vector,int CurrentSize)for(int i=0;i CurrentSize-1;i+)int k=i;/选择具有最小排序码的对象 for(int j=i+1;j CurrentSize;j+)if(Vectorj Vectork)k=j;/当前具最小排序码的对象
24、 if(k!=i)/对换到第 i 个位置 Swap(Vectori,Vectork);第34页，共70页，编辑于2022年，星期六选择排序的主要操作是进行关键字间的选择排序的主要操作是进行关键字间的比较比较。在在 n 个关键字中选出最小值，至少需要个关键字中选出最小值，至少需要 n-1 次比较次比较。在剩余的在剩余的 n-1 个关键字中选出最小值，至少需要个关键字中选出最小值，至少需要 n-2 次比较次比较？如果能利用前如果能利用前 n-1 次比较所得信息，可以减少后面选择的比较次比较所得信息，可以减少后面选择的比较次数。次数。体育比赛中的锦标赛体育比赛中的锦标赛:第35页，共70页，编辑于2
25、022年，星期六例，例，8 名运动员要决出名运动员要决出 冠、亚、季军。冠、亚、季军。按简单选择排序需要比赛按简单选择排序需要比赛 7+6+5=18 场。场。若能够利用以前的比赛结果，比赛场次实际可以减少为若能够利用以前的比赛结果，比赛场次实际可以减少为 11 场。场。前提前提:若若 甲甲 胜胜 乙乙，乙，乙 胜胜 丙丙，则，则 甲甲 必能胜必能胜 丙丙。ZhaoChaLiuBaoDiaoYangXueWangBaoBaoDiaoChaBaoDiaoWang冠军冠军第36页，共70页，编辑于2022年，星期六如何求如何求 亚军？亚军？ZhaoChaLiuDiaoYangXueWangChaDi
26、aoCha亚军亚军可以利用前面的比赛结果！可以利用前面的比赛结果！ChaLiuDiaoWang第37页，共70页，编辑于2022年，星期六如何求如何求 季军？季军？ZhaoLiuDiaoYangXueWangLiuDiaoDiao季军季军同样可以利用前面的比赛结果！同样可以利用前面的比赛结果！LiuDiaoWangZhao第38页，共70页，编辑于2022年，星期六又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。例，序列例，序列 49 38 65 97 76 13 27 50第一趟选择第一趟选择1338134938659776
27、13275038651327最小值最小值树形选择排序第39页，共70页，编辑于2022年，星期六第二趟选择第二趟选择2738274938659776275038657627次小值次小值第三趟选择第三趟选择38385049386597765038657650次次小值次次小值493865977613275049386597762750缺点:需要大量辅助存储空间第40页，共70页，编辑于2022年，星期六堆堆:一棵完全二叉树，任一个非终端结点的值均小于等于一棵完全二叉树，任一个非终端结点的值均小于等于(或大于等于或大于等于)其左、右儿子结点的值。其左、右儿子结点的值。例，例，128547305336
28、2491963811 98324根结点为最小值根结点为最小值根结点为最大值根结点为最大值堆排序第41页，共70页，编辑于2022年，星期六2.把这棵普通的完全二叉树改造成堆，便可获取把这棵普通的完全二叉树改造成堆，便可获取最小值最小值；思想思想:3.输出最小值输出最小值；4.删除根结点，继续改造剩余树成堆，便可获取删除根结点，继续改造剩余树成堆，便可获取次小值次小值；5.输出次小值输出次小值；6.重复改造，输出次次小值、次次次小值，直至所有结点均输出，重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序便得到一个排序。1.将序列构造成一棵完全二叉树将序列构造成一棵完全二叉树；
29、第42页，共70页，编辑于2022年，星期六例，序列例，序列 49 38 65 97 76 13 27 501.按顺序依次构造成完全二叉树的结点；按顺序依次构造成完全二叉树的结点；49386597761327502.把完全二叉树改造成把完全二叉树改造成堆堆；从下向上，父子交换；从下向上，父子交换；50971365134949273.取得最小值取得最小值 134.删除删除 13，重新改造成新堆；，重新改造成新堆；1397279797495.取得次小值取得次小值 27；6.删除删除 27，重新改造成新堆；，重新改造成新堆；9727973897507.取得次次小值取得次次小值 38；第43页，共70
30、页，编辑于2022年，星期六归并排序（Merge Sort)|归并-合并两个有序的序列z假设有两个已排序好的序列A（长度为n1），B（长度为n2），将它们合并为一个有序的序列C（长度为n=n1+n2)z方法很简单：把A，B两个序列的最小元素进行比较，把其中较小的元素作为C的第一个元素；在A，B剩余的元素中继续挑最小的元素进行比较，确定C的第二个元素，依次类推，就可以完成对A和B的归并，其复杂度为O(n)第44页，共70页，编辑于2022年，星期六归并排序（Merge Sort)|归并-合并两个有序的序列A:1 3 8 9 11B:2 5 7 10 13C:1 2 3 5 7 8 9 10 11
31、 13第45页，共70页，编辑于2022年，星期六归并排序（Merge Sort)|归并-合并两个有序的序列void merge(T A,int Alen,T B,int Blen,T C)int i=0,j=0,k=0;while(i Alen&j Blen)if(Ai Bj)Ck+=Ai+;else Ck+=Bj+;while(i Alen)Ck+=Ai+;while(j Blen)Ck+=Bj+;第46页，共70页，编辑于2022年，星期六归并排序（Merge Sort)|归并-合并一个序列中的两个有序的数据段void merge(T A,int l,int m,int h)int i=
32、l,j=m+1,k=0;T*C=new Th-l+1;while(i=m&j=h)if(Ai Aj)Ck+=Ai+;else Ck+=Aj+;while(i =m)Ck+=Ai+;while(j =h)Ck+=Bj+;for(k=0;kb和ab),z如果以每次比较作为节点，则每个以比较为基础的排序算法都可以用一个二叉树来表示，其中一个中间节点表示一次比较，叶子节点表示排序的一种结果，这样的二叉树称为判定树或决策树z举例：比如有一个序列a,b,c(a,b,c互不相等），下列算法：先比较a和b,再比较a和c，最后比较b和c 可以用下面的判定树表示 第53页，共70页，编辑于2022年，星期六归并排
33、序（Merge Sort)|以比较为基础的排序算法的下界ab?yesac?yesbc?yesabcacbnononocabac?yesbacnobc?yesbcacbano第54页，共70页，编辑于2022年，星期六归并排序（Merge Sort)|以比较为基础的排序算法的下界z假设输入为a,b,c,acb,则算法执行经过的路线为(ab)(ac)(bc)，需要3次比较z假设输入为a,b,c,bac,则算法执行经过的路线为(ab)(ac)需要2次比较z任何以比较为基础的排序算法都可以表示为一棵决策树树的形状和大小表示的是排序算法的功能和需要排序的元素个数树的高度表示了算法的运行时间任何排序决策树
34、都有n!个叶子 第55页，共70页，编辑于2022年，星期六归并排序（Merge Sort)|以比较为基础的排序算法的下界z根据数据结构中关于二叉树的性质，有：z最坏情况：任何排序算法至少要做次比较z平均情况：任何排序算法的平均比较次数的下界是z结论：具有O(nlgn)复杂度的比较排序算法在渐进意义下是最优的算法 第56页，共70页，编辑于2022年，星期六是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。1.多关键字排序多关键字排序扑克牌问题扑克牌问题:已知扑克牌中已知扑克牌中52张牌面的次序关系定义为张牌面的次序关系定义为:
35、花色花色:面值面值:2 3 A.例，例，8 3花色优先级更高，为主关键字，面值为次关键字基数排序第57页，共70页，编辑于2022年，星期六2.52张牌排序方法张牌排序方法:最高位优先法最高位优先法(MSDF):先按不同先按不同“花色花色”分成有次序的分成有次序的4堆，每一堆均具有相同的花色；堆，每一堆均具有相同的花色；然后分别对每一堆按然后分别对每一堆按“面值面值”大小整理有序。大小整理有序。最低位优先法最低位优先法(LSDF):先按不同先按不同“面值面值”分成分成 13 堆堆；然后将这然后将这 13 堆牌自小至大叠在一起堆牌自小至大叠在一起(2,3,.,A)；然后将这付牌整个颠倒过来再重新
36、按不同的然后将这付牌整个颠倒过来再重新按不同的“花色花色”分成分成 4 堆堆；最后将这最后将这 4 堆牌按自小至大的次序合在一起堆牌按自小至大的次序合在一起。收集分配第58页，共70页，编辑于2022年，星期六3.基数排序基数排序基数排序就是借助于基数排序就是借助于“分配分配”和和“收集收集”两种操作实现对单逻辑关键字的排序。两种操作实现对单逻辑关键字的排序。首先，单逻辑关键字通常都可以看作是由若干关键字复合而成。首先，单逻辑关键字通常都可以看作是由若干关键字复合而成。其次，利用其次，利用 LSDF 法实现对若干关键字的排序。法实现对若干关键字的排序。例，若关键字是数值，且值域为例，若关键字是
37、数值，且值域为 0K999，故可以将故可以将 K 看作是由看作是由 3 个关键字个关键字 K0 K1 K2 组成，组成，例，例，603是由是由 6 0 3 组成。组成。第59页，共70页，编辑于2022年，星期六例，序列例，序列 278 109 063 930 589 184 505 269 008 083第一趟分配第一趟分配0 1 2 3 4 5 6 7 8 9278 109063930589184505269008083第一趟收集第一趟收集930063 083184505278 008109 589 269第二趟分配第二趟分配0 1 2 3 4 5 6 7 8 99300630831845
38、05278008109589269第二趟收集第二趟收集505 008 109930063 269278083 184 589第60页，共70页，编辑于2022年，星期六第二趟收集第二趟收集505 008 109930063 269278083 184 589第三趟分配第三趟分配0 1 2 3 4 5 6 7 8 9505008 109930063269278083184589第三趟收集第三趟收集008 063 083109 184269 278505 589930第61页，共70页，编辑于2022年，星期六中序遍历可实现二叉搜索树结点的有序化中序遍历可实现二叉搜索树结点的有序化 13 8523
39、 1837 95 8 9 13 18 23 37?如何实现自大到小排列二叉树排序第62页，共70页，编辑于2022年，星期六各种内排序方法的选择各种内排序方法的选择1从时间复杂度选择从时间复杂度选择对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法。2从空间复杂度选择从空间复杂度选择尽量选空间复杂度为O（1）的排序方法，其次选空间复杂度为O(log2n)的快速排序方法，最后才选空间复杂度为O（n）二路归并排序的排序方法。3一般选择规则一般选择规则（1）当待排序元素的个数n较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。第63页，共70
40、页，编辑于2022年，星期六（2)当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。（3）当待排序元素的个数n大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。（4)当待排序元素的个数n小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序为宜。(5)当待排序元素的个数n小，对稳定性不做要求时，则采用直接选择排序为宜，若排序码不接近逆序，也可以采用直接插入排序。冒泡排序一般很少采用。第64页，共70页，编辑于2022年，星期六各种排序方法的比较各种排序方法的比较第65页，共70页，编辑于2022年，星期六案例分
41、析：多项式相加|C+中如何表示多项式z链表|对两个多项式中的每个数据项的变量进行排序|执行加法运算第66页，共70页，编辑于2022年，星期六课堂练习|对于一组记录的排序码为(465，792，562，383，401，845，502，423)，写出基数排序（低位优先）进行一趟分配与回收后的结果。第67页，共70页，编辑于2022年，星期六序列序列 8,3,10,13,25,18,6,4对上述序列使用直接插入排序、希尔排序（对上述序列使用直接插入排序、希尔排序（d1=4；d2=2;d3=1;）、快速排序、堆排序、归并排序、基数排序（低位优先）进行排）、快速排序、堆排序、归并排序、基数排序（低位优先）进行排序的过程。序的过程。作业1第68页，共70页，编辑于2022年，星期六作业2|P409：1，15第69页，共70页，编辑于2022年，星期六上机作业1.直接插入排序程序2.希尔排序程序3.编写冒泡排序程序（改进版）4.快速排序程序5.简单选择排序程序6.归并排序程序第70页，共70页，编辑于2022年，星期六