推荐慕课网，刘宇波老师《算法与数据结构》
链接：http:
quickSort（优化） 课堂笔记
#include <cstdlib>
#include <iostream>
using namespace std;
template<
typename T>
void _quickSort3(T arr[],
int l,
int r){
swap(arr[l],arr[rand()%(r-l+
1)+l]);
T v = arr[l];
int lt = l;
int gt = r+
1;
int i = l+
1;
while(i < gt){
if(arr[i] < v){
swap(arr[i],arr[lt+
1]);
i++,lt++;
}
else if(arr[i] > v){
swap(arr[i],arr[gt-
1]);
gt--;
}
else
i++;
}
swap(arr[l],arr[lt]);
_quickSort3(arr,l,lt-
1);
_quickSort3(arr,gt,r);
}
template<
typename T>
void quickSort3(T arr[],
int n){
_quickSort3(arr,
0,n-
1);
}
int main()
{
int a[] = {
9,
8,
7,
6,
5,
4,
3,
2,
1};
int n1 =
sizeof(a)/
sizeof(a[
0]);
quickSort3(a,n1);
for(
int i =
0;i < n1;i++)
cout<<a[i]<<
" ";
cout<<endl;
return 0;
}
