In place Merge(原地归并)

数组al[0,mid-1] 和 al[mid,num-1]，都分别有序。将其merge成有序数组al[0,num-1]，要求空间复杂度O(1)

思路：一般的归并是需要O(n)的空间，而这里要求空间复杂度为O(1)，也就是只能使用常熟级别的临时变量。而原地操作无非就是移动，关键是怎么移动。在编程珠玑中有一个旋转算法(旋转后k个元素到前面)，可以在这里起到关键性作用。见http://www.cnblogs.com/ivorfeng/archive/2013/05/12/3074822.html

因为数组al[0,mid-1] 和 al[mid,num-1]，都分别有序，我们要做的是将较小的元素(可能是连续的一片)插入到合理的位置中；不妨假设left 和right是两个有序数组中的下标，a[left] < a[right],首先要在左半部分找到第一个比a[right]大的下标newleft，接着在右半部分找到比a[newleft]小的下表newright，并记录right到newright所移动的步数move

In place Merge(原地归并) 如上图所示，最后就是将红色框中的元素进行右旋转move（这里为3）个元素。

代码如下：

 1 //翻转数组
 2 template <typename T>
 3 void Reverse(T *a, int size)
 4 {
 5     T tmp;
 6     for(int i = 0; i < size/2; ++i)
 7     {
 8         tmp = a[i];
 9         a[i] = a[size - i - 1];
10         a[size - i - 1] = tmp;
11     }
12 
13 }
14 //旋转
15 template <typename T>
16 void Rotate(T*a, int size, int pos)
17 {
18     Reverse(a, pos);
19     Reverse(a + pos, size - pos);
20     Reverse(a, size);
21 
22 }
23 template<typename T>
24 void InplaceMerge(T *a, int size, int mid)
25 {
26     int fir = 0;
27     int sec = mid;
28     int Move = 0;
29     while (fir < sec && sec < size)
30     {
31         while (fir < sec && a[fir] < a[sec])
32         {
33             ++fir;
34         }
35         Move = 0;
36         while ( sec < size && a[sec] < a[fir])
37         {
38             ++sec;
39             ++Move;
40         }
41         Rotate(a + fir, sec - fir, sec - fir - Move);
42         fir += Move;
43     }
44 }

这样空间复杂度主要是Reverse中用到，为O(1).

In place Merge(原地归并)

相关推荐