快速排序
严书上的快排是以最左边元素为枢纽的，如下：
#include <iostream> #include<algorithm> using namespace std; int Partition(int a[],int left,int right){ int p=a[left]; //传统快排 while(left<right){ while(a[right]>p&&left<right)right--; a[left]=a[right]; while(a[left]<p&&left<right)left++; a[right]=a[left]; } a[left]=p; return left; } void quicksort(int a[],int left,int right){ //快速排序 if(left<right){ int p=Partition(a,left,right); quicksort(a,left,p-1); quicksort(a,p+1,right); } } int main(){ int a[6]={5,7,6,8,3,1}; quicksort(a,0,5); for(int i=0;i<6;i++) cout<<a[i]<<" "; cout<<endl; return 0; }
注意在Partition函数里面利用了两个标杆左右同时遍历，方法巧妙
2.随机快速排序
实际上，如果原始序列本身就接近于有序，利用上面的快排效率和变低，因为枢纽没有把序列划分为两个长度接近的子区间，这时可以采用随机枢纽，只需要再上面的Partition函数前面生成一个区间范围内的随机数即可，这要用到srand（），和rand（）和time()几个函数，注意头文件的添加，得随机快速排序如下。
#include <iostream> #include<algorithm> #include<time.h> using namespace std; int Partition(int a[],int left,int right){ int r=rand()%(right-left+1)+left; swap(a[r],a[left]); //随机快排 int p=a[left]; //传统快排 while(left<right){ while(a[right]>p&&left<right)right--; a[left]=a[right]; while(a[left]<p&&left<right)left++; a[right]=a[left]; } a[left]=p; return left; } void quicksort(int a[],int left,int right){ //快速排序 if(left<right){ int p=Partition(a,left,right); quicksort(a,left,p-1); quicksort(a,p+1,right); } } int main(){ srand((unsigned) time(NULL)); int a[6]={5,7,6,8,3,1}; quicksort(a,0,5); for(int i=0;i<6;i++) cout<<a[i]<<" "; cout<<endl; return 0; }
