归并排序【参考数据结构教材】

  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 }