1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include<stdio.h>
#include<malloc.h>
void myprint(int *,int);
void merge(int* a, int p, int q, int r)
{
int s,t,k;
int *b;
int i;
b = (int*)malloc((r-p+1)*sizeof(int));
s = p;
t = q+1;
k = 0;
while ((s<=q)&&(t<=r))
if(a[s]<=a[t])
b[k++] = a[s++];
else
b[k++] = a[t++];
if(s == q + 1)
while (t<=r)
b[k++] = a[t++];
else
while (s<=q)
b[k++] = a[s++];
k = 0;
while (p<=r)
{
a[p++] = b[k++];
}
}
int main()
{
int N,j;
int *a = NULL;
printf("Please input the numbers:");
scanf("%d", &N);
a = (int* )malloc(N*sizeof(int));
for(j=0; j<N; j++)
{
scanf("%d",&a[j]);
}
int s,i;
int t = 1;
while(t<=N)
{
s = t; //s代表是被合并的数组大小,t代表的是合并之后的每一组的数组大小！
t = 2*s;
i = 0; //i代表要合并的下一组的首项的下标
while(i+t<=N)
{
merge(a,i,i+s-1,i+t-1);
i = i+t;
}
if ((i+s)<=(N-1)) // n-1 是最后元素的下标
{
merge(a,i,i+s-1,N-1);
}
}
myprint(a,N);
}
void myprint(int *a , int n){
int i;
for(i = 0; i < n; i++)
printf("%3d",a[i]);
printf("\n");
}
|
