算法导论习题

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

1、2-1：//在合并排序中对小数组采用插入排序#includevoidmain(){voidMERGE_SORT(inta[],intp,intr,intk);inta[12];//={3,0,1,10,9,5,4,12,7,8,2,6};intk=3,n=12;inti,j,s;inttmp=0;printf("请输入12个正整数：");for(i=0;i<12;i++)scanf("%d",&a[i]);for(i=0;i<=3;i++){for(j=i*3+1;j

2、3+3;j++){s=j;while(s>=i*3+1){if(a[s]

3、",a[i]);printf("");}voidMERGE_SORT(inta[],intp,intr,intk){voidMERGE(inta[],intp,intq,intr,intk);intq;if(p

4、i,j,s;int*L=newint[n1];int*R=newint[n2];for(i=0;in1-1)a[s]=R[j++];elseif(j>n2-1)a[s]=L[i++];elseif(L[i]

5、中查找逆序对#includevoidmain(){intcount_inversion(inta[],intp,intr);inta[5]={5,4,3,2,1};printf("数组的逆序对是%d个",count_inversion(a,0,4));}intmerge_inversion(inta[],intp,intq,intr){intn1=q-p+1;intn2=r-q;int*L=newint[n1];int*R=newint[n2];inti,j,k,v;for

6、(i=0;in1-1)a[k]=R[j++];elseif(j>n2-1)a[k]=L[i++];elseif(L[i]>R[j]){a[k]=R[j++];v+=n1-i;}elsea[k]=L[i++];}deleteL;deleteR;returnv;}intcount_inversion(inta[],intp,int

7、r){intv=0,q;if(pa[i-1])a[i-1]=key;while(i>1&&a[i/2-1]

8、1]){tmp=a[i/2-1],a[i/2-1]=a[i-1],a[i-1]=tmp;i=i/2;}}voidMAX_HEAP_INSERT(inta[],intkey,intheap_size){heap_size+=1;a[heap_size-1]=0;HEAP_INCREASE_KEY(a,heap_size,key);}voidBUILD_MAX_HEAP(inta[],intlengh){intheap_size=1;inti;for(i=2;i<=lengh;i++){MAX_HE