<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

回答

相关问题