quicksort（双指针版本）

quicksort有两个版本。左右指针版本（如下）和Hoare版本（较易但复杂度略输）。
以下代码由松松提供。致谢~

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

template <class T>
int divide(vector<T>& a, int low, int high) {
    T k = a[low];
    do {
        while (low < high && a[high] >= k) high--;
        if (low < high) {
            a[low] = a[high];
            low++;
        }
        while (low < high && a[low] <= k) low++;
        if (low < high) {
            a[high] = a[low];
            high--;
        }
    } while (low != high);
    a[low] = k;
    return low;
}

template <class T>
void quickSort(vector<T>& a, int low, int high) {
    int mid;
    if (low >= high) {
        return ;
    }
    mid = divide(a, low, high);
    quickSort(a, low, mid-1);
    quickSort(a, mid+1, high);
}

template <class T>
void quickSort(vector<T>& a) {
    quickSort(a, 0, a.size()-1);
}

int main()
{
    vector<int> arr({1, 8, 2, 1, 7, 5, 3, 3, 2});
    for (int i = 0; i < arr.size(); i++) cout<<arr[i]<<' '; cout<<endl;
    quickSort(arr);
    for (int i = 0; i < arr.size(); i++) cout<<arr[i]<<' '; cout<<endl;

    return 0;
}