合并两个有序的子序,要求空间复杂度为O(1) - legendmaner - 博客园
数组al[0,mid-1]和al[mid,num-1]是各自有序的,对数组al[0,num-1]的两个子有序段进行merge,得到al[0,num-1]整体有序。要求空间复杂度为O(1)。注:al[i]元素是支持'<'运算符的。
数组al[0,mid-1]和al[mid,num-1]是各自有序的,对数组al[0,num-1]的两个子有序段进行merge,得到al[0,num-1]整体有序。要求空间复杂度为O(1)。注:al[i]元素是支持'<'运算符的。
/* 2 数组a[begin, mid] 和 a[mid+1, end]是各自有序的,对两个子段进行Merge得到a[begin , end]的有序数组。 要求空间复杂度为O(1) 3 方案: 4 1、两个有序段位A和B,A在前,B紧接在A后面,找到A的第一个大于B[0]的数A[i], A[0...i-1]相当于merge后的有效段,在B中找到第一个大于A[i]的数B[j], 5 对数组A[i...j-1]循环右移j-k位,使A[i...j-1]数组的前面部分有序 6 2、如此循环merge 7 3、循环右移通过先子段反转再整体反转的方式进行,复杂度是O(L), L是需要循环移动的子段的长度 8 */
void Reverse(int *a , int begin , int end ) //反转 13 { 14 for(; begin < end; begin++ , end--) 15 swap(a[begin] , a[end]); 16 } 17 void RotateRight(int *a , int begin , int end , int k) //循环右移 18 { 19 int len = end - begin + 1; //数组的长度 20 k %= len; 21 Reverse(a , begin , end - k); 22 Reverse(a , end - k + 1 , end); 23 Reverse(a , begin , end); 24 } 25 26 // 将有序数组a[begin...mid] 和 a[mid+1...end] 进行归并排序 27 void Merge(int *a , int begin , int end ) 28 { 29 int i , j , k; 30 i = begin; 31 j = 1 + ((begin + end)>>1); //位运算的优先级比较低,外面需要加一个括号,刚开始忘记添加括号,导致错了很多次 32 while(i <= end && j <= end && i<j) 33 { 34 while(i <= end && a[i] < a[j]) 35 i++; 36 k = j; //暂时保存指针j的位置 37 while(j <= end && a[j] < a[i]) 38 j++; 39 if(j > k) 40 RotateRight(a , i , j-1 , j-k); //数组a[i...j-1]循环右移j-k次 41 i += (j-k+1); //第一个指针往后移动,因为循环右移后,数组a[i....i+j-k]是有序的 42 } 43 } 44 45 void MergeSort(int *a , int begin , int end ) 46 { 47 if(begin == end) 48 return ; 49 int mid = (begin + end)>>1; 50 MergeSort(a , begin , mid); //递归地将a[begin...mid] 归并为有序的数组 51 MergeSort(a , mid+1 , end); //递归地将a[mid+1...end] 归并为有序的数组 52 Merge(a , begin , end); //将有序数组a[begin...mid] 和 a[mid+1...end] 进行归并排序 53 }
接着又网上搜索工作,找到一个block swapping.
Read full article from 合并两个有序的子序,要求空间复杂度为O(1) - legendmaner - 博客园