优化原地归并排序:实现 O(1) 空间复杂度

88. Merge Sorted Array 中,因为 nums1 预留了空间

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

,相当于用了额外空间,使得我们能够直接向尾部插入大元素原地排序:

 1  void merge(vector<int> &v1, int m, vector<int> &v2, int n) {
 2    int l = m - 1, r = n - 1, ins = m + n - 1; // ins: 插入位置
 3    while (l >= 0 && r >= 0) {
 4      if (v1[l] > v2[r]) {
 5        v1[ins] = v1[l];
 6        ins--;
 7        l--;
 8      } else {
 9        v1[ins] = v2[r];
10        ins--;
11        r--;
12      }
13    }
14    while (r >= 0) {
15      v1[ins] = v2[r];
16      ins--;
17      r--;
18    }
19  }

然而在实际情况,我们面临的是这样的数组:

arr = [...2,5,6,1,2,3...]
          ^   ^ ^   ^
          l1  m l2  r

按照上面的算法:

// 比较 6 > 3,因此尾部插入 6 被覆盖
arr = [...2,5,6,1,2,6...]
          ^   ^ ^   ^
          l1  m l2  r

出问题了,3 被覆盖了。

自然可以通过额外临时空间解决。但这样每次要使用 n/2 的空间。加起来空间复杂度翻倍。

如何对其进行原地合并呢?交换吗?

// 6 > 3
arr = [...2,5,3,1,2,6...]
          ^   ^ ^   ^
          l1  m l2  r

不行,简单交换 会打乱顺序

移动吗?

// 6 > 3
arr = [...2,5,1,2,3,6...]
          ^   ^ ^   ^
          l1  m l2  r

