LANSGANBS

With a determined mindset, no obstacle is insurmountable.

统计加载中...

公告

如需添加友链，可以在任意文章下评论，并留下网站名称,链接,介绍和头像链接。

关于本站

1106 字

6 分钟

分治思想（归并排序）

2025-08-25

2025-09-26

算法竞赛

算法与数据结构

统计加载中...

分治思想（归并排序）#

0. 引入#

分治（Divide and Conquer）= 分 → 治 → 合
- 分：把大问题拆成规模更小、形式相同的子问题；
- 治：递归地解决每个子问题；
- 合：把子问题的答案合并，得到原问题答案。
归并排序是分治思想的经典案例：它的“合”步骤是把两个有序段“拉链式”合并。

直观例子（升序）：

把区间 [l..r] 二分成 [l..mid] 和 [mid+1..r]；
分别排好左段、右段；
用双指针合并这两个有序段。

归并排序性质一览：

时间复杂度： $O(n log n)$
额外空间： $O(n)$
具有稳定性

1. 从“合并两个有序段”开始#

“拉链式合并”

1
// 合并两个有序数组 A, B 到 C（都升序）
2
vector<int> merge_two(const vector<int>& A, const vector<int>& B) {
3
  vector<int> C;
4
  C.reserve(A.size() + B.size());
5
  size_t i = 0, j = 0;
6
  while (i < A.size() && j < B.size()) {
7
    if (A[i] <= B[j]) C.push_back(A[i++]);   // 用 <= 保证稳定性
8
    else              C.push_back(B[j++]);
9
  }
10
  while (i < A.size()) C.push_back(A[i++]);
11
  while (j < B.size()) C.push_back(B[j++]);
12
  return C;
13
}

2. 归并排序1#

1
void merge_sort(vector<int>& a, int l, int r, vector<int>& tmp) {
2
  if (l >= r) return;
3
  int mid = l + (r - l) / 2;
4

5
  merge_sort(a, l, mid, tmp);
6
  merge_sort(a, mid + 1, r, tmp);
7

8
  // 小优化：如果两个段已经衔接有序，跳过合并
9
  if (a[mid] <= a[mid + 1]) return;
10

11
  int i = l, j = mid + 1, k = l;
12
  while (i <= mid && j <= r) {
13
    if (a[i] <= a[j]) tmp[k++] = a[i++];     // <= 保证稳定
14
    else              tmp[k++] = a[j++];
15
  }
16
  while (i <= mid) tmp[k++] = a[i++];
17
  while (j <= r)   tmp[k++] = a[j++];
18
  for (int x = l; x <= r; ++x) a[x] = tmp[x];
19
}

3. 归并排序2#

1
void merge_sort_iter(vector<int>& a) {
2
  int n = (int)a.size();
3
  vector<int> tmp(n);
4
  for (int len = 1; len < n; len <<= 1) {
5
    for (int l = 0; l < n; l += (len << 1)) {
6
      int mid = min(l + len - 1, n - 1);
7
      int r   = min(l + (len << 1) - 1, n - 1);
8
      if (mid >= r) continue;                 // 右段不存在
9
      int i = l, j = mid + 1, k = l;
10
      while (i <= mid && j <= r) {
11
        if (a[i] <= a[j]) tmp[k++] = a[i++];
12
        else              tmp[k++] = a[j++];
13
      }
14
      while (i <= mid) tmp[k++] = a[i++];
15
      while (j <= r)   tmp[k++] = a[j++];
16
      for (int x = l; x <= r; ++x) a[x] = tmp[x];
17
    }
18
  }
19
}

4. 复杂度#

时间复杂度： $T(n) = 2T(\frac{n}{2}) + O(n) → O(n log n)$ $T (n) = 2 T (\frac{n}{2}) + O (n) \to O (n l o g n)$
- 递归树每层都处理 n 个元素，共约 $logn$ 层。
空间复杂度： $O(n)$ 额外空间存放临时数组；递归版另有 $O(log n)$ 栈。

5. 应用一：逆序对计数（分治在“合并阶段统计”）#

题意（如：洛谷 P1908、POJ 2299）

逆序对：i < j 且 a[i] > a[j] 的有序对个数。

6. 应用二：小和问题#

定义

对每个 a[i]，统计它右侧有多少元素 ≥ a[i]，贡献 a[i] × 这个数量；求总贡献。

合并思路

当 a[i] <= a[j] 时，a[i] 对右段当前 j..r 的所有元素都满足 ≥ a[i]，一次性贡献 $(r - j + 1) \times a[i]$ 。

7. 应用三：最大子段和（分治合并信息）#

设计四个量

sum：区间总和；
lmax：以左端点开头的最大前缀和；
rmax：以右端点结尾的最大后缀和；
best：区间内的最大子段和。

合并法则

sum = L.sum + R.sum
lmax = max(L.lmax, L.sum + R.lmax)
rmax = max(R.rmax, R.sum + L.rmax)
best = max(L.best, R.best, L.rmax + R.lmax)

8. 链表归并排序#

为什么链表适合归并

归并只需要顺序前进指针，不依赖随机访问；
快排/堆排对链表并不友好。

代码

1
struct ListNode {
2
  int val;
3
  ListNode* next;
4
  ListNode(int v): val(v), next(nullptr) {}
5
};
6

7
ListNode* merge_lists(ListNode* a, ListNode* b) {
8
  ListNode dummy(0);
9
  ListNode* tail = &dummy;
10
  while (a && b) {
11
    if (a->val <= b->val) { tail->next = a; a = a->next; }
12
    else                  { tail->next = b; b = b->next; }
13
    tail = tail->next;
14
  }
15
  tail->next = a ? a : b;
16
  return dummy.next;
17
}
18

19
ListNode* split_mid(ListNode* head) {
20
  ListNode* slow = head;
21
  ListNode* fast = head->next;
22
  while (fast && fast->next) {
23
    slow = slow->next;
24
    fast = fast->next->next;
25
  }
26
  ListNode* right = slow->next;
27
  slow->next = nullptr;
28
  return right;
29
}
30

31
ListNode* merge_sort_list(ListNode* head) {
32
  if (!head || !head->next) return head;
33
  ListNode* right = split_mid(head);
34
  ListNode* L = merge_sort_list(head);
35
  ListNode* R = merge_sort_list(right);
36
  return merge_lists(L, R);
37
}

9. 多路归并与外部排序概念#

k 路归并：有 k 个有序序列，合并成一个有序序列。
做法：小根堆维护每个序列的当前最小元素，弹出后推进该序列下一个。
复杂度： $O(n log k)$ 。

1
struct Item {
2
  int val, i, j; // val 值；来自第 i 段的第 j 个
3
  bool operator>(const Item& other) const { return val > other.val; }
4
};
5

6
vector<int> k_merge(const vector<vector<int>>& arrs) {
7
  priority_queue<Item, vector<Item>, greater<Item>> pq;
8
  for (int i = 0; i < (int)arrs.size(); ++i)
9
    if (!arrs[i].empty()) pq.push({arrs[i][0], i, 0});
10
  vector<int> res;
11
  while (!pq.empty()) {
12
    auto [v, i, j] = pq.top(); pq.pop();
13
    res.push_back(v);
14
    if (j + 1 < (int)arrs[i].size()) pq.push({arrs[i][j + 1], i, j + 1});
15
  }
16
  return res;
17
}

分治思想（归并排序）

https://lansganbs.cn/posts/算法竞赛/分治思想归并排序/

作者

LANSGANBS

发布于

2025-08-25

许可协议

CC BY-NC-SA 4.0

模拟与暴力枚举

递推与递归