二路归并排序(MergeSort)

1 #include
2
3 // 将两个有序序列进行合并
4 void Merge(int arr[], int first, int mid, int last)
5 {
6 int i1 &＃61; first;
7 int i2 &＃61; mid &＃43; 1;
8 int m &＃61; mid;
9 int n &＃61; last;
10 int i3 &＃61; 0;
11
12 int *temp &＃61; new int[last - first &＃43; 1];
13
14 while(i1 <&＃61; m && i2 <&＃61; n)
15 {
16 if (arr[i1] < arr[i2])
17 temp[i3&＃43;&＃43;] &＃61; arr[i1&＃43;&＃43;];
18 else
19 temp[i3&＃43;&＃43;] &＃61; arr[i2&＃43;&＃43;];
20 }
21 while(i1 <&＃61; m)
22 temp[i3&＃43;&＃43;] &＃61; arr[i1&＃43;&＃43;];
23 while(i2 <&＃61; n)
24 temp[i3&＃43;&＃43;] &＃61; arr[i2&＃43;&＃43;];
25 for(i1&＃61;0; i1)
26 arr[first &＃43; i1] &＃61; temp[i1];
27
28 delete [] temp;
29
30 }
31
32 void MergeSort(int arr[], int first, int last)
33 {
34 if (first < last)
35 {
36 int mid &＃61; (first &＃43; last) / 2;
37 MergeSort(arr, first, mid);
38 MergeSort(arr, mid &＃43; 1, last);
39 Merge(arr, first, mid, last);
40 }
41 }
42
43 // 在主函数中测试
44 void main()
45 {
46 int arr[] &＃61; {9, 1, 6, 5, 7, 3, 8, 2, 4, 0};
47 MergeSort(arr, 0, 9);
48 // 输出排序后数组的内容
49 for(int i&＃61;0; i<10; i&＃43;&＃43;)
50 printf("%d ", arr[i]);
51
52 getchar();
53 }