归并排序【参考数据结构教材】
最编程
2024-02-16 10:44:33
...
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 }