相对于快速排序来说，我们接触到的排序算法可能是冒泡排序和插入排序，然而当数据过多的时候，冒泡排序和插入排序的性能往往并不能满足我们的需求。这时候快速排序的优点就体现出来了，平均情况下快速排序的时间复杂度为$o(nlog_n)$，最坏的情况是$o(n^2)$。
快排的思路
快排的思路其实很简单，采用分治的策略。步骤如下
- 选择一个基准元素（pivot）
- 把比pivot小的放在pivot左边，把比pivot大的放在pivot右边
- 将pivot左边和pivot右边的序列重复步骤1，2（递归来实现）
QuickSort(A,L,R):
if(L>R) return;
newP=exchang(A,L,R)//步骤2
QuickSort(A，L，newP-1);
QuickSort(A,newP+1,R);
快排的C++实现
void quickSort(vector<int>&v,int L,int R){
if(L>R){
return;
}
int pivot=v[R];//定义基准元素，这里可以采取随机算法选择基准，从而避免最坏的时间复杂度
int left=L;
int right=R-1;
//将比pivot小的元素放在它左边，大的放在右边
while(left<right){
//注意，这一步到最后肯定是left=right
while(v[left]<pivot&&left<right) left++;
while(v[right]>=pivot&&left<right)right--;
swap(v[left],v[right]);
}
//对于1 2 3 5的情况，v[left]是小于pivot的，这个时候只要考虑L-left-1就行,left++就行，直接到最后一个数
//对于1 2 3 5 4的情况,v[left]是大于pivot的,这个时候需要考虑（L-left-1）以及（left+1，R）
//对于1 2 3 5 8 8 5的情况，v[left]等于pivot，这个情况同大于
if(v[left]>=pivot){
swap(v[left],pivot);
}else{
left++;
}
quickSort(v, L, left-1);
quickSort(v, left+1, v[R]);
}
增加随机性
为了防止产生最坏的时间复杂度，我们可以引入随机性的基准。这里只要产生一个随机的L-R中间的值，和R处的值做交换即可。
void randomQuickSort(vector<int>&v,int L,int R){
if(R-L==1) return;
int rindex=rand()%(end-begin);//随机产生一个0到end-begin-1之间的数
rindex=rindex+begin;
swap(v[R],v[rindex]);
quickSort(v,L,R);
}
