分治策略：归并排序与逆序对计算
目录
前言
在计算机科学的世界里，分治策略（Divide and Conquer）是一种优雅而强大的算法设计范式。它将复杂问题分解为若干个相同或相似的子问题，递归地解决这些子问题，最后合并子问题的解以得到原问题的解。这种"分而治之"的思想不仅贯穿于算法设计的各个领域，更是许多高效算法背后的核心逻辑。
今天，我们将深入探讨分治策略的两个经典应用：归并排序和逆序对计算。这两个问题看似不同，却共享着相同的分治基因，展现着这一策略的普适性和强大威力。
一、归并排序——分治的经典范例
1.1 归并排序的基本思想
归并排序是分治策略最直观的体现之一。它的核心思想非常简单：
(1). 分解：将待排序的数组从中间分成两半
(2). 解决：递归地对两个子数组进行排序
(3). 合并：将两个已排序的子数组合并成一个有序数组
这种递归分解的过程会一直持续到子数组只包含一个元素（此时自然是有序的），然后开始逐层合并。
1.2 归并排序的算法实现
#include <iostream>
#include <vector>
using namespace std;
// 合并两个已排序数组
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
vector<int> L(n1), R(n2);
// 复制数据到临时数组
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// 合并临时数组回原数组
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 归并排序主函数
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
// 递归排序左右两部分
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 合并已排序的两部分
merge(arr, left, mid, right);
}
// 归并排序的包装函数
void mergeSort(vector<int>& arr) {
if (arr.size() <= 1) return;
mergeSort(arr, 0, arr.size() - 1);
}
// 辅助函数：打印数组
void printArray(const vector<int>& arr) {
for (int num : arr) {
cout << num << " ";
}
cout << endl;
}1.3 归并排序的性能分析
归并排序的时间复杂度分析是理解分治策略效率的关键。我们可以通过递归树来分析：
递归深度：每次将数组分成两半，递归深度为 O(log n)
每层工作量：每层需要合并所有元素，工作量为 O(n)
总时间复杂度：O(n log n)
空间复杂度为 O(n)，因为需要额外的数组来合并子数组。与快速排序的原地排序不同，归并排序需要额外的存储空间，这是其代价。
1.4 归并排序的稳定性与适用场景
归并排序是稳定排序算法，即相等元素的相对顺序在排序后保持不变。这一特性在某些应用场景中非常重要，比如：
(1). 多关键字排序：先按次要关键字排序，再按主要关键字排序
(2). 数据库操作：保持记录的相对顺序
(3). 需要稳定排序的算法：如某些计算几何算法
此外，归并排序对于链表这种数据结构特别高效，因为链表的合并操作可以在 O(1) 的额外空间内完成。
二、逆序对问题
2.1 什么是逆序对？
在深入讨论逆序对的计算方法之前，让我们先明确什么是逆序对。
定义：对于一个数组 A = [a₁, a₂, ..., aₙ]，如果存在索引 i < j 且 A[i] > A[j]，则称 (i, j) 为一个逆序对（inversion pair）。
示例：数组 [2, 4, 1, 3, 5] 中的逆序对有：
(2, 1): 索引0的值2 > 索引2的值1
(4, 1): 索引1的值4 > 索引2的值1
(4, 3): 索引1的值4 > 索引3的值3
总共3个逆序对。
2.2 逆序对的应用意义
逆序对计数问题看似简单，却有着广泛的实际应用：
(1). 衡量数据混乱程度：逆序对数量可以作为数组"乱序程度"的量化指标
(2). 推荐系统：比较用户偏好排序与推荐排序的一致性
(3). 基因序列分析：在生物信息学中，衡量基因序列的相似性
(4). 协作过滤：评估用户评分的一致性
(5). 排序算法分析：某些排序算法（如冒泡排序）的交换次数等于逆序对数量
2.3 朴素方法的局限性
最直观的逆序对计算方法是检查所有可能的元素对：
long long countInversionsNaive(const vector<int>& arr) {
long long count = 0;
int n = arr.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
count++;
}
}
}
return count;
}这种方法的时间复杂度为 O(n²)，对于大规模数据（如 n=10⁶）来说完全不可行。我们需要更高效的算法。
三、分治法计算逆序对
3.1 算法灵感来源
观察到归并排序过程中有一个重要特性：当合并两个已排序的子数组时，我们可以高效地计算跨越这两个子数组的逆序对数量。
关键洞察：在合并过程中，如果左子数组的当前元素大于右子数组的当前元素，那么左子数组中该元素之后的所有元素也都大于右子数组的当前元素，这些都会形成逆序对。
3.2 分治算法设计
计算逆序对的分治算法遵循与归并排序相同的结构：
(1). 分解：将数组分成两半
(2). 解决：递归计算左半部分的逆序对和右半部分的逆序对
(3). 合并：在合并两个已排序子数组的过程中，计算跨越中点的逆序对
3.3 算法实现
#include <iostream>
#include <vector>
using namespace std;
// 合并并计算逆序对
long long mergeAndCount(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
long long inversions = 0;
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
// L[i] 到 L[n1-1] 的所有元素都与 R[j] 形成逆序对
inversions += (n1 - i);
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
return inversions;
}
// 分治计算逆序对
long long countInversionsMergeSort(vector<int>& arr, int left, int right) {
long long inversions = 0;
if (left < right) {
int mid = left + (right - left) / 2;
// 递归计算左右两部分的逆序对
inversions += countInversionsMergeSort(arr, left, mid);
inversions += countInversionsMergeSort(arr, mid + 1, right);
// 计算跨越两部分的逆序对
inversions += mergeAndCount(arr, left, mid, right);
}
return inversions;
}
// 计算逆序对的包装函数
long long countInversions(vector<int> arr) { // 传值以保护原数组
return countInversionsMergeSort(arr, 0, arr.size() - 1);
}3.4 算法正确性证明
为了理解为什么这个算法是正确的，我们需要考虑三种类型的逆序对：
(1). 左逆序对：两个元素都在左半部分
(2). 右逆序对：两个元素都在右半部分
(3). 跨越逆序对：一个元素在左半部分，另一个在右半部分
递归调用分别计算了左逆序对和右逆序对。在合并过程中，当发现 left[i] > right[j] 时，我们知道 left[i] 及其之后的所有元素都大于 right[j]，因此形成了 (len(left) - i) 个跨越逆序对。这样，三种类型的逆序对都被正确计数。
3.5 时间复杂度分析
与归并排序相同，该算法的时间复杂度为 O(n log n)，空间复杂度为 O(n)。这比朴素方法的 O(n²) 有了巨大的改进。
对于 n=10⁶ 的数据，朴素方法需要约 5×10¹¹ 次比较（假设每秒进行10⁸次比较，需要约5000秒），而分治方法只需约 2×10⁷ 次比较（约0.2秒）。
四、算法优化与变体
4.1 原地归并的优化
标准的归并排序需要额外的 O(n) 空间。我们可以通过一些技巧实现原地归并，将空间复杂度降低到 O(1)，但这通常以增加时间复杂度为代价。
// 原地合并的简化示例（不完全原地，但减少空间使用）
void mergeInPlace(vector<int>& arr, int left, int mid, int right) {
int i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
i++;
} else {
int value = arr[j];
int index = j;
// 向右移动元素
while (index > i) {
arr[index] = arr[index - 1];
index--;
}
arr[i] = value;
i++;
mid++;
j++;
}
}
}4.2 多路归并
对于某些特定场景，我们可以将二路归并扩展为多路归并（k-way merge），这在外部排序（如大数据处理）中特别有用。
4.3 逆序对计算的并行化
逆序对计算天然适合并行化处理，因为左右子数组的计算相互独立。C++17 引入了并行算法支持：
#include <execution>
#include <algorithm>
// 使用C++17并行排序的示例
void parallelMergeSort(vector<int>& arr) {
std::sort(std::execution::par, arr.begin(), arr.end());
}
// 注意：并行化逆序对计算需要更复杂的实现
// 因为跨越逆序对的计算需要串行处理4.4 树状数组解法
除了分治法，逆序对问题还可以使用树状数组（Fenwick Tree）或线段树在 O(n log n) 时间内解决，特别适用于需要频繁更新和查询的场景。
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
class FenwickTree {
private:
vector<int> bit;
int n;
public:
FenwickTree(int size) {
n = size;
bit.assign(n + 1, 0);
}
void update(int idx, int delta) {
while (idx <= n) {
bit[idx] += delta;
idx += idx & -idx;
}
}
int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= idx & -idx;
}
return sum;
}
};
long long countInversionsFenwick(const vector<int>& arr) {
// 坐标压缩
vector<int> sorted_arr = arr;
sort(sorted_arr.begin(), sorted_arr.end());
unordered_map<int, int> rank;
for (int i = 0; i < sorted_arr.size(); i++) {
rank[sorted_arr[i]] = i + 1; // 1-based index
}
FenwickTree bit(arr.size());
long long inversions = 0;
// 从后向前遍历
for (int i = arr.size() - 1; i >= 0; i--) {
int rank_idx = rank[arr[i]];
inversions += bit.query(rank_idx - 1); // 比当前元素小的已出现元素数量
bit.update(rank_idx, 1); // 标记当前元素已出现
}
return inversions;
}五、实际应用与案例分析
5.1 推荐系统中的相似度计算
在电商推荐系统中，用户对商品的点击序列可以看作一个排列。通过计算两个用户点击序列的逆序对差异，可以衡量他们的兴趣相似度。
Kendall Tau距离：基于逆序对计数的相似度度量
τ = 1 - 2 * (逆序对数) / (n*(n-1)/2)5.2 基因重排分析
在生物信息学中，基因重排是进化的重要机制。通过比较两个物种的基因顺序，计算将它们转换为彼此所需的最小逆序对数，可以推断物种间的进化距离。
5.3 算法竞赛实例
逆序对计算是算法竞赛中的经典问题。以LeetCode 315题"计算右侧小于当前元素的个数"为例：
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> result(n, 0);
vector<pair<int, int>> indexedNums; // (value, original index)
for (int i = 0; i < n; i++) {
indexedNums.push_back({nums[i], i});
}
mergeSort(indexedNums, 0, n - 1, result);
return result;
}
private:
void mergeSort(vector<pair<int, int>>& nums, int left, int right, vector<int>& result) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid, result);
mergeSort(nums, mid + 1, right, result);
merge(nums, left, mid, right, result);
}
void merge(vector<pair<int, int>>& nums, int left, int mid, int right, vector<int>& result) {
vector<pair<int, int>> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
int rightCount = 0;
while (i <= mid && j <= right) {
if (nums[i].first > nums[j].first) {
rightCount++;
temp[k++] = nums[j++];
} else {
result[nums[i].second] += rightCount;
temp[k++] = nums[i++];
}
}
while (i <= mid) {
result[nums[i].second] += rightCount;
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
for (int idx = 0; idx < temp.size(); idx++) {
nums[left + idx] = temp[idx];
}
}
};六、拓展与进阶
6.1 三维逆序对问题
将逆序对问题扩展到三维空间：给定三维空间中的点 (xᵢ, yᵢ, zᵢ)，计算满足 xᵢ < xⱼ, yᵢ < yⱼ, zᵢ < zⱼ 的三元组 (i, j, k) 数量。
这个问题可以通过分治策略结合树状数组或线段树在 O(n log² n) 时间内解决，是分治法的经典高阶应用。
6.2 在线逆序对计算
传统逆序对计算是离线的（需要全部数据）。在线逆序对问题要求在数据流中实时维护逆序对数量，每添加一个新元素就更新计数。
这可以通过平衡二叉搜索树或树状数组实现，每次插入的复杂度为 O(log n)。
6.3 外部排序中的逆序对
在大数据处理中，当数据无法完全装入内存时，需要使用外部排序。归并排序是外部排序的核心算法，而逆序对计算可以帮助评估数据的预排序程度，从而优化外部排序策略。
七、总结
分治策略是一种深刻而强大的算法设计思想，归并排序和逆序对计算完美地展示了这种思想的优雅和高效。通过将复杂问题分解为可管理的子问题，我们不仅能够设计出清晰的算法，还能获得优异的性能表现。
从归并排序的 O(n log n) 时间复杂度到逆序对计算的高效解法，我们看到分治策略如何将看似不同的两个问题统一在相同的框架下。这种统一性正是计算机科学之美的一部分——简单而强大的思想能够解决广泛而多样的问题。
理解和掌握分治策略不仅仅是学习几个算法，更是培养一种解决问题的思维方式。在面对新问题时，我们可以思考：这个问题能否分解？子问题是否更容易解决？解能否合并？这种思维模式将贯穿你的整个算法学习之旅，帮助我们在复杂问题面前找到清晰而高效的解决路径。
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
21
0- 0
已为社区贡献4条内容
所有评论(0)