quicksort有兩個(gè)版本寒随。左右指針版本（如下）和Hoare版本（較易但復(fù)雜度略輸）猖任。
以下代碼由松松提供啦租。致謝~
#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;
}
