时间戳

首页 > 解决方案 > 在 C++ 中使用合并排序计算反转

c++ - 在 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); 

}

我难以理解的是为什么在向count_and_merge函数附加元素之前需要清除函数中的数组？有没有其他方法可以在不清除数组的情况下做到这一点？我问是因为我习惯用array[sorted_index++] = left_subarry[left_index++]

标签： c++algorithmmergesort

解决方案

count_and_merge为什么在向函数中添加元素之前需要清除函数中的数组？

在所示示例中这是必要的，因为您在array. 但是，您希望array保持相同的长度但被排序。

我问是因为我习惯用array[sorted_index++] = left_subarry[left_index++]

我看不出你不能使用它而不是std::vector::push_back(). 中的原始内容array并不重要，因为所需的信息包含在left_subarray和中right_subarray。因此，您可以直接覆盖到array. 事实上，如果你使用这个实现，你甚至不需要std::vector::clear()事先。

推荐阅读