C++归并排序工具

Question

我想用C++和向量实现合并排序(考虑到输入的整数数是未知的)。我试图通过维基百科基于自下而上的实现思想来实现：http://en.wikipedia.org/wiki/Merge_sort。我给出了下面的代码。它可以通过编译，但在输入数字时会死掉。我不知道这里出了什么问题。

#include<iostream>
#include<vector>
using namespace std;

void BottomUpMerge(vector<int>, vector<int>::iterator, vector<int>::iterator, vector<int>::iterator, vector<int>);

void BottomUpSort(int n, vector<int> A, vector<int> B)
{
  int width;

  /* Each 1-element run in A is already "sorted". */

  /* Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted. */
  for (width = 1; width < n; width = 2 * width){
    vector<int>::iterator leftstart;

    /* Array A is full of runs of length width. */
    for (leftstart = A.begin(); leftstart <= A.end(); leftstart = leftstart + 2 * width){
        /* Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[] */
        /* or copy A[i:n-1] to B[] ( if(i+width >= n) ) */
        vector<int>::iterator rightstart;
        vector<int>::iterator rightend;
        if(leftstart+width >= A.end()){
            rightstart = A.end();
        }
        else{
            rightstart = leftstart+width;
        }
        if(leftstart+2*width >= A.end()){
            rightend = A.end();
        }
        else{
            rightend = leftstart+2*width;
        }

        BottomUpMerge(A, leftstart, rightstart, rightend, B);
    }

    /* Now work array B is full of runs of length 2*width. */
    /* Copy array B to array A for next iteration. */
    /* A more efficient implementation would swap the roles of A and B */
    A = B;
    /* Now array A is full of runs of length 2*width. */
    }
}

void BottomUpMerge(vector<int> A, vector<int>::iterator iLeft, vector<int>::iterator iRight, vector<int>::iterator iEnd, vector<int> B)
{
  vector<int>::iterator i0 = iLeft;
  vector<int>::iterator i1 = iRight;
  vector<int>::iterator j = B.begin() + distance(iLeft, A.begin()); //iterator for vector B

  /* While there are elements in the left or right lists */
  for (; j != B.end(); j++){
    /* If left list head exists and is <= existing right list head */
    if (i0 < iRight && (i1 >= iEnd || *i0 <= *i1)){
        *j = *i0;
        i0 = i0 + 1;
    }
    else{
        *j = *i1;
        i1 = i1 + 1;
    }
  }
}


int main(){
    int input;
    vector<int> numbers;    //input vector of numbers

    cout << "Please input the numbers to be sorted:" << endl;
    while(cin>>input){
        numbers.push_back(input);
    }

    int length = numbers.size();
    vector<int> sorted = numbers;   //work vector ensure has the same size of the original vector

    BottomUpSort(length, numbers, sorted);

    vector<int>::iterator it;
    for(it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << (*it) << '\n';
    }

    system("pause");
    return 1;
}

Answer 1

看这里：

BottomUpMerge(A, leftstart, rightstart, rightend, B);
...

void BottomUpMerge(vector<int> A, vector<int>::iterator iLeft, ...)
{
  ...

您通过值传递向量，这意味着BottomUpMerge正在处理它们的副本。但是迭代器仍然指向原始代码，接着就会变得很有趣。通过引用传递向量，至少其中一些问题应该会消失。

(在测试此函数时，在编写所有周围代码之前，您应该已经发现了这一点。绝不会添加到不起作用的代码中。)