無盡的循環，而分裂一個向量

我想實現MergeSort作爲一項家庭作業。我得到了一個名爲MergeSort的函數，它接受一個輸入向量。然後，我得到了分割和合並功能。無盡的循環，而分裂一個向量

我知道MergeSort是如何工作的，而且我已經在Java中多次實現了，但是我一直使用數組，並且我沒有太多關於指針和引用的經驗。

這裏是我到目前爲止，

void Split(const std::vector<int>& input, std::vector<int>* output1, std::vector<int>* output2) { 



    std::cout << "In split function" << std::endl; 
    // this just prints the values in my vector 
    for (int i = 0; i < input.size(); i++) { 
     std::cout << input[i] << ", "; 
    } 
    std::cout << std::endl; 

    if (input.size() > 1) { 


     int i = 0; 
     int j = input.size(); 

     while (i <= j) { 
      output1->push_back(input[i]); 
      i++; 


      if (i != j) { 
       output2->push_back(input[j]); 
       j--; 
      } 
     } 



     std::vector<int> left= {}; 
     std::vector<int> right = {}; 

     Split(*output1, &left, &right); 
     Split(*output2, &left, &right); 
    } 
} 

void MergeSort(std::vector<int>* input){ 
    std::vector<int> output1= {}; 
    std::vector<int> output2 = {}; 
    std::cout << "Starting mergesort" << std::endl; 
    Split(*input, &output1, &output2); 

}

我也有我不希望包括因爲它不相關的我的問題是合併函數。

現在，我的代碼編譯，但它陷入了一個無限循環，並給我一個段錯誤。

我有一個調用與所述值的歸併功能的主要功能：{3,5，1，2，9,4}

Split函數被調用，則這只是印刷到stdout直至終止：

In split function 3, 5, 1,

爲什麼我被陷在這個循環？

來源

2017-09-14 Human Cyborg Relations

'輸入[J]基礎情況''與J = input.size（）'由一個超過界限... –

你用1分鐘Stephan打敗了我。 –

正如評論指出的，這個數組的索引是錯誤的。

int i = 0; 
int j = input.size();

正因爲如此，你的循環最終產生output1是{3, 5, 1}，然後將其送入Split(...)，生產{3, 5, 1}，直到再次遞歸導致賽格故障。

int i = 0; 
int j = input.size() - 1;

這將導致output1陣列實際上收縮{3, 5}，導致終止在if(input.size() > 1)

來源

2017-09-14 19:47:37 lcs

我修正了'j'，但現在它無限循環{3，5}，然後給我一個段錯誤。 –

無盡的循環，而分裂一個向量

回答

相關問題