STL vector实现快速排序

解题思路:递归+双指针

注意事项: vector索引必须用int, 不能用size_t

参考代码:

#include<iostream>
#include<vector>
using namespace std;

void swap(vector<int> &vec, int l, int r)
{
    int tmp = vec[l];
    vec[l] = vec[r];
    vec[r] = tmp;
}

void quicksort(vector<int> &vec, int left, int right)
{
    if (left >= right)
        return;
    size_t p = left;    // pivot
    size_t i = left;
    size_t j = right;
    while (i<j) {
        while (i<j && vec[p]<=vec[j])
            j--;
        while (i<j && vec[i]<=vec[p])
            i++;
        swap(vec, i, j);
    }
    swap(vec, p, i);
    quicksort(vec, left, i-1);
    quicksort(vec, i+1, right);
}

int main()
{
    int n;
    cin >> n;
    vector<int> vec(n);
    while (n--)
        cin >> vec[vec.size()-1-n];
    quicksort(vec, 0, vec.size()-1);
    for (vector<int>::const_iterator it = vec.cbegin();
         it != vec.cend();
         ++it)
         cout << *it << " ";
    return 0;
}