例如:
已知数组a前半部分a[0,mid - 1],后半部分a[mid,num-1],现前半部分和后半部分均已排好序。要求:实现a数组的从小到大排序。空间复杂度为O(1).
1 #include <iostream>
2 using namespace std;
3
4 void PrintArry(int v[],int len)
5 {
6 for(int i = 0; i < len; i ++)
7 cout<<v[i]<<" ";
8 cout<<endl;
9 }
10
11 void MergeSort(int *v, const int len, const int mid)
12 {
13 int i, temp;
14 int left = 0, right = mid;
15
16 while (left < right && right < len)
17 {
18 while (v[left] < v[right]) {
19 ++ left;
20 }
21
22 temp = v[right];
23 for(i = right; i > left ; -- i) {
24 v[i] = v[i-1];
25 }
26 v[left] = temp;
27
28 //move the current right postion
29 ++ right;
30 }
31
32 }
33
34 int main(int argc, char **argv)
35 {
36 //int arry[]={1,3,5,7,9,3,4,6,8};
37 //int arry[]={1,3,5,7,9,7,8,9,9,11};
38 //int arry[] = {0,2,4,6,8,8,9,9,1000,1,3,5,7,10,11,12,14,16,18,20,21,23,25,45,68};
39 int v[] = {100,1,3,5,7,10,11,12,14,16,18,20,21,23,25,45,68};
40 int len = sizeof(v) / sizeof(int);
41 PrintArry(v, len);
42 MergeSort(v, len, 1);
43 PrintArry(v, len);
44 return 0;
45 }