在C #中使用合并排序计数反转

Question

因此，我理解了使用合并排序对数组中的反转进行计数的一般思路。在合并过程中，您可以递归地计算左子数组和右子数组中的倒数。

这是我为此编写的一些代码。

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); 

}

我很难理解的是为什么在向其附加元素之前必须清除count_and_merge函数中的数组？有没有其他方法可以不清除数组？我问是因为我习惯于用数组[sorted_index]=left_subarry[left_index]编写合并排序

Answer 1

为什么必须先清除count_and_merge函数中的数组，然后再向其附加元素？

在所示示例中，这是必要的，因为您将元素附加在数组之后。但是，您希望数组保持相同长度，但进行排序。

我这样问是因为我习惯用数组[sorted_index]=left_subarry[left_index]编写合并排序

我看不出为什么你不能使用它来代替std：：vector：:p ush_back（）。数组中的原始内容并不重要，因为所需的信息包含在left_subarray和right_subarray中。因此，您可以直接覆盖到数组。事实上，如果你使用这个实现，你甚至不需要事先的std：：vector：：clear（）。