数据结构之树和图算法

数据结构之树和图算法第1页，共70页，2023年，2月20日，星期六假设Ki=Kj

，且排序前序列中Ri

领先于Rj

；若在排序后的序列中Ri

仍领先于Rj

，则称排序方法是稳定的。若在排序后的序列中Rj

仍领先于Ri

，则称排序方法是不稳定的。例，序列3158

869若排序后得368

8915稳定的若排序后得368

8915不稳定的稳定排序与不稳定排序第2页，共70页，2023年，2月20日，星期六内部排序:

指的是待排序记录存放在计算机随机存储器中进行的排序过程。外部排序:

指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。内部排序与外部排序第3页，共70页，2023年，2月20日，星期六排序的时间复杂性排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。第4页，共70页，2023年，2月20日，星期六按照排序过程中所依据的原则的不同可以分类为:

插入排序

交换排序(快速排序)

选择排序

归并排序

基数排序

二叉排序树排序内部排序第5页，共70页，2023年，2月20日，星期六思想:利用有序表的插入操作进行排序有序表的插入:

将一个记录插入到已排好序的有序表中，从而得到一个新的有序表。例，序列132738657697插入4913273849

657697插入排序——直接插入排序第6页，共70页，2023年，2月20日，星期六例，序列49386597761327初始，S={49}；{3849}初始，令第1

个元素作为初始有序表；依次插入第

2,3,…,k

个元素构造新的有序表；直至最后一个元素；{384965}{38496597}{3849657697}{133849657697}{13273849657697}直接插入排序算法主要应用比较和移动两种操作。直接插入排序算法描述第7页，共70页，2023年，2月20日，星期六voidinsertsort(ElemTypeR[],intn)//待排序元素用一个数组R表示，数组有n个元素{for(inti=1;i<n;i++)//i表示插入次数，共进行n-1次插入

{ElemTypetemp=R[i];//把待排序元素赋给tempintj=i-1;while((j>=0)&&(temp<R[j])){R[j+1]=R[j];j--;}//顺序比较和移动

R[j+1]=temp;}}第8页，共70页，2023年，2月20日，星期六直接插入排序的效率分析从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。从时间分析，首先外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i＋2次（逆序）（i=1，2，…，n-1）。Cmin=n-1Mmin=2（n-1）Cmax=1+2+…+n-1=（n2-n）/2Mmax=3+4+…+n+1=（n2+3n-4）/2Cave=（n2+n-2）/4Mmax=（n2+7n-8）/4因此，直接插入排序的时间复杂度为O（n2）。直接插入算法的元素移动是顺序的，该方法是稳定的。第9页，共70页，2023年，2月20日，星期六由于直接插入排序算法利用了有序表的插入操作，故顺序查找操作可以替换为折半查找操作。例，序列49386597761327设已形成有序表{3849659776}插入元素13折半插入排序第10页，共70页，2023年，2月20日，星期六算法:voidBinaryInsertSort(ElemTypeR[],intn){for(inti=1;i<n;i++)//共进行n-1次插入

{ intleft=0,right=i-1;ElemTypetemp=R[i];while(left<=right) {intmiddle=(left+right)/2;//取中点

if(temp<R[middle])right=middle-1;//取左区间

else left=middle+1;}//取右区间

for(intj=i-1;j>=left;j--) R[j+1]=R[j];//元素后移空出插入位

R[left]=temp;}}第11页，共70页，2023年，2月20日，星期六折半插入效率分析二分插入算法与直接插入算法相比，需要辅助空间与直接插入排序基本一致；时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏，两种方法的元素的移动次数相同，因此二分插入排序的时间复杂度仍为O(n2)。二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。第12页，共70页，2023年，2月20日，星期六分析直接插入排序1.若待排序记录序列按关键字基本有序，则排序效率可大大提高；2.待排序记录总数越少，排序效率越高；希尔(shell)排序第13页，共70页，2023年，2月20日，星期六思想:先将待排序记录序列分割成为若干子序列分别进行直接插入排序；待整个序列中的记录基本有序后，再全体进行一次直接插入排序。例，序列493865977613274855419第一趟排序491319382765489755764131949273848655597476第14页，共70页，2023年，2月20日，星期六第二趟排序13194927384865559747613553876274

