c++ - 用C++中的合并排序计数反转

我正在研究我的前几项算法来构建我的C++技巧，现在我正在编写一个用归并排序计数倒排的方法。我已经设法得到了一个工作合并排序在一起，但我有一点困难，保持对倒转的数量你知道从这里去哪里吗在这样的递归算法中，如何跟踪逆运算的次数另外，在我的网络旅行中，我看到了两种不同的实现方法，并且发现大多数人都偏离了std：：vector方法，知道为什么吗谢谢你的帮助，我的代码如下！

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

vector<int> print(vector<int> input){

    for(int i=0; i<input.size(); i++){
        cout<<input[i]<<",";
    }
    cout<<endl;
    return input;
}


vector<int> merge(vector<int> left,vector<int> right){

    //set up some varibles
    vector<int> output;
    int i=0;
    int j=0;

    //loop through the lists and merge
    while(i<left.size() && j<right.size()){

        //push the smallest of the two to the vector output
        if(left[i]<=right[j]){
            output.push_back(left[i]);
            i+=1;
        }
        if(left[i]>right[i]){
            output.push_back(right[j]);
            j+=1;
        }
    }

    //push the remnants of the vectors to output
    for(i; i<left.size(); i++){
        output.push_back(left[i]);
    }

    for(j; j<right.size(); j++){
        output.push_back(right[j]);
    }

    return output;
}//end merge

vector<int> merge_sort(vector<int> input){
    //check the size of the vector
    if(input.size()<2){
        return input;
    }

    else{

    //int new vectors
    vector<int> left;
    vector<int> right;
    vector<int> output;

    //find the middle of the input vector
    int middle=(input.size())/2;

    //build the left vector
    for(int i=0; i<middle; i++){
        left.push_back(input[i]);
    }

    //build the right vector
    for(int i=middle; i<input.size(); i++){
        right.push_back(input[i]);
    }

    //make recursive calls
    left=merge_sort(left);
    right=merge_sort(right);

    //call merge
    output=merge(left,right);


    return output;
    }
}


int main()
{
    vector<int> output;
    vector<int> input;

    input.push_back(2);
    input.push_back(1);
    input.push_back(10);
    input.push_back(4);

    output=merge_sort(input);

    print(output);


}

最佳答案

好消息：从这里开始倒数很容易。
想想你的“合并”方法每次将左向量中的元素放入输出时，都不会更改其相对于右向量中元素的位置。另一方面，每次从右向量添加元素时，都将其放在“左向量中仍要处理的所有元素”之前，而之前则放在“它们”之后，即创建（left.size-i）“反转”。
如果需要的话，你可以通过归纳法来证明这一点。
所以答案很简单：向merge方法传递一个int*，每次从右向量中推一个元素时，它都会增加（left.size-i）。
编辑：工作代码示例

#include <iostream>
#include <vector>
// removed useless dependency math.h

using namespace std;

// void type -> does not return anything
void print (vector<int> input) {
    // range-based for loop (since C++ 11)
    // no brackets -> only one instruction in for loop
    for(int i : input)
        cout << i << ",";
}

vector<int> merge (vector<int> left, vector<int> right, int * inv_count) {
    vector<int> output;
    // multiple variable definition of the same type
    int i=0, j=0;

    // spaces around "<", after "while", before "{" for readability
    while (i < left.size() && j < right.size()) {

        // one-instruction trick again
        if (left[i] <= right[j])
            // i++ is evaluated to <previous value of i> and then increments i
            // this is strictly equivalent to your code, but shorter
            // check the difference with ++i
            output.push_back(left[i++]);
        // else because the two conditions were complementary
        else {
            output.push_back(right[j++]);
            // pointer incrementation
            *inv_count += (left.size() - i);
        }
    }

    // first field of for ommited because there is no need to initialize i
    for(; i < left.size(); i++)
        output.push_back(left[i]);

    for(; j < right.size(); j++)
        output.push_back(right[j]);

    return output;
}

vector<int> merge_sort (vector<int> input, int * inv_count) {
    // no-braces-idiom again
    // spaces around "<" and after "if" for readability
    if (input.size() < 2)
        return input;

    // no need for else keyword because of the return

    // multiple variable definition
    vector<int> left, right;

    int middle = input.size() / 2;

    // one-instruction for loop
    for(int i=0; i < middle; i++)
        left.push_back(input[i]);

    for(int i=middle; i < input.size(); i++)
        right.push_back(input[i]);

    // no need for intermediate variable
    return merge( merge_sort(left, inv_count),
                  merge_sort(right, inv_count),
                  inv_count);
}

// consistent convention : brace on the same line as function name with a space
int main () {
    // vector initialization (valid only since C++ 11)
    vector<int> input = {2, 1, 10, 4, 42, 3, 21, 7};

    int inv_count = 0;

    // No need for intermediate variables again, you can chain functions
    print( merge_sort(input, &inv_count) );

    // The value inv_count was modified although not returned
    cout << "-> " << inv_count << " inversions" << endl;
}

我修改了你的代码，包括了一些常用的C++习语。因为你使用了C++ 14标签，所以我也使用了仅供C++ 11使用的技巧。我不建议在任何地方都使用所有这些技巧，它们包含在这里，因为这是一个很好的学习体验。
我建议你在深入研究C++之前先阅读一些指针。
还要注意，这段代码并不是最优的：创建了太多的中间向量，而向量在这里并不有用，数组就足够了。但我会再留一次。

关于c++ - 用C++中的合并排序计数反转，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49091710/