分段錯誤（核心轉儲）錯誤與快速排序

Question

我在C++中執行Quicksort時遇到問題。 我不知道爲什麼我收到「分段錯誤（核心轉儲）」錯誤... 這是我的代碼。任何幫助將非常感激。謝謝！ 我也不太清楚該怎麼做基本案例，以及如何在需要合併時將左側數組，右側數組和右側數組合併到一個數組中。

void printVector(vector<int> ar, int ar_size); 

    void quickSort(vector <int> ar, int ar_size) { 
     int pivot = ar[0]; 
     vector <int> left(ar_size); 
     int leftcount = 0; 
     vector <int> right(ar_size); 
     int rightcount = 0; 

    for(int i = 0; i < ar_size; i++){ 
     if(ar[i] < pivot){ 
      left.push_back(ar[i]); 
      leftcount++; 
     } 
     if(ar[i] >= pivot){ 
      right.push_back(ar[i]); 
      rightcount++; 
     } 
    } 
    if(ar_size <= 2){ 
     printVector(left, leftcount); 
     cout << pivot; 
     printVector(right, rightcount); 
    } 
    if(leftcount>0){ 
    quickSort(left, leftcount); 
    } 
    if(rightcount>0){ 
    quickSort(right, rightcount); 
    } 

} 

void printVector(vector<int> ar, int ar_size){ 

     for(int i = 0; i<ar_size; i++){ 

     cout << ar[i] << " "; 

    } 
} 

int main(void) { 
    vector <int> _ar; 
    int _ar_size; 
cin >> _ar_size; 
for(int _ar_i=0; _ar_i<_ar_size; _ar_i++) { 
    int _ar_tmp; 
    cin >> _ar_tmp; 
    _ar.push_back(_ar_tmp); 
} 

quickSort(_ar, _ar_size); 

return 0; 
} 

Answer 1

算法「一般」是可以的，但這裏有很多問題。

首先，您可能需要reserve內存，而不是在每次迭代中創建向量中的ar_size元素。

其次，要在quickSort執行循環從int i = 1不int i = 0開始，因爲othewiseñ最大的元素總是會在vector<int> right，你會得到一個堆棧溢出。

第三，也是最後一次，您的打印/排列順序應該是這樣的：

if (leftcount>0) { 
    quickSort(left, leftcount); 
    if (ar_size == 1){ 
     printVector(left, leftcount); 
    } 
} 

cout << pivot << " "; 

if (rightcount>0) { 
    quickSort(right, rightcount); 
    if (ar_size == 1) { 
     printVector(right, rightcount); 
    } 
}