654948199713385576427

4965194897第三趟排序4131927

38

4849

556576

97第15页，共70页，2023年，2月20日，星期六希尔排序的算法template<classT>voidShellSort(TVector[],intarrSize){Ttemp;

intgap=arrSize/2;//gap是子序列间隔

while(gap!=0){ //循环,直到gap为零

for(inti=gap;i<arrSize;i++){temp=Vector[i]; //直接插入排序

for(intj=i;j>=gap;j-=gap)

if(temp<Vector[j-gap])

Vector[j]=Vector[j-gap];elsebreak;

Vector[j]=temp;}

gap=(int)(gap/2

);}}

第16页，共70页，2023年，2月20日，星期六希尔排序效率分析希尔排序的时间复杂性在O（nlog2n）和O（n2

）之间，大致为O（n1.3）。第17页，共70页，2023年，2月20日，星期六思想:

通过不断比较相邻元素大小，进行交换来实现排序。首先将第一个元素与第二个元素比较大小，若为逆序，则交换；然后比较第二个元素与第三个元素的大小，若为逆序，则交换；...直至比较第n-1个元素与第n个元素的大小，若为逆序，则交换；第一趟排序:结果:关键字最大的记录被交换至最后一个元素位置上。交换排序——冒泡排序第18页，共70页，2023年，2月20日，星期六例，序列4938761327493876132738

49

13

27384913762776初始第一趟排序后最大值13

492749次大值第二趟排序后3813

27132713382738第三趟排序后第四趟排序后第19页，共70页，2023年，2月20日，星期六冒泡排序的算法实现。voidBubblesort(ElemTypeR[],intn){intflag=1;//当flag为0则停止排序

for(inti=1;i<n;i++){//i表示趟数，最多n-1趟

flag=0;//开始时元素未交换

for(intj=n-1;j>=i;j--)if(R[j]<R[j-1]) {//发生逆序ElemTypet=R[j]; R[j]=R[j-1]; R[j-1]=t;flag=1;}//交换，并标记发生了交换

if(flag==0)return;}}第20页，共70页，2023年，2月20日，星期六冒泡排序的效率分析从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n)/2，因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法。第21页，共70页，2023年，2月20日，星期六冒泡排序的一种改进算法。思想:以首记录作为轴记录，从前、后双向扫描序列，通过交换，实现大值记录后移，小值记录前移，最终将轴记录安置在一个适当的位置。(小值记录在前、大值记录在后)轴记录将原序列分割成两部分，依次对前后两部分重新设定轴记录，继而分别再进行快速排序。直至整个序列有序。交换排序——快速排序第22页，共70页，2023年，2月20日，星期六快排序（QuickSort)

快速排序实例快排序—算法思想第23页，共70页，2023年，2月20日，星期六快排序（QuickSort)快排序---分割过程快排序是一个分治算法（也是第一个）快排序的关键过程是每次递归的分割过程分割问题描述：对一个序列，取它的一个元素作为轴，把所有小于轴的元素放在它的左边，大于它的元素放在它的右边分割算法：用临时变量对轴备份取两个指针low和high，它们的初始值就是序列的两端下标，在整个过程中保证low不大于high移动两个指针首先从high所指的位置向左搜索，找到第一个小于轴的元素,把这个元素放在low的位置再从low开始向右，找到第一个大于轴的元素，把它放在high的位置第24页，共70页，2023年，2月20日，星期六快排序（QuickSort)快排序---分割过程分割算法：重复上述过程，直到low=high，把轴放在low所指的位置这样所有大于轴的元素被放在右边，所有小于轴的元素被放在左边第25页，共70页，2023年，2月20日，星期六快排序（QuickSort)快排序---分割过程3865977613274949lowhighpivot=49

