遞歸返回向量C++

嘿傢伙我試圖把這個javascript代碼轉換成C++。我正在做快速排序，一切都是直接減去最後一步。遞歸返回向量C++

function quickSort(arr) 
{ 
    //base case if the arr is 1 or 0 then return the array 
    if(arr.length === 1 || arr.length === 0) 
    { 
     return arr; 
    } 


    var pivotIndex = Math.floor(arr.length/2); 
    var pivotValue = arr[pivotIndex]; 

    var before = []; 
    var after = []; 

    for(var counter = 0; counter < arr.length; counter++) 
    { 
     if(counter === pivotIndex) 
      continue; 
     if(pivotValue <= arr[counter]) 
     { 
      before.push(arr[counter]) 
     } 
     else 
     { 
      after.push(arr[counter]) 
     } 
    } 
//this step I am having trouble rewriting in c++ 
    return quickSort(after).concat(pivotValue).concat(quickSort(before)); 

}

我很難重寫C++中的遞歸步驟。我不知道如何concat 2載體。我嘗試使用插入方法，但我不斷收到關於無效使用void表達式的錯誤。

vector<int> quickSort(vector<int> arr) 
{ 
    if(arr.size() == 1 || arr.size() == 0) 
    { 
     return arr; 
    } 

    int pivotIndex = arr.size()/2; 
    int pivotValue = arr[pivotIndex]; 

    vector<int> before; 
    vector<int> after; 


    //put values in before or after the piv 
    for(size_t counter = 0; counter < arr.size(); counter++) 
    { 
     if(counter == pivotIndex) 
      continue; 
     if(pivotValue <= arr[counter]) 
      before.push_back(arr[counter]); 
     else 
      after.push_back(arr[counter]); 
    } 

    return //????? not sure how to do this 

}

來源

2017-08-08 user1314272

使用多行嗎？ – Yakk

大聲笑確定這很好，我明白，但我的C++有點生疏，所以一個例子會很好 – user1314272

連接'v'和'v2'：'v.insert（v.end（），v2.begin（），v2）。端（））'。 – Jarod42

所以，你意識到，你的核心問題是「如何連接兩個vector的」，你找到了一個right answer: using insert。現在你的問題是關於你爲什麼得到「關於無效使用void表達式的錯誤。」（這是假設我的回答是，至少。）

那是因爲你很可能會試圖做類似如下：

return quickSort(after).insert(/* stuff */);

這是不對的。在JavaScript中，array.concat返回級聯數組。它的返回類型實際上是Array，所以這樣做return arr.concat(arr2)返回Array，因爲arr.concat將返回Array。此外，在JavaScript中，array.concat不會修改它所調用的數組，而是返回一個新數組。

但是在C++中，vector.insert (#4 in the reference) returns void。這意味着它什麼都不返回。因此，當您嘗試返回insert的結果時，您會收到關於無效使用void表達式的錯誤。此外，在C++中，vector.insert確實修改了它被調用的vector。

那麼你在這種情況下如何使用插入？

vector<int> quickSort(vector<int> arr) 
{ 
    // ... 

    // Sort `before` and `after` 
    before = quickSort(before); 
    after = quickSort(after); 

    // Modify `after` and return it. 
    after.push_back(pivotValue); 
    after.insert(after.end(), before.begin(), before.end()); 
    return after; 
}

注：我的代碼是不是最佳的，在C++重寫JS的想法也奇怪具體。我的回答是簡單地概述問題中提出的問題，不能給出一個很好的C++實現快速排序。

來源

2017-08-08 00:50:11 Clavin

要Concat的雙載體，可以使用std ::合併像：std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));

來源

2017-08-08 00:55:06 user8368461

遞歸返回向量C++

回答

相關問題