搜索
1/22算法设计与分析复习资料：1、背包问题的贪心算法：（贪心法）voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i=n;i++)x[i]=0;floatc=M;for(i=1;i=n;i++){if(w[i]c)break;x[i]=1;c-=w[i];}if(i=n)x[i]=c/w[i];}2、快速排序（分治法）voidQuickSort(Typea[],intp,intr){if(pr){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}3、n后问题（回溯法）intn;//皇后个数intsum=0;//可行解个数intx[N];//皇后放置的列数intplace(intk){inti;for(i=1;ik;i++)if(abs(k-i)==abs(x[k]-x[i])||x[k]==x[i])return0;return1;}intqueen(intt){if(tn&&n0)//当放置的皇后超过n时，可行解个数加1，此时n必须大于02/22sum++;elsefor(inti=1;i=n;i++){x[t]=i;//标明第t个皇后放在第i列if(place(t))//如果可以放在某一位置，则继续放下一皇后queen(t+1);}returnsum;}4、归并排序voidMergeSort(intarray[],intstart,intend){if(startend){inti;i=(end+start)/2;//对前半部分进行排序MergeSort(array,start,i);//对后半部分进行排序MergeSort(array,i+1,end);//合并前后两部分Merge(array,start,i,end);}}voidMerge(intarray[],intstart,intmid,intend){inttemp1[10],temp2[10];intn1,n2;n1=mid-start+1;n2=end-mid;//拷贝前半部分数组for(inti=0;in1;i++)temp1[i]=array[start+i];//拷贝后半部分数组for(inti=0;in2;i++)temp2[i]=array[mid+i+1];//把后面的元素设置的很大temp1[n1]=temp2[n2]=1000;//逐个扫描两部分数组然后放到相应的位置去for(intk=start,i=0,j=0;k=end;k++){if(temp1[i]=temp2[j]){array[k]=temp1[i];i++;}else{3/22array[k]=temp2[j];j++;}}}5、堆排序1.堆堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：Key[i]=key[2i+1]&&Key[i]=key[2i+2]或者Key[i]=Key[2i+1]&&key=key[2i+2]即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。堆分为大顶堆和小顶堆，满足Key[i]=Key[2i+1]&&key=key[2i+2]称为大顶堆，满足Key[i]=key[2i+1]&&Key[i]=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。2.堆排序的思想利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。其基本思想为(大顶堆)：1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]=R[n];3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。操作过程如下：1)初始化堆：将R[1..n]构造为堆；2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。下面举例说明：给定一个整形数组a[]={16,7,3,20,17,8}，对其进行堆排序。首先根据该数组元素构建一个完全二叉树，得到然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：4/2220和16交换后导致16不满足堆的性质，因此需重新调整这样就得到了初始堆。即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。此时3位于堆顶不满堆的性质，则需调整继续调整5/226/22这样整个区间便已经有序了。从上述过程可知，堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R[1...n]中选择最大记录，需比较n-1次，然后从R[1...n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序，不适合记录较少的排序。6、最小生成树（1）PRIM算法假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树:1:初始化:U={u0},TE={}。此步骤设立一个只有结点u0的结点集U和一个空的边集TE作为最小生成树的初始行态,在随后的算法执行中,这个行态会不断的发生变化,直到得到最小生成树为止。2:在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u0,v0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U中,其次边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合。3:如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。7/22（2）KrusKal算法第一步我们要做的事情就是将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择。排序完成后，我们率先选择了边AD。这样我们的图就变成了第二步，在剩下的边中寻找。我们找到了CE。这里边的权重也是5依次类推我们找到了6,7,7。完成之后，图变成了这个样子。下一步就是关键了。下面选择那条边呢？BC或者EF吗？都不是，尽管现在长度为8的边是最小的未选择的边。但是他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB,BA,AD,DF来接连）。所以我们不需要选择他们。类似的BD也已经连通了（这里上图的连通线用红色表示了）。最后就剩下EG和FG了。当然我们选择了EG。最后成功的图就是下图：8/22到这里所有的边点都已经连通了，一个最小生成树构建完成。Kruskal算法的时间复杂度由排序算法决定，若采用快排则时间复杂度为O(NlogN)。7、2-3树（B+树）M阶B+树的定义(M阶是指一个节点最多能拥有的孩子数,M2):图1.13阶B+树(1)根结点只有1个，分支数量范围[2,m]。(2)除根以外的非叶子结点，每个结点包含分支数范围[[m/2],m]，其中[m/2]表示取大于m/2的最小整数。(3)所有非叶子节点的关键字数目等于它的分支数量。(4)所有叶子节点都在同一层，且关键字数目范围是[[m/2],m]，其中[m/2]表示取大于m/2的最小整数。(5)所有非叶子节点的关键字可以看成是索引部分，这些索引等于其子树（根结点）中的最大（或最小）关键字。例如一个非叶子节点包含信息:(n，A0,K0,A1,K1,……,Kn,An)，其中Ki为关键字，Ai为指向子树根结点的指针，n表示关键字个数。即Ai所指子树中的关键字均小于或等于Ki，而Ai+1所指的关键字均大于Ki（i=1，2，……，n）。(6)叶子节点包含全部关键字的信息(非叶子节点只包含索引)，且叶子结点中的所有关键字依照大小顺序链接(所以一个B+树通常有两个头指针，一个是指向根节点的root，另一个是指向最小关键字的sqt)。l例1：往下图的3阶B+树中插入关键字99/22首先查找9应插入的叶节点(最左下角的那一个),插入发现没有破坏B+树的性质,完毕。插完如下图所示:l例2：往下图的3阶B+树插入20首先查找20应插入的叶节点(第二个叶子节点),插入，如下图发现第二个叶子节点已经破坏了B+树的性质,则把之分解成[2021],[3744]两个,并把21往父节点移，如下图发现父节点也破坏了B+树的性质,则把之再分解成[1521],[4459]两个,并把21往其父节点移，如下图10/22这次没有破坏B+树的性质(如果还是不满足B+树的性质,可以递归上去,直到满足为至),插入完毕。l例3：往下图的3阶B+树插入100首先查找100应插入的叶节点(最后一个节点),插入，如下图修改其所有父辈节点的键值为100(只有插入比当前树的最大数大的数时要做此步),如下图然后重复Eg.2的方法拆分节点,最后得11/227、Dijkstra算法1.初始时，S中只有源点，即S={v}，v的距离为0（到自己的距离为0）。U包含除v外地所有其他顶点，U中顶点u距离为边上的权（若v到u存在边）或∞（v到u不存在边，即u不是v的出边邻接点）2.从U中选取一个距离v最小的顶点k加入到S中（选定的距离就是v到k的最短路径）3.以k为新考虑的中间点，修改U中各顶点的距离。若从源点v经过顶点k到顶点u的距离比原来距离（不经过顶点k）段，则修改顶点u的距离，修改后的距离值为顶点k的距离加上边k-u的权4.重复步骤2、3直到所有的顶点都加入到S中步骤S集合中U集合中1选入A，此时S={A}此时最短路径A-A=0以A为中间点，从A开始找U={B,C,D,E,F}A-B=6A-C=3A-U中其他顶点=∞其中A-C=3权值为最小，路径最短2选入上一轮中找到的最短路径的顶点C，此时S={A,C}此时最短路径A-A=0，A-C=3以C为中间点，从A-C=3这条最短路径开始新一轮查找U={B,D,E,F}A-C-B=5(比上面的A-B=6要小)替换B的权值为更小的A-C-B=5A-C-D=6A-C-E=7A-C-U中其他顶点=∞其中A-C-B=5最短3选入B,此时S={A,C,B}此时最短路径A-A=0，A-C=3A-C-B=5以B为中间点，从A-C-B=5这条最短路径开始新一轮查找U={D,E,F}A-C-B-D=10(比上面的A-C-D=6大，不替换，保持D的权值为