01234567high38659776134927low27389776134965high27389776654913low27381376654997high49第26页，共70页，2023年，2月20日，星期六快排序（QuickSort)快排序---分割过程intPartition(TArray[],intlow,inthigh){Tpivot=Array[low]; //while(low<high){//在作为快排序的子程序时不用

while(low<high&&Array[high]>=pivot) high--;Array[low]=Array[high]; while(low<high&&Array[low]<=pivot) low++;Array[high]=Array[low];//}//在作为快排序的子程序时不用

Array[low]=pivot;returnlow;}第27页，共70页，2023年，2月20日，星期六快排序（QuickSort)快排序---算法快排序算法是个递归地对序列进行分割的过程，递归终止的条件是最终序列长度为1

0123456749386597761327497697654927381349491338274965977613173849769749

65第28页，共70页，2023年，2月20日，星期六快排序（QuickSort)快排序---算法voidQuickSort(TArray[],intlow,inthigh){ intPivotLocation; if(low<high){ PivotLocation=Partition(Array,low,high);QuickSort(Array,low,PivotLocation-1);QuickSort(Array,PivotLocation+1,high); }}第29页，共70页，2023年，2月20日，星期六3．快速排序的效率分析若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数n与二叉树深度h应满足log2n<h<log2n+1，所以总的比较次数不会超过(n+1)log2n。因此，快速排序的最好时间复杂度应为O（nlog2n）。而且在理论上已经证明，快速排序的平均时间复杂度也为O（nlog2n）。若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，得到的非空子区间包含有n-i个(i代表二叉树的层数（1≤i≤n）元素，每层划分需要比较n-i+2次，所以总的比较次数为（n2+3n-4）/2。因此，快速排序的最坏时间复杂度为O(n2)。快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。快速排序是一种不稳定的排序方法。第30页，共70页，2023年，2月20日，星期六思想:

每一趟都选出一个最大或最小的元素，并放在合适当的位置。

简单选择排序

树形选择排序

堆排序选择排序第31页，共70页，2023年，2月20日，星期六思想:第1趟选择:从1—n

个记录中选择关键字最小的记录，并和第1个记录交换。第2趟选择:从2—n

个记录中选择关键字最小的记录，并和第2

个记录交换。第n-1趟选择:从n-1—n

个记录中选择关键字最小的记录，并和第n-1

个记录交换。...简单选择排序第32页，共70页，2023年，2月20日，星期六例，序列4938976576第1趟选择:min3849976576第2趟选择:min38

49976576第3趟选择:min38

49

659776第4趟选择:min38

49

65

7697第33页，共70页，2023年，2月20日，星期六直接选择排序的算法template<classT>voidSelectSort(TVector[],intCurrentSize){for(inti=0;i<CurrentSize-1;i++){intk=i;//选择具有最小排序码的对象

for(intj=i+1;j<CurrentSize;j++)if(Vector[j]<Vector[k])

k=j;//当前具最小排序码的对象

if(k!=i)

//对换到第

i个位置

Swap(Vector[i],Vector[k]

);} }第34页，共70页，2023年，2月20日，星期六选择排序的主要操作是进行关键字间的比较。在n个关键字中选出最小值，至少需要n-1次比较。在剩余的n-1个关键字中选出最小值，至少需要n-2次比较？如果能利用前n-1次比较所得信息，可以减少后面选择的比较次数。体育比赛中的锦标赛:第35页，共70页，2023年，2月20日，星期六例，8名运动员要决出冠、亚、季军。按简单选择排序需要比赛7+6+5=18

场。若能够利用以前的比赛结果，比赛场次实际可以减少为11

场。前提:

若甲胜乙，乙胜丙，则甲必能胜丙。ZhaoChaLiuBaoDiaoYangXueWangBaoBaoDiaoChaBaoDiaoWang冠军第36页，共70页，2023年，2月20日，星期六如何求亚军？ZhaoChaLiuDiaoYangXueWangChaDiaoCha亚军可以利用前面的比赛结果！ChaLiuDiaoWang第37页，共70页，2023年，2月20日，星期六如何求季军？ZhaoLiuDiaoYangXueWangLiuDiaoDiao季军同样可以利用前面的比赛结果！LiuDiaoWangZhao第38页，共70页，2023年，2月20日，星期六又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。例，序列4938659776132750第一趟选择133813493865977613275038651327最小值树形选择排序第39页，共70页，2023年，2月20日，星期六第二趟选择2738274938659776∞275038657627次小值第三趟选择3838504938659776∞∞5038657650次次小值49386597761327504938659776∞2750缺点:

需要大量辅助存储空间第40页，共70页，2023年，2月20日，星期六堆:

一棵完全二叉树，任一个非终端结点的值均小于等于(或大于等于)其左、右儿子结点的值。例，128547305336249196381198324根结点为最小值根结点为最大值堆排序第41页，共70页，2023年，2月20日，星期六2.把这棵普通的完全二叉树改造成堆，便可获取最小值；思想:3.输出最小值；4.删除根结点，继续改造剩余树成堆，便可获取次小值；5.输出次小值；6.重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序。1.将序列构造成一棵完全二叉树；第42页，共70页，2023年，2月20日，星期六例，序列49386597761327501.按顺序依次构造成完全二叉树的结点；49386597761327502.把完全二叉树改造成堆；从下向上，父子交换；50971365134949273.取得最小值134.删除13

，重新改造成新堆；1397279797495.取得次小值27；6.删除27

，重新改造成新堆；9727973897507.取得次次小值38；第43页，共70页，2023年，2月20日，星期六归并排序（MergeSort)归并---合并两个有序的序列假设有两个已排序好的序列A（长度为n1），B（长度为n2），将它们合并为一个有序的序列C（长度为n=n1+n2)方法很简单：把A，B两个序列的最小元素进行比较，把其中较小的元素作为C的第一个元素；在A，B剩余的元素中继续挑最小的元素进行比较，确定C的第二个元素，依次类推，就可以完成对A和B的归并，其复杂度为O(n)第44页，共70页，2023年，2月20日，星期六归并排序（MergeSort)归并---合并两个有序的序列A:138911B:2571013C:1

