1 #include<stdio.h> 2 void insertsort(int *A,int p,int r){ 3 //插入排序 4 int i,j,k; 5 for(i=p;i<=r;i++){ 6 j=A[i];k=i; 7 while(k>p&&j<A[k-1]){ 8 A[k]=A[k-1]; 9 k--; 10 } 11 A[k]=j; 12 } 13 // for(i=p;i<=r;i++){ 14 // printf("%d\t",A[i]); 15 // } 16 // printf("\n"); 17 } 18 void MERGE(int *A,int p,int q,int r){ 19 //单步归并排序 20 int i,j,k; 21 int *B=malloc((r-p+1)*sizeof(int)); 22 i=p;j=q+1;k=0; 23 while(i<=q&&j<=r){ 24 if(A[i]<A[j]){ 25 B[k]=A[i]; 26 i++; 27 } 28 else{ 29 B[k]=A[j]; 30 j++; 31 } 32 k++; 33 } 34 while(i<=q){B[k]=A[i];i++;k++;} 35 while(j<=r){B[k]=A[j];j++;k++;} 36 for(i=p,k=0;i<=r;i++,k++){ 37 A[i]=B[k]; 38 // printf("%d\t",A[i]); 39 } 40 // printf("\n"); 41 } 42 void MERGE_InsertSORTUP(int *A,int p,int r,int k){ 43 //杂交体：插入归并排序， 44 int q; 45 if(p<r){ 46 q=(p+r)/2; 47 if((q-p+1)<=k) //当子数组长度≤k的时候就不再进行划分，而是对该子数组进行插入排序 48 insertsort(A,p,q); 49 else 50 MERGE_InsertSORTUP(A,p,q,k); 51 if((r-q)<=k) 52 insertsort(A,q+1,r); 53 else 54 MERGE_InsertSORTUP(A,q+1,r,k); 55 56 MERGE(A,p,q,r); 57 } 58 } 59 void main(){ 60 int i,k; 61 int length=100; 62 int *B=malloc(length*sizeof(int)); 63 for(i=0;i<length;i++){ 64 B[i]=rand()%100; //随机生成数组 65 printf("%6d",B[i]); 66 if((i+1)%10==0)printf("\n"); 67 } 68 printf("\n\n--------------------------我是分割线------------------------\n\n"); 69 k=5; //设置子数组长度为5 70 MERGE_InsertSORTUP(B,0,length-1,k); 71 for(i=0;i<length;i++){ 72 printf("%6d",B[i]); 73 if((i+1)%10==0)printf("\n"); 74 } 75 }
结果：
转载于:https://www.cnblogs.com/zzsf/p/3823562.html