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

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

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

  void merge(vector<int> &v1, int m, vector<int> &v2, int n) {
    int l = m - 1, r = n - 1, ins = m + n - 1; //ins: 插入位置
    while (l >= 0 && r >= 0) {
      if (v1[l] > v2[r]) {
        v1[ins] = v1[l];
        ins--;
        l--;
      } else {
        v1[ins] = v2[r];
        ins--;
        r--;
      }
    }
    while (r >= 0) {
      v1[ins] = v2[r];
      ins--;
      r--;
    }
  }

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

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 参考代码:

template <typename T> void print_vec(std::vector<T> &vec) {
  if (vec.size() == 0) {
    printf("{}\n");
    return;
  }
  printf("{");
  for (size_t i = 0; i < vec.size() - 1; i++) {
    cout << vec[i] << ", ";
  }
  cout << vec[vec.size() - 1];
  printf("}\n");
}

void swap(vector<int> &xs, int i, int j) {
  printf("swap %d,%d\n", xs[i], xs[j]);
  int tmp = xs[i];
  xs[i] = xs[j];
  xs[j] = tmp;
}

void wmerge(vector<int> &xs, int i, int m, int j, int n, int w) {
  while (i < m && j < n) {
    if (xs[i] < xs[j]) {
      printf("%d < %d \n", xs[i], xs[j]);
    } else {
      printf("%d >= %d \n", xs[i], xs[j]);
    }
    swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
    print_vec(xs);
  }
  while (i < m) {
    swap(xs, w++, i++);
    print_vec(xs);
  }
  while (j < n) {
    swap(xs, w++, j++);
    print_vec(xs);
  }
}

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

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

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

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