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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
int a[1000];
/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge(int a[],int tmpA[],int L,int R,int RightEnd)
{
/* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
int LeftEnd;
int tmp;
LeftEnd=R-1;/* 左边终点位置 */
tmp=L;/* 有序序列的起始位置 */
while(L<=LeftEnd&&R<=RightEnd){
if(a[L]<a[R]){
tmpA[tmp]=a[L];/* 将左边元素复制到TmpA */
tmp = tmp+1;
L = L+1;
}
else{
tmpA[tmp]=a[R];/* 将右边元素复制到TmpA */
tmp = tmp+1;
R = R+1;
}
}
while(L<=LeftEnd){
tmpA[tmp]=a[L];/* 直接复制左边剩下的 */
tmp = tmp+1;
L = L+1;
}
while(R<=RightEnd){
tmpA[tmp]=a[R];/* 直接复制右边剩下的 */
tmp = tmp+1;
R = R+1;
}
}
/* length = 当前有序子列的长度*/
void Mergepass(int a[],int tmpA[],int n,int length)
{/* 两两归并相邻有序子列 */
int i;
int j;
i=0;
while(i<=n-2*length){
Merge(a,tmpA,i,i+length,i+2*length-1);
i = i + 2*length;
}
if(i+length<n){/* 归并最后2个子列----剩余的个数够一个length，不够两个length*/
Merge(a,tmpA,i,i+length,n-1);
}
else{/* 最后只剩1个子列---剩余的个数不够一个length*/
j = i;
while(j<n){
tmpA[j]=a[j];
j=j+1;
}
}
}
void MergeSort(int a[],int n)//稳定
{
int length;
int tmpA[1000];
length=1;/* 初始化子序列长度*/
while(length<n){
Mergepass(a,tmpA,n,length);
length=length*2;
Mergepass(tmpA,a,n,length);
length=length*2;
}
}
int main()
{
int size;
int i;
size = getint();
i = 0;
while(i<size){
a[i] = getint();
i=i+1;
}
MergeSort(a,size);
putarray(size,a);
putch(10);
return 0;
}
|
