第一段代码参考数据结构教材：清华大学《数据结构教程》（第3版）李春葆等编著。
数据结构教程（第三版）学习指导
作者：李春葆
图书详细信息：
ISBN：9787302193753
定价：25元
印次：1-4
装帧：平装
印刷日期：2011-7-22
本段代码含自顶向下、自底向上两种归并排序的算法：
1 #include<stdio.h> 2 #include<stdlib.h> 3 4 #include<time.h> 5 6 7 //merge()完成一次合并（两个子段合并为一个序列） 8 void merge(int *r,int *temp,int low,int mid,int height); 9 //mergePass()函数完成一趟归并排序.(即对整个序列的若干个子段中两两相邻的子段进行合并) 10 void mergePass(int *r,int *temp,int length,int n); 11 void mergeSort1(int *r,int n);//自底向上的归并排序 12 13 //mergeSortDC()对r[low]~r[height]进行自顶向下的归并排序 14 void mergeSortDC(int *r,int *temp,int low,int height); 15 void mergeSort2(int *r,int n);//对数r进行自顶向下的归并排序 16 17 int main() 18 { 19 int *a,*b,*temp,n,i; 20 scanf("%d",&n); 21 a=(int *)malloc(sizeof(int)*n); 22 b=(int *)malloc(sizeof(int)*n); 23 temp=(int *)malloc(sizeof(int)*n); 24 srand((unsigned int)time(0)); 25 for(i=0;i<n;i++) 26 { 27 b[i]=a[i]=rand()%100+1; 28 printf("%d ",a[i]); 29 if((i+1)%5==0) printf("\n"); 30 } 31 printf("\n"); 32 33 mergeSort1(a,n); 34 for(i=0;i<n;i++) 35 { 36 printf("%d ",a[i]); 37 if((i+1)%5==0) printf("\n"); 38 } 39 printf("\n"); 40 41 mergeSort1(b,n); 42 for(i=0;i<n;i++) 43 { 44 printf("%d ",b[i]); 45 if((i+1)%5==0) printf("\n"); 46 } 47 printf("\n"); 48 49 return 0; 50 } 51 /*----------------------------------------- 52 函数名称：merge 53 函数功能：实现一次归并，即：把r数组的两个有序的子段r[low]~r[mid]和 54 r[mid+1]~r[height]合并成为一个有序的序列。 55 参数说明： 56 *r ：要做归并排序的数组 57 *temp：归并排序过程中的临时数组 58 low：需要合并的序列1的起始位置 59 mid：需要合并的序列1的结束位置 60 由此可计算需要合并的序列2的起始位置（mid+1） 61 height ：需要合并的序列2的结束位置 62 -------------------------------------------*/ 63 void merge(int *r,int *temp,int low,int mid,int height) 64 { 65 int i=low,j=mid+1,k=0;//i是左子段的下标，j是右子段的下标，k是临时空间temp的下标 66 while(i<=mid&&j<=height)//在左子段和右子段均未扫描完时循环 67 { 68 if(r[i]<=r[j]) 69 { 70 temp[k++]=r[i++];//将左子段的记录往临时空间temp数组存放 71 } 72 else 73 { 74 temp[k++]=r[j++];//将右子段的记录往临时空间temp数组存放 75 } 76 } 77 while(i<=mid)//将左子段剩余的记录往临时空间temp数组存放 78 { 79 temp[k++]=r[i++]; 80 } 81 while(j<=height)//将右子段剩余的记录往临时空间temp数组存放 82 { 83 temp[k++]=r[j++]; 84 } 85 for(k=0,i=low;i<=height;k++,i++)//将临时空间temp数组的数据复制回数组r中 86 { 87 r[i]=temp[k]; 88 } 89 } 90 /*---------------------------------------------- 91 函数名称：mergePass 92 函数功能：对数组r完成一趟归并排序，即：r数组被分为若干个长为length的小组。 93 对这若干个小组进行两两归并（调用merge()函数来对两个子段进行归并。） 94 数组r的记录个数为n，即：r[0]~r[n-1],各子段长度为length（最后一个子段 95 长度可能小于length。），则当前r[0]-r[n-1]共有(n/length)的上取整个 96 有序子表（子段），即r[0]~r[length-1],r[length]~r[2*length-1],…… 97 本函数调用merge()函数对这若干个子段两两归并。 98 参数说明： 99 *r：需要进行归并排序的数组 100 *temp：归并排序过程中的临时数组 101 length：当前这一趟归并过程中，每个子段的长度 102 n：数组r的记录个数 103 ------------------------------------------------*/ 104 void mergePass(int *r,int *temp,int length,int n) 105 { 106 int i; 107 for(i=0;i+2*length-1<n;i=i+2*length)//对长为length的两两相邻的子段进行归并 108 { 109 merge(r,temp,i,i+length-1,i+2*length-1); 110 } 111 if(i+length-1<n)//剩余两个子段，后者长度小于length 112 { 113 merge(r,temp,i,i+length-1,n-1);//归并剩余的两个子段 114 } 115 } 116 /*-------------------------------------------- 117 函数名称： mergeSort1 118 函数功能：自底向上的归并排序 119 本函数需要进行若干趟的归并（也即要调用mergePass()函数若干趟）。 120 具体的次数应该是在对数级数量（logn ） 。 121 参数说明： 122 *r：需要归并排序的数组r 123 n：数组r的记录个数 124 ----------------------------------------------*/ 125 void mergeSort1(int *r,int n) 126 { 127 int length; 128 int *temp=(int *)malloc(sizeof(int)*n); 129 for(length=1;length<n;length=length*2) 130 mergePass(r,temp,length,n); 131 free(temp); 132 } 133 /*-------------------------------------------- 134 函数名称： mergeSortDC 135 函数功能：对子段r[low]~r[height]进行自顶向下的归并排序。 136 上述自底向上的归并排序虽然效率较好，但可读性差。 137 下面的自顶向下归并排序的代码比较简洁。 138 过程如下：假设需要归并排序的子段是r[low]~r[height], 139 则递归归并步骤分为以下两个步骤： 140 （1）分解：将当前区间一分为二，即计算mid=(low+height)/2; 141 然后递归地对r[low]~r[mid]以及r[mid+1]~r[height]继续进行分解。 142 最终结束条件是子段长度都变为1（毕竟一个子段只有1个数据肯定就是有序的） 143 （2）归并：和分解的过程相反，将已排序的两个子段r[low]~r[mid]以及 144 r[mid+1]~r[height]归并为一个有序的子段r[low]~r[height]。 145 146 本函数递归分解，然后调用函数merge（）来合并被分解的两个子段。 147 参数说明： 148 *r:需要归并排序的数组 149 low和height： 对数组r的在区间low~height之间进行归并排序。 150 *temp:归并过程中需要使用的临时空间。 151 ----------------------------------------------*/ 152 void mergeSortDC(int *r,int *temp,int low,int height) 153 { 154 int mid; 155 if(low<height) 156 { 157 mid=low+(height-low)/2; 158 mergeSortDC(r,temp,low,mid); 159 mergeSortDC(r,temp,mid+1,height); 160 merge(r,temp,low,mid,height); 161 } 162 } 163 /*----------------------------------------------------- 164 函数名称：mergeSort2 165 函数功能：对数组r进行自顶向下的归并排序 166 参数说明: 167 *r:需要排序的数组r 168 n：数组r的元素个数 169 -------------------------------------------------------*/ 170 void mergeSort2(int *r,int n) 171 { 172 int *temp=(int*)malloc(sizeof(int)*n); 173 mergeSortDC(r,temp,0,n-1); 174 free(temp); 175 }
下面的这段代码来自刘汝佳的《算法竞赛入门经典》
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<time.h> 4 void merge_sort(int *A,int x,int y,int *T); 5 int main() 6 { 7 int n,*a,i,*t; 8 scanf("%d",&n); 9 a=(int *)malloc(sizeof(int)*n); 10 t=(int *)malloc(sizeof(int)*n); 11 srand((unsigned int)time(0)); 12 for(i=0;i<n;i++) 13 { 14 a[i]=rand()%91+10; 15 printf("%d ",a[i]); 16 if((i+1)%5==0) printf("\n"); 17 } 18 printf("\n"); 19 printf("\n"); 20 merge_sort(a,0,n,t); 21 for(i=0;i<n;i++) 22 { 23 printf("%d ",a[i]); 24 if((i+1)%5==0) printf("\n"); 25 } 26 printf("\n"); 27 return 0; 28 } 29 void merge_sort(int *A,int x,int y,int *T) 30 { 31 if(y-x>1) 32 { 33 int m=x+(y-x)/2; //划分 34 int p=x,q=m,i=x; 35 merge_sort(A,x,m,T); 36 merge_sort(A,m,y,T); 37 while(p<m||q<y) 38 { 39 if(q>=y||(p<m&&A[p]<=A[q])) T[i++]=A[p++]; 40 else T[i++]=A[q++]; 41 } 42 for(i=x;i<y;i++) A[i]=T[i]; 43 } 44 }
归并排序复杂度分析：
关于归并排序的优秀博客文章：
http://blog.csdn.net/cjf_iceking/article/details/7921443
http://blog.csdn.net/cjf_iceking/article/details/7920153
