c++ - 搞乱了我的快速排序

Question

我必须在 C++ 中实现快速排序。我想将 std::vector 用于我的快速排序算法，因为我将从文本文件中读取大量数字，动态调整大小会很有用。但是，当我尝试使用 vector 而不是数组实现快速排序时，它不起作用，我无法解释原因。

此外，当我使用 vector 实现时，我的一个函数停止打印到控制台。我用数组尝试了代码，它工作正常，但我真的更喜欢使用 vector 。

这是代码:(请注意，这只是算法本身，而不是任何文本文件内容)

#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() 的“Swapping...”部分对我来说没有输出，但我在 main 中测试了函数本身，它似乎在 swap 中交换元素 vector 罚款。我对 vector 还很陌生，所以非常感谢任何帮助。

Answer 1

您打算通过引用而不是值传递 vector ，以便可以更改原始 vector :vector<double>& list而不是 vector<double> list .

此外，我强烈建议不要使用标准容器名称，如 list作为参数名称。