<vector>搞亂了我的Quicksort

我必須在C++中實現快速排序。我想爲我的快速排序算法使用std::vector，因爲我要從文本文件中讀取一定數量的負載，並且動態調整大小會很有用。然而，當我試圖用向量而不是數組來實現快速排序時，它不起作用，我無法解釋爲什麼。<vector>搞亂了我的Quicksort

另外，當我使用矢量實現時，我的一個函數停止打印到控制檯。我嘗試了一個數組的代碼，它工作正常，但我真的更喜歡使用一個向量。

下面的代碼：（注意，這僅僅是算法本身，沒有任何的文本文件的東西）

#include<iostream> 
#include<vector> 

using namespace std; 

void QuickSort(vector<double>, int, int); 
int splitVector(vector<double>, int, int); 
void swap(int &, int &); 

void main(){ 

    vector<double> myVector; 

    myVector.insert(myVector.end(), 2); 
    myVector.insert(myVector.end(), 6); 
    myVector.insert(myVector.end(), 5); 
    myVector.insert(myVector.end(), 9); 
    myVector.insert(myVector.end(), 3); 

    QuickSort(myVector, 0, myVector.size()-1); 

    for(vector<double>::iterator it = myVector.begin(); it != myVector.end(); it++) 
     cout<<*it<<" "; 

    cout<<endl<<endl; 

} 

void QuickSort(vector<double> list, int low, int high){ 

    if((high-low) > 1){ 

    int splitIndex = splitVector(list, low, high); 

    QuickSort(list, low, splitIndex-1); //left subarray 
    QuickSort(list, splitIndex+1, high); 


    } 

} 

int splitVector(vector<double> list, int low, int high){ 

    int left = low+1; 
    int right = high; 

    double pivot = list[low]; 

    while(left <= right){ 

     while(list[left] < pivot && left <= right){ 
       left++; 
     } 

     while(list[right] > pivot && right >= left){ 
       right--; 
     } 

     if((right - left) > 0){ 
       swap(list[left], list[right]); 
     } 

    } 

    swap(list[low], list[left-1]); 

    return left-1; //resting place of the pivot 

} 

void swap(int &first, int &second){  

    cout<<"Swapping..."<<endl<<endl; 

    int temp = first; 

    first = second; 

    second = temp; 

}

的swap()的「交換......」的部分是不部分輸出給我，但我測試了主函數本身，它似乎交換罰款向量元素。我對矢量來說很新，所以任何幫助都會很感激。

來源

2014-02-26 Radix

只是一個評論：你知道[std :: vector :: push_back（）]（http://en.cppreference.com/w/cpp/container/vector/push_back）的存在，對嗎？ – streppel

'myVector.push_back（2）'是對'myVector.insert（myVector.end（），2）'進行的操作。只是說。 –

@Streppel Nope。我認爲這很重要？ – Radix

你打算通過引用而不是值來傳遞你的向量，所以原來可以改變：vector<double>& list而不是vector<double> list。

此外，我強烈建議不要使用標準容器名稱，如list作爲參數名稱。

來源

2014-02-26 18:29:00

就是這樣。我認爲矢量會像數組一樣通過引用自動傳遞，但我想我應該完成我的研究。謝謝！ – Radix

@Radix：說數組通過引用傳遞是不正確的。由於C++數組在技術上是指向某個內存位置的指針，因此即使無法修改指針本身（即指向它的_which_位置），也可以修改該位置。如果它通過引用傳遞，您將能夠修改指針本身。 –

@VioletGiraffe你當然是對的。我想我正在引用傳遞引用的功能含義，而不是實際的內存方面。 – Radix

<vector>搞亂了我的Quicksort

回答

相關問題