C++归并排序统计逆序对时合并函数清空数组的原因及替代方案

核心思路 #

使用归并排序统计逆序对的核心逻辑分为两部分：

• 递归拆分原数组，分别统计左、右子数组内部的逆序对数量
• 合并两个已排序的子数组时，统计跨左右子数组的逆序对数量
  两部分相加即为当前数组的总逆序对数量。

原实现代码 #

int count_and_merge(vector<int>& array, const vector<int>& left_subarray, const vector<int>& right_subarray) {
    vector<int> merged {};
    array.clear();
    int left_index = 0, right_index = 0, sorted_index = 0;
    int inversions = 0;
    while(left_index < left_subarray.size() and right_index < right_subarray.size()) {
        if(left_subarray[left_index] <= right_subarray[right_index])
            array.push_back(left_subarray[left_index++]);
        else {
            array.push_back(right_subarray[right_index++]);
            inversions += left_subarray.size() - left_index;
        }
    }
    while(left_index < left_subarray.size()) array.push_back(left_subarray[left_index++]);
    while(right_index < right_subarray.size()) array.push_back(right_subarray[right_index++]);
    return inversions;
}

int count_inversions_and_sort(vector<int>& array) {
    if(array.size() <= 1) return 0;
    int n = array.size();
    vector<int> left_subarray(array.begin(), array.begin() + n / 2),
                right_subarray(array.begin() + n / 2, array.end());
    
    int left_subarray_inversions  = count_inversions_and_sort(left_subarray),
        right_subarray_inversions = count_inversions_and_sort(right_subarray);
    return left_subarray_inversions + right_subarray_inversions + count_and_merge(array, left_subarray, right_subarray); 
}

疑问解答 #

1. 为什么必须先执行array.clear()？ #

你当前的实现用push_back方法向array中添加元素，该方法会在数组的末尾追加新元素。如果不清空数组，array中还保留着拆分前的旧数据，合并后的新元素会追加在旧数据之后，最终得到的数组长度会是预期的2倍，内容也会包含错误的旧数据，导致上层递归逻辑出错。
你平时常用的array[sorted_index++] = xxx写法是直接覆盖数组对应位置的旧元素，不需要追加操作，自然不需要提前清空。

2. 无需清空数组的实现方式 #

存在无需清空的实现，就是采用你熟悉的下标赋值写法即可。进入count_and_merge时，array的长度刚好等于左右子数组的长度之和，足够容纳合并后的结果，直接覆盖原有位置的内容即可，示例代码如下：

int count_and_merge(vector<int>& array, const vector<int>& left_subarray, const vector<int>& right_subarray) {
    int left_index = 0, right_index = 0, sorted_index = 0;
    int inversions = 0;
    while(left_index < left_subarray.size() && right_index < right_subarray.size()) {
        if(left_subarray[left_index] <= right_subarray[right_index])
            array[sorted_index++] = left_subarray[left_index++];
        else {
            array[sorted_index++] = right_subarray[right_index++];
            inversions += left_subarray.size() - left_index;
        }
    }
    while(left_index < left_subarray.size()) array[sorted_index++] = left_subarray[left_index++];
    while(right_index < right_subarray.size()) array[sorted_index++] = right_subarray[right_index++];
    return inversions;
}

该版本完全去掉了clear操作和push_back调用，和常规归并排序的实现逻辑一致。

内容的提问来源于stack exchange，提问作者Mutating Algorithm