也不是不行,但是这样导致每次操作移动一串数据,效率低下($O(n^2)$ )。(这种方法称为死板归并排序

经过一些资料的搜索,我发现这个问题并不简单。

高德纳的《计算机程序设计艺术》第三卷将这个问题作为习题提出。而刘新宇《算法新解》第 13 中解释了这个方法。

原地工作区排序原理

简而言之,就是利用未排序的部分作为工作区(即排序的临时操作区域)。数据宏观上呈现这样的变化:

+------------------------------------------+
|               未排序 1/1                 |
+------------------------------------------+

+---------------------+--------------------+
|      未排序 1/2      |     已排序 1/2      |
+---------------------+--------------------+

+----------+----------+--------------------+
| 已排序1/4 |   工作区  |     已排序1/2       |
+----------+----------+--------------------+

+----------+-------------------------------+
|   工作区  |           已归并3/4            |
+----------+-------------------------------+

每轮操作,未排序的部分数量呈指数衰减。时间复杂度是 $O(n)$。

它是如何避免覆盖问题呢?

总是对未排序部分的后⼆分之⼀排序,从⽽将已序结果交换到前⼀半,⽽使得新的⼯作区位于中间。这样就不断将⼯作区的⼤⼩减半,从 1/2 到 1/4 到 1/8……归并的规模不断下降。当⼯作区中只剩下⼀个元素时,我们⽆须继续排序,因为只含有⼀个元素的数组⾃然是已序的。归并只含有⼀个元素的数组等价于插⼊元素。实际上,我们可以使⽤插⼊排序来处理最后的⼏个元素

**注意下面是如何选取工作区的**
9 6 5 2 2 1 6
排序后半
--- 子问题:2 1 6 的排序
------- 排序后半
---------- 子问题:6 的排序,单个元素无需操作
------- 2 1 [6] // 方括号表示已排序的部分
------- 将 1 作为工作区,对 2 排序
---------- 子问题:2 的排序,单个元素无需操作
---------- [2] 1 [6]
---------- 将 [2] 归并到 [6]:交换 2 <-> 1
---------- 1 [2  6]
----------工作区只剩一个元素,交换法原地插入排序
------ [1 2 6] 子问题解决
9 6 5 2 [1 2 6]
--- 从 9 6 5 2 中选取工作区。由于长度为 4,4/2 = 2,因此选择 5, 2 作为工作区
--- 对 9 6 排序
------- 子问题:9 6 的排序。排序后半 6,无需操作。
-------- 工作区 9,交换法原地插入排序,得到 [6 9]
--- [6 9]
[6 9] 5 2 [1 2 6]
--- 将 5 2 作为工作区,归并排序 [6 9] 和 [1 2 6] **下面是归并的核心实现**

void wmerge(Key* xs, int i, int m, int j, int n, int w) {
    while (i < m && j < n)
        swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
    while (i < m)
        swap(xs, w++, i++);
    while (j < n)
        swap(xs, w++, j++);
}
下面是以此代码为原理的例子:
------ 两个分组的索引是 [i, m) ; [j,n); w 是工作区起始索引
------ [6 9] 5 2 [1 2 6]
------- ^i  mw    ^j    n
------- 6 >= 1,交换 w 与 j (5<->1), j++,w++
------ [6 9] 1 2 [5 2 6]
------- ^i     w    ^j
------- 6 >= 2,交换 w 与 j (2<->2), j++,w++
------ [6 9] 1 2 [5 2 6]
------- ^i        w   ^j
------- 6 >= 6,交换 w 与 j (5<->6), j++, w++
------ [6 9] 1 2 [6 2 5]
------- ^i          w  ^j
------- 此时 j 已经出界。i 中剩余与工作区交换.
------- 交换 2, 6
------ [6 9] 1 2 [6 2 5]
-------   ^i          w^j
------- 交换 5, 9
------ [2 9] 1 2 [6 6 5]
-------   ^i          w^j
------ [2 5] 1 2 [6 6 9]
-------     ^i          w^j
----此时从 [已排序][工作区][已排序],变成了 [工作区][已归并]
--- 2 5 [1 2 6 6 9]
--- 选取 5 作为工作区:
--- [2] 5 [1 2 6 6 9]
--- 重复上面的 merge 操作:
--- [2] 5 [1 2 6 6 9]
--- 2 >= 1 
--- swap 5,1
--- [2] 1 [5 2 6 6 9]
--- 2 >= 2 
--- swap 5,2
--- [2] 1 [2 5 6 6 9]
--- 2 < 6 
--- swap 5,2
--- [5] 1 [2 2 6 6 9]
--- swap 6,6
--- [5] 1 [2 2 6 6 9]
--- swap 6,6
--- [5] 1 [2 2 6 6 9]
--- swap 9,9
--- [5] 1 [2 2 6 6 9]
--- 即得到:
--- 5 [1 2 2 6 6 9]
工作区 5,只剩一个在工作区,简单插入即可:
--- [1 2 2 5 6 6 9]

读者可以自行测试,merge 参考代码:

 1template <typename T> void print_vec(std::vector<T> &vec) {
 2  if (vec.size() == 0) {
 3    printf("{}\n");
 4    return;
 5  }
 6  printf("{");
 7  for (size_t i = 0; i < vec.size() - 1; i++) {
 8    cout << vec[i] << ", ";
 9  }
10  cout << vec[vec.size() - 1];
11  printf("}\n");
12}
13
14void swap(vector<int> &xs, int i, int j) {
15  printf("swap %d,%d\n", xs[i], xs[j]);
16  int tmp = xs[i];
17  xs[i] = xs[j];
18  xs[j] = tmp;
19}
20
21void wmerge(vector<int> &xs, int i, int m, int j, int n, int w) {
22  while (i < m && j < n) {
23    if (xs[i] < xs[j]) {
24      printf("%d < %d \n", xs[i], xs[j]);
25    } else {
26      printf("%d >= %d \n", xs[i], xs[j]);
27    }
28    swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
29    print_vec(xs);
30  }
31  while (i < m) {
32    swap(xs, w++, i++);
33    print_vec(xs);
34  }
35  while (j < n) {
36    swap(xs, w++, j++);
37    print_vec(xs);
38  }
39}

这样,我们完成了归并排序。

时间复杂度:$O(n \log_{} n) $ (网上传的 $O(n^2)$ 复杂度原地归并,是因为使用了移动数组,而我们通过原地开辟工作区+交换,将其优化掉了! )

空间复杂度:$O(1)$(网上传的 $O(N)$ 复杂度,是因为 merge 开辟了临时数组,我们已经将其优化掉!)

有兴趣的可以搜索论文:Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola - Practical in-place mergesort