算法导论习题

//在合并排序中对小数组采用插入排序 #include void main() {

void MERGE_SORT(int a[],int p,int r,int k); int a[12]; //={3,0,1,10,9,5,4,12,7,8,2,6}; int k=3,n=12; int i,j,s; int tmp=0;

printf("请输入12个正整数：\n"); for(i=0;i

scanf("%d",&a[i]); for(i=0;i=i*3+1) {

if(a[s]

tmp=a[s],a[s]=a[s-1],a[s-1]=tmp; s--; } } } printf("第一步对4个长度3的子列表进行插入排序的结果为：\n"); for(i=0;i

void MERGE_SORT(int a[],int p,int r,int k) {

void MERGE(int a[],int p,int q,int r,int k); int q; if(p

void MERGE(int a[],int p,int q,int r,int k) { int n1=(q-p+1)*k,n2=(r-q)*k; int i,j,s; int *L=new int[n1]; int *R=new int[n2]; for(i=0;in1-1) a[s]=R[j++]; else if(j>n2-1) a[s]=L[i++]; else if(L[i]

//用分治法在数组中查找逆序对 #include void main() {

int count_inversion(int a[],int p,int r); int a[5]={5,4,3,2,1};

printf("数组的逆序对是%d个

\n",count_inversion(a,0,4)); }

int merge_inversion(int a[],int p,int q,int r) {

int n1=q-p+1; int n2=r-q;

int *L=new int[n1]; int *R=new int[n2]; int i,j,k,v;

for(i=0;i

for(k=p;k

if(i>n1-1)

a[k]=R[j++]; else if(j>n2-1) a[k]=L[i++]; else if(L[i]>R[j]) {

a[k]=R[j++]; v+=n1-i; } else

a[k]=L[i++]; }

delete L; delete R; return v; }

int count_inversion(int a[],int p,int r) {

int v=0,q; if(p

q=(p+r)/2;

v+=count_inversion(a,p,q); v+=count_inversion(a,q+1,r); v+=merge_inversion(a,p,q,r); }

return v; }

//用插入方法建堆 #include"stdio.h"

void HEAP_INCREASE_KEY(int a[],int i,int key) { int tmp; if(key>a[i-1]) a[i-1]=key; while(i>1&&a[i/2-1]

void MAX_HEAP_INSERT(int a[],int key,int heap_size) { heap_size+=1; a[heap_size-1]=0; HEAP_INCREASE_KEY(a,heap_size,key); }

void BUILD_MAX_HEAP(int a[],int lengh) { int heap_size=1; int i; for(i=2;i

void main() {

int j;

int a[10]={15,84,62,16,29,35,6,18,9,17}; BUILD_MAX_HEAP(a,10); for(j=0;j

}

#include"stdio.h"

void MAX_D_HEAPIFY(int a[],int i,int d,int heap_size) { int n=d,j,largest; int tmp; int *child=new int[n]; for(j=0;ja[i-1]) largest=child[0]; else largest=i; for(j=1;ja[largest-1]) largest=child[j]; } if(largest!=i) { tmp=a[largest-1],a[largest-1]=a[i-1],a[i-1]=tmp; MAX_D_HEAPIFY(a,largest,d,heap_size); } }

void BUILD_MAX_D_HEAP(int a[],int d,int heap_size) { int i,j; j=heap_size%d; if(j==0||j==1)

i=heap_size/d;

else i=heap_size/d+1;//由叶子节点求父节点有两种情况 for(i;i>=1;i--) MAX_D_HEAPIFY(a,i,d,heap_size); }

int EXTRACT_MAX(int a[],int d,int heap_size) { int tmp; tmp=a[heap_size-1];a[heap_size-1]=a[0];a[0]=tmp; heap_size--; MAX_D_HEAPIFY(a,1,d,heap_size); return a[heap_size]; }

void main() { int

a[20]={52,47,16,58,23,26,14,18,59,68,47,19,35,29,61,82,74,75,98,81}; // int b[18]={25,11,15,9,8,17,21,40,18,11,10,20,14,15,19,21,7,10}; int d=5,j,largest; BUILD_MAX_D_HEAP(a,5,20); // BUILD_MAX_D_HEAP(b,5,18); for(j=0;j

largest=EXTRACT_MAX(a,5,20); for(j=0;j

/* for(j=0;j

#include"stdio.h"

void MAX_D_HEAPIFY(int a[],int i,int d,int heap_size)

{ int n=d,j,largest; int tmp; int *child=new int[n]; for(j=0;ja[i-1]) largest=child[0]; else largest=i; for(j=1;ja[largest-1]) largest=child[j]; } if(largest!=i) { tmp=a[largest-1],a[largest-1]=a[i-1],a[i-1]=tmp; MAX_D_HEAPIFY(a,largest,d,heap_size); } }

void BUILD_MAX_D_HEAP(int a[],int d,int heap_size) { int i,j; j=heap_size/d; if(j==0||j==1) i=heap_size/d; else i=heap_size/d+1;//由叶子节点求父节点有两种情况 for(i;i>=1;i--) MAX_D_HEAPIFY(a,i,d,heap_size); }

void HEAP_INCREASE_KEY(int a[],int i,int d,int key) { int tmp,j;

if(a[i-1]

a[i-1]=key; while(i>1) { if(i%d==0||i%d==1) j=i/d; else j=i/d+1; if(a[j-1]

void INSERT(int a[],int key,int d,int heap_size) { heap_size+=1; a[heap_size-1]=0;

HEAP_INCREASE_KEY(a,heap_size,d,key); }

void main() {

int

a[20]={52,47,16,58,23,26,14,18,59,68,47,19,35,29,61,82,74,75,98,81}; int j,s=0;

BUILD_MAX_D_HEAP(a,5,19);

for(j=0;j

INSERT(a,a[19],5,19); s=0;

printf("\n"); for(j=0;j

printf("%d,",a[j]); s+=1; if(s%6==0) printf("\n");

}

}

#include"stdio.h"

void MAX_D_HEAPIFY(int a[],int i,int d,int heap_size) { int n=d,j,largest; int tmp; int *child=new int[n]; for(j=0;ja[i-1]) largest=child[0]; else largest=i; for(j=1;ja[largest-1]) largest=child[j]; } if(largest!=i) { tmp=a[largest-1],a[largest-1]=a[i-1],a[i-1]=tmp; MAX_D_HEAPIFY(a,largest,d,heap_size); } }

void BUILD_MAX_D_HEAP(int a[],int d,int heap_size) { int i,j; j=heap_size/d; if(j==0||j==1)

i=heap_size/d;

else i=heap_size/d+1;//由叶子节点求父节点有两种情况 for(i;i>=1;i--) MAX_D_HEAPIFY(a,i,d,heap_size); }

void HEAP_DECREASE_KEY(int a[],int i,int d,int key,int heap_size) { if(a[i-1]>=key) a[i-1]=key;

MAX_D_HEAPIFY(a,i,d,heap_size); }

void main() {

int

a[20]={52,47,16,58,23,26,14,18,59,68,47,19,35,29,61,82,74,75,98,81}; int key=1,s=0,j;

BUILD_MAX_D_HEAP(a,5,20); for(j=0;j

printf("\n"); s=0;

HEAP_DECREASE_KEY(a,3,5,key,20); for(j=0;j

#include"stdio.h"

{ //int a[10]={6,4,12,7,9,11,5,13,18,8}; int a[10]={20,18,17,14,16,10,8,9,8,15}; int i=9,j; int heap_size;

void BULD_MAX_HEAP(int a[]); int HEAP_DELETE(int a[],int i); BULD_MAX_HEAP(a); heap_size=HEAP_DELETE(a,i); printf("删除第i个元素后的堆是：\n"); for(j=0;j

void BULD_MAX_HEAP(int a[]) {

void MAX_HEAPIFY(int a[],int j,int heap_size); int heap_size=10; int j; for(j=4;j>=0;j--) MAX_HEAPIFY(a,j,heap_size); printf("堆a是：\n"); for(j=0;j

void MAX_HEAPIFY(int a[],int j,int heap_size) { int left=2*(j+1); int right=2*(j+1)+1;//结点与数组下标之间要转换 int largest=0,temp; if(lefta[j]) largest=left-1; else

if(righta[largest]) largest=right-1; if(largest!=j) { temp=a[largest];a[largest]=a[j];a[j]=temp; MAX_HEAPIFY(a,largest,heap_size); } }

int HEAP_DELETE(int a[],int i) { int temp,key=a[9],key1=a[i-1]; int heap_size=10;

temp=a[9];a[9]=a[i-1];a[i-1]=temp; heap_size--; if(key>key1) { while(i>1&&a[i/2-1]

于i结点的值，则通过不断与父结点的比较 //来确它的位置 { temp=a[i/2-1],a[i/2-1]=a[i-1],a[i-1]=temp; i=i/2; } } else MAX_HEAPIFY(a,i-1,heap_size);//如果a[9]比i结点的值要小，则从i结点开始堆维护 return heap_size; }

//建立最小堆 #include"stdio.h"

void MIN_HEAPIFY(int a[],int i,int heap_size) { int small,tmp; int left=2*i,right=2*i+1; if(lefta[i-1]) small=left;

small=i; if(righta[small-1]) small=right; if(small!=i) { tmp=a[small-1],a[small-1]=a[i-1],a[i-1]=tmp; MIN_HEAPIFY(a,small,heap_size); } }

void BUILD_MIN_HEAP(int a[],int heap_size) { int i; for(i=(heap_size/2);i>=1;i--) MIN_HEAPIFY(a,i,heap_size); }

void HEAPSORT(int a[],int lengh) { int i,tmp; int heap_size=lengh;

BUILD_MIN_HEAP(a,heap_size); for(i=lengh;i>=2;i--) { tmp=a[i-1],a[i-1]=a[0],a[0]=tmp; heap_size--;

MIN_HEAPIFY(a,1,heap_size); } }

void main() { int a[10]={23,6,21,3,7,5,8,54,14,10}; int i; HEAPSORT(a,10); for(i=0;i

//PARTITION的最初版本 #include"stdio.h"

{ int x,tmp; int i,j; x=a[p-1]; i=p-1; j=r+1; while(1) { while(a[--j-1]>x); while(a[++i-1]

void QUICK_SORT(int a[],int p,int r) { int q; if(p

void main() { int i; int

a[20]={10,58,46,23,26,48,47,59,68,23,12,19,17,24,43,81,76,72,98,46}; QUICK_SORT(a,1,20); for(i=0;i

/*对插入排序来说，当其输入已“几乎”排好序时，运行时间是很快的。在实践中， 可以充分利用这一特点来改善快速排序的运行时间。当在一个长度小于k的子数组上

调用快速排序时，不让他做任何排序就返回。当顶层的快速排序调用返回后，堆对整个数

组运行插入排序来完成排序过程。证明这一排序算法的期望运行时间是O(nk+nlg(n/k))。 在理论上和实践中，应如何选择k?*/ #include"stdio.h"

int PARTITION(int a[],int p,int r) { int i=p-1,j; int x,tmp; x=a[r-1]; for(j=p;j

void QUICK_SORT(int a[],int p,int r,int k) { int q; if(r-p>k) { q=PARTITION(a,p,r); QUICK_SORT(a,p,q-1,k); QUICK_SORT(a,q+1,r,k); } }

void INSERT_SORT(int a[],int length) { int i,j; int tmp; for(i=1;i0&&a[j-1]>=a[j])

{

tmp=a[j-1],a[j-1]=a[j],a[j]=tmp; j--; } } }

void QUICK_INSERT_SORT(int a[],int length,int k) { if(length>k) { QUICK_SORT(a,1,length,k); INSERT_SORT(a,length); } else INSERT_SORT(a,length); }

void main() { int i,k=5; int

a[20]={10,58,46,23,26,48,47,59,68,23,12,19,17,24,43,81,76,72,98,46};

QUICK_INSERT_SORT(a,20,k); for(i=0;i

/*考虑对PARTITION过程做这样的修改：从数字A中随机的选出三个元素，并围绕着三个数的

中数（即这三个元素的中间值）对它们进行划分。求出以a的函数形式表示的、最坏情况中

a:a(1-a)划分的近似概率。*/ #include"stdio.h" #include"stdlib.h"

int PARTITION(int a[],int p,int r) { int i=p-1,j; int b[3],tmp,x; for(j=0;j

b[j]=(int)rand()%(r-p+1)+p; if(a[b[0]-1]>a[b[1]-1]) tmp=a[b[0]-1],a[b[0]-1]=a[b[1]-1],a[b[1]-1]=tmp; if(a[b[1]-1]>a[b[2]-1])

tmp=a[b[1]-1],a[b[1]-1]=a[b[2]-1],a[b[2]-1]=tmp; if(a[b[0]-1]>a[b[1]-1]) tmp=a[b[0]-1],a[b[0]-1]=a[b[1]-1],a[b[1]-1]=tmp; tmp=a[r-1],a[r-1]=a[b[1]-1],a[b[1]-1]=tmp; x=a[r-1]; for(j=p;j

void QUICK_SORT(int a[],int p,int r) { int q; if(p

void main() { int i; int

a[20]={10,58,46,23,26,48,47,59,68,23,12,19,17,24,

43,81,76,72,98,46}; QUICK_SORT(a,1,20); for(i=0;i

//随机化快速排序 #include"stdio.h" #include"stdlib.h"

int PARTITION(int a[],int p,int r) { int i=p-1,j; int x,tmp; x=a[r-1]; for(j=p;j

int RANDOMIZED_PARTITION(int a[],int p,int r) { int i; int tmp; i=(int)rand()%(r-p+1)+p; tmp=a[r-1],a[r-1]=a[i-1],a[i-1]=tmp; return PARTITION(a,p,r); }

void RANDOMIZED_QUICKSORT(int a[],int p,int r) { int q; if(p

RANDOMIZED_QUICKSORT(a,q+1,r); } }

void main() { int i; int

a[20]={10,58,46,23,26,48,47,59,68,23,12,19,17,24,43,81,76,72,98,46};

/* for(j=1;j

i=(int)rand()%7+4; printf("%4d",i); }*/

RANDOMIZED_QUICKSORT(a,1,20); for(i=0;i

#include"stdio.h"

int COUNTING_SORT(int a[],int b[],int k,int n,int x,int y) { int i; int *c=new int[k+1]; for(i=0;i

/* for(i=n-1;i>=0;i--)//i从n-1到0是为了不改变相同元素的相对顺序，基数排序的稳定性 {

b[c[a[i]]-1]=a[i];//这个地方要减一，

c[a[i]]表示a[i]在数组中的排序数，放在b数组中要减一 c[a[i]]--; }*/ return c[y]-c[x-1]; }

void main() { int

a[20];//={12,3,2,5,4,6,7,8,8,6,5,4,9,7,0,14,14,15,16,12},b[20]={0}; int b[20]; int i,k,s; printf("Input k:\n"); scanf("%d",&k); printf("Input 20 positive numbers ranged 0 to k:\n "); for(i=0;i

#include"stdio.h"

void COUNTING_SORT(int a[],int k,int n) { int i,tmp; int *c=new int[k+1]; for(i=0;i

for(i=n-1;i>0;i--) { if(i!=(c[a[i]]-1)) { tmp=a[i],a[i]=a[c[a[i]]-1],a[c[a[i]]-1]=tmp; c[a[i]]--; i++; } } }

void main() { int

a[20]={12,3,2,5,4,6,7,8,8,6,5,4,9,7,0,14,14,15,16,12}; int i,k;

// printf("Input k:\n"); // scanf("%d",&k);

// printf("Input 20 positive numbers ranged 0 to k:\n ");

// for(i=0;i

// scanf("%d",&a[i]);

COUNTING_SORT(a,20,20); // printf("The sorted numbers:\n"); for(i=0;i

#include"stdio.h"

void RADIX_SORT(int a[],int d[],int n) { int *c=new int[n+1]; int *b=new int[n]; int i; for(i=0;i

c[a[i]%n]++;

for(i=1;i=0;i--) { b[c[a[i]%n]-1]=a[i]; c[a[i]%n]--; }

for(i=0;i=0;i--) { d[c[(b[i]/n)%n]-1]=b[i]; c[(b[i]/n)%n]--; } }

void main() { int n=10; int i; //int

a[10]={58,40,15,42,43,69,49,19,52,13},d[10]={0}; int *a=new int[n]; int *d=new int[n]; printf("Input n:\n"); scanf("%d",&n); printf("Input n positive numbers ranged 0 to n*n-1:\n"); for(i=0;i

//写出RANDOMIZED-SELECT的一个迭代版本 }

#include"stdio.h" #include"stdlib.h"

int RANDOMIZED_PARTITION(int a[],int p,int r) { int i,j,x; int tmp; i=rand()%(r-p+1)+p;

tmp=a[i-1],a[i-1]=a[r-1],a[r-1]=tmp; x=a[r-1]; i=p-1; for(j=p-1;j

int RANDOMIZED_SELECT(int a[],int p,int r,int i) { int q,k; while(1) { if(p==r) return a[p-1]; q=RANDOMIZED_PARTITION(a,p,r); k=q-p+1; if(i==k) return a[q-1]; else if(i

}

void main() { int

a[20]={45,28,17,46,39,58,49,14,13,98,6,75,40,36,30,9,4,54,71,25}; int i,key; key=RANDOMIZED_SELECT(a,1,20,2); printf("%d\n",key); }

#include"stdio.h"

int PARTITION(int a[],int p,int r) { int x,i,j,tmp; x=a[r-1]; i=p-1; for(j=p-1;j

int RANDOMIZED_SELECT(int a[],int p,int r,int i) { int q,k; if(p==r) return a[p-1]; q=PARTITION(a,p,r); k=q-p+1; if(k==i) return a[q-1]; else if(i

else RANDOMIZED_SELECT(a,q+1,r,i-k); }

void main() { int

a[20]={15,42,18,63,35,39,58,54,76,91,14,10,9,4,51,56,87,94,68,49}; int k=5,n=20,i; int *b=new int[k]; for(i=0;i

//最坏情况线性时间的选择。。。。利用中位数的中位数使快速排序时间性能更好 #include"stdio.h"

void INSERT_SORT(int a[],int p,int r) //对的数组a插入排序 { int i,j; int tmp; for(i=p;ip-1&&a[j]

int PARTITION(int a[],int p,int r) { int MID_NUMBER(int a[],int p,int r);

int i,j,x;

int tmp;

// if(r-p+1>5) // {

// i=MID_NUMBER(a,p,r);

// tmp=a[i-1],a[i-1]=a[r-1],a[r-1]=tmp; // } x=MID_NUMBER(a,p,r); i=p-1; for(j=p-1;j

int SELECT(int a[],int p,int r,int i) //寻找数组a的第p到r元素中第i小的元素 { int q,k; if(p==r) return a[p-1]; q=PARTITION(a,p,r); k=q-p+1; if(k==i) return a[q-1]; else if(i

int MID_NUMBER(int a[],int p,int r)//寻找数组a的从元素p到元素r的中位数 { int k=5,j; int group=(r-p+6)/k; //p到r个元素分成

group组，每组5个元素 int *b=new int[group]; for(j=1;j

void main() { int

a[20]={45,28,17,46,39,58,49,14,13,98,6,75,40,36,30,9,4,54,71,25}; int i,key; key=SELECT(a,1,20,6); printf("%d\n",key); }