2

3

5

7

89

10

11

13第45页，共70页，2023年，2月20日，星期六归并排序（MergeSort)归并---合并两个有序的序列voidmerge(TA[],intAlen,TB[],intBlen,TC[]){inti=0,j=0,k=0;while(i<Alen&&j<Blen){if(A[i]<B[j]) C[k++]=A[i++]; else C[k++]=B[j++]; } while(i<Alen) C[k++]=A[i++]; while(j<Blen) C[k++]=B[j++];}第46页，共70页，2023年，2月20日，星期六归并排序（MergeSort)归并---合并一个序列中的两个有序的数据段voidmerge(TA[],intl,intm,inth){inti=l,j=m+1,k=0;T*C=newT[h-l+1];while(i<=m&&j<=h){if(A[i]<A[j])C[k++]=A[i++]; elseC[k++]=A[j++];} while(i<=m)C[k++]=A[i++]; while(j<=h)C[k++]=B[j++];for(k=0;k<h-l+1;k++)A[i+k]=C[k];//将排好序的元素写回A数组

delete[]C;}第47页，共70页，2023年，2月20日，星期六归并排序（MergeSort)归并排序归并排序是一个分治递归算法递归基础：若序列只有一个元素，则它是有序的，不执行任何操作递归步骤：先把序列划分成长度基本相等的两个序列对每个子序列递归排序把排好序的子序列归并成最后的结果第48页，共70页，2023年，2月20日，星期六归并排序（MergeSort)归并排序初始序列：[8，4，5，6，2，1，7，3]分解：[8][4][5][6][2][1][7][3]归并：[4，8][5，6][1，2][3，7]归并：[4，5，6，8][1，2，3，7]归并：[1，2，3，4，5，6，7，8]分解：[8，4，5，6][2，1，7，3]分解：[8，4][5，6][2，1][7，3]第49页，共70页，2023年，2月20日，星期六归并排序（MergeSort)归并排序voidMergeSort(intA[],intl,inth)//将数组A中A[l,…,(l+h)/2]与A[(l+h)/2+1,…,h]两段数据归并{

if(l==h) return; intm=(l+h)/2; MergeSort(A,l,m); MergeSort(A,m+1,h); Merge(A,l,m,h);}第50页，共70页，2023年，2月20日，星期六归并排序（MergeSort)算法分析最坏情况：归并排序是一个递归算法，所以很容易得到算法计算量的递推公式

所以算法最坏情况的复杂度为算法需要的辅助空间

第51页，共70页，2023年，2月20日，星期六归并排序（MergeSort)其他策略上面归并排序每次迭代时将原序列分割为两个基本等长的序列，称为二路归并排序也可以分割成其他的分，如3，4等等评论：尽管归并排序最坏情况的比较次数比快速排序少，但它需要更多的元素移动，因此，它在实用中不一定比快速排序快

第52页，共70页，2023年，2月20日，星期六归并排序（MergeSort)以比较为基础的排序算法的下界基于比较的算法总是在一系列比较下完成的每次比较都可能出现两种情况(a>b和a<b),如果以每次比较作为节点，则每个以比较为基础的排序算法都可以用一个二叉树来表示，其中一个中间节点表示一次比较，叶子节点表示排序的一种结果，这样的二叉树称为判定树或决策树举例：比如有一个序列{a,b,c}(a,b,c互不相等），下列算法：先比较a和b,再比较a和c，最后比较b和c

可以用下面的判定树表示

第53页，共70页，2023年，2月20日，星期六归并排序（MergeSort)以比较为基础的排序算法的下界a<b?yesa<c?yesb<c?yesa<b<ca<c<bnononoc<a<ba<c?yesb<a<cnob<c?yesb<c<ac<b<ano第54页，共70页，2023年，2月20日，星期六归并排序（MergeSort)以比较为基础的排序算法的下界假设输入为a,b,c,a<c<b,则算法执行经过的路线为(a<b)—(a<c)—(b<c)，需要3次比较假设输入为a,b,c,b<a<c,则算法执行经过的路线为(a<b)—(a<c)需要2次比较任何以比较为基础的排序算法都可以表示为一棵决策树树的形状和大小表示的是排序算法的功能和需要排序的元素个数树的高度表示了算法的运行时间任何排序决策树都有n!个叶子

第55页，共70页，2023年，2月20日，星期六归并排序（MergeSort)以比较为基础的排序算法的下界根据数据结构中关于二叉树的性质，有：最坏情况：任何排序算法至少要做 次比较平均情况：任何排序算法的平均比较次数的下界是结论：具有O(nlgn)复杂度的比较排序算法在渐进意义下是最优的算法

第56页，共70页，2023年，2月20日，星期六是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。1.多关键字排序扑克牌问题:已知扑克牌中52张牌面的次序关系定义为:♣

＜

♦

＜

♥

＜

♠花色:面值:2＜3＜＜A...例，♦8

♠

3＜花色优先级更高，为主关键字，面值为次关键字基数排序第57页，共70页，2023年，2月20日，星期六2.52张牌排序方法:最高位优先法(MSDF):先按不同“花色”分成有次序的4堆，每一堆均具有相同的花色；然后分别对每一堆按“面值”大小整理有序。最低位优先法(LSDF):先按不同“面值”分成13堆；然后将这13堆牌自小至大叠在一起(2,3,...,A)；然后将这付牌整个颠倒过来再重新按不同的“花色”分成4堆；最后将这4堆牌按自小至大的次序合在一起。收集分配第58页，共70页，2023年，2月20日，星期六3.基数排序基数排序就是借助于“分配”和“收集”两种操作实现对单逻辑关键字的排序。首先，单逻辑关键字通常都可以看作是由若干关键字复合而成。其次，利用LSDF法实现对若干关键字的排序。例，若关键字是数值，且值域为0≤K≤999，故可以将K

看作是由3个关键字K0K1K2

组成，例，603是由603

组成。第59页，共70页，2023年，2月20日，星期六例，序列278109063930589184505269008083第一趟分配0123456789278109063930589184505269008083第一趟收集930063