例如:
已知数组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 }
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。
