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
| //归并两个已排序的表,空间复杂性O(n)
void merge(int list[],int sorted[],int i,int m,int n){
//merge two sorted files : list[i]..list[m] and list[m+1]..list[n] to a sorted list sorted[i]..sorted[n]
int j,k,t;
j=m+1;//index for the second sublist
k=i;//index for the sorted list
while(i<=m && j<=n){
if(list[i] <= list[j])
sorted[k++]=list[i++];
else
sorted[k++]=list[j++];
}
//sorted[k]..sorted[n] = list[j]..list[n]
while(j<=n)
sorted[k++]=list[j++];
//sorted[k]..sorted[n] = list[i]..list[m]
while(i<=m)
sorted[k++]=list[i++];
}
void merge_pass(int list[],int sorted[],int n,int length){
//perform one pass of the merge sort.
//It merges adjacent(邻近) pairs of subfiles from list int sorted
//n is the number of list,length is the length of the subfile
int i,j;
for(i=0;i<=n-2*length;i+=2*length){
merge(list, sorted, i, i+length-1, i+2*length-1);
}
//#如果一段是正好可归并的数量而另一段则少于正好可归并的数量#
if(i+length < n){
merge(list, sorted, i, i+length-1, n-1);
} else {
for(j=i;j<n;j++){//#如果只剩下一段或者更少的数量#
sorted[j]=list[j];
}
}
}
//总归并次数log2 n,每遍归并时间O(n),所以O(nlogn)
//额外空间开销与待排文件的记录个数成比例
void iter_merge_sort(int list[],int n){
int length = 1;
// int extra[MAX_SIZE];
int extra[n];
while(length < n){
merge_pass(list, extra, n, length);
length *=2;
merge_pass(extra, list, n, length);
length *=2;
}
}
|