合并排序算法——merge sort

#include <stdio.h> #include <malloc.h> #include <limits.h> void init(int A[],int p,int r);//初始化数组 void print_A(int A[],int p,int r);//打印数组元素 void merge(int A[],int p,int q,int r);//合并排序算法 /************合并排序算法的实现******************/ int main() { int p,q,r; printf("合并排序算法的实现:\n"); printf("请输入p、q、r的值(输入格式1,12,13):"); scanf("%d,%d,%d",&p,&q,&r); printf("p=%d,q=%d,r=%d\n",p,q,r); int * A = (int*)malloc((r+1)*sizeof(int)); init(A,p,r); printf("待合并数组:\n"); print_A(A,p,r); printf("\n\n"); printf("合并排序算法的实现过程:\n"); merge(A,p,q,r); free(A);//释放动态数组空间 return 0; } /*************初始化数组****************************/ void init(int A[],int p,int r) { int i = p; printf("请输入数组元素：\n"); for(i;i<(r+1);i++) { scanf("%d",&A[i]); printf("A[%d]=%d",i,A[i]); printf("\n"); } printf("\n"); } /*****************************************************/ /*****************打印数组元素***********************/ void print_A(int A[],int p,int r) { for(p;p<(r+1);p++) printf("%d ",A[p]); printf("\n"); } /****************************************************/ /****************合并排序算法************************/ void merge(int A[],int p,int q,int r) { int n1 = q-p+1; int n2 = r-q; int * L = (int*)malloc((n1+1)*sizeof(int)); int * R = (int*)malloc((n2+1)*sizeof(int)); int i,j,k; for(i=0;i<n1;i++) L[i]= A[p+i]; for(j=0;j<n2;j++) R[j]=A[q+j+1]; L[n1]=INT_MAX;//设置边界，哨兵位； R[n2]=INT_MAX; i=0;j=0; for(k=p;k<=r;k++) { if(L[i]<=R[j]) { A[k]=L[i]; i++; } else { A[k]=R[j]; j++; } print_A(A,p,r); } free(L); free(R); } /****************************************************/