算法设计与分析导论

《算法设计与分析导论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、代码实现第二章算法复杂度与问题下界1.直接插入排序：for(inti=1;i0&&a[j]high)return;if(a[mid]==k)returnmid;elseif(a[mid]

2、=right)return;inti=left,j=right;do{while(a[++i]a[f]);swap(a[i],a[j]);}while(i

3、[j]);swap(a[i],a[left]);quicksort(left,i-1);quicksort(i+1,right);5.堆排序：//下移voidshutdown(inti,int*a,intn){if(i*2+1>=n)return;intpos=i*2+1;if(i*2+2=0;i--)shut

4、down(i,a,n);}//排序voidheapsort(int*a,intn){build(a,n);for(inti=n;i>1;i--){swap(a[i-1],a[0]);shutdown(0,a,i-1);}}6.淘汰排序（树形选择排序）:voidtaotaisort(int*a,intn){int*b=newint[2*n-1];inti;//建树for(i=0;i=0;i--)b[i]=b[2*i+1]>b[i*2+2]?b[i*2+2]:b[i*2+1];//排序for(i

5、=0;i0){if(pos%2)b[(pos-1)/2]=b[pos]>b[pos+1]?b[pos+1]:b[pos];elseb[(pos-1)/2]=b[pos]>b[pos-1]?b[pos-1]:b[pos];pos=(pos-1)/2;}}}第三章贪心法1.Kruskal算法实现用到并查集和最小值堆：并查集：方便检验是否形成环最小值堆：方便选取权值最

6、小的边//定义边结构structedge{intstart,end;edge*next;intweight;edge(ints,inte,intw){start=s;end=e;weight=w;next=NULL;}};//邻接表方式表示图：根据边的数目重复调用buildvoidbuild(edge*graph[],intn,ints,inte,intw){if(graph[s]==NULL){graph[s]=newedge(s,e,w);return;}edge*temp=graph[s];while(temp->next!=NULL)temp=te

7、mp->next;temp->next=newedge(s,e,w);}//按秩合并与路径压缩的并查集intrank[100]={0};intparent[100]={0};//递归实现intfind(intx){if(parent[x]==0)returnx;returnparent[x]=find(parent[x]);}//迭代实现/*intfind(intx){intt;//for(;parent[t=x];x=parent[x],parent[t]=(parent[x]?parent[x]:x));//与上面的等价while(parent[x])

8、{t=x;x=parent[x];parent[t]=(paren