快排之双向扫描分区法
#include<iostream>
using namespace std;
int partition(int A[],int p,int r){
int pivot=A[p];
int left=p+1;
int right=r;
while(left<=right){
//left不停往右走，直到遇到大于主元的元素
while(A[left]<=pivot) left++; //循环退出时，left一定是指向第一个大于主元的位置
while(A[right]>pivot) right--; //循环退出时，right一定是指向最后一个小于等于主元的位置
if(left<right){
swap(A[right],A[left]);
}
}
//while退出时，两者交错，且right指向的是最后一个小于等于主元的位置，也就是主元应该待的位置
swap(A[p],A[right]);
return right;
}
void quickSort(int A[],int p, int r){
if(p<r){
int q=partition(A,p,r);
quickSort(A,p,q-1);
quickSort(A,q+1,r);
}
}
int main(){
int arr[]={1,6,2,3,4,8,11,3,9,4,2,5,3};
quickSort(arr,0,12);
for(int i=0;i<13;i++){
cout<<arr[i]<<" ";
}
return 0;
}
| 
转播
