C++合併排序工具

Question

我想用C++和vector實現合併排序（考慮輸入整數數量未知）。我試圖通過wikipedia：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正在處理把它們拷貝的傳遞的載體。但迭代者仍然指向原始文件，並且隨之而來的是快樂。通過引用傳遞向量，至少其中一些問題應該消失。

（你應該已經發現了這一點，當你在測試這個功能，你寫的所有周圍的代碼之前。絕不添加到代碼不起作用。）