首页 > 代码库 > 再说快速排序
再说快速排序
快速排序作为排序算法中的战斗机，一直是排序算法里面用的最多也是考的最多的一个算法
已经证明，对n个元素进行排序，最优的算法也是需要NLogN的时间复杂度，而快速排序的时间复杂度就是NlogN，
所以快速排序是排序算法中最优算法中的一个，下面我们继续来探索一下神奇的快速排序算法吧
快速排序的核心思想：每次排序把每一个元素k移动到正确的位置，并且把小于k的元素都移动到k的左边，大于k的元素都移动到k的右边
待排序的数列x[]，长度为n
算法一：初始化k=x[m](m为待排序的第一个元素)，对于每一个元素x[i](i>m)，如果x[i]>=k，i++;如果x[i]<k,swap(x[i],x[++m])
代码如下：
void qsort1(int l,int h){ if(l>=h) return; int m=l; for(int i=l;i<=h;i++) { if(x[i]<x[l]) { int temp=x[i];x[i]=x[++m];x[m]=x[i]; } } int temp=x[l];x[l]=x[m];x[m]=x[l]; qsort1(l,m-1); qsort1(m+1,h);}
算法一对随机整数组很有效，但是对于n个相同元素的时候，其性能会急剧下降，因为每次都要花O(n)的时间来去掉一个元素，总共需要接近O(n2)的时间复杂度
于是诞生了双向靠拢的算法二，
void qsort2(int l,int h){ if(l>=h) return; int t=x[l],i=l,j=h; while(i<j) { while(i<j&&x[j]>t) j--; x[i]=x[j]; while(i<j&&x[i]<t) i++; x[j]=x[i]; } x[i]=t; qsort2(l,i-1); qsort2(i+1,h);}
算法二比算法一优化的地方是对于相同的元素，每次都可以把当前元素的位置定位在接近中间的位置，这使得总时间接近于O(NlogN)的时间复杂度
改进后的算法二虽然提高了对相等数列的效率，但对于已经排序好的升序来说，还是接近O(N2)的时间复杂度，原因是我们每次都是以第一个元素为划分
改进的算法三想法如下：swap(l,randint(l,h)) ,randint(l,h)保证产生一个[l,h]范围的整数即可
int randint(int l,int h){ srand(unsigned(time(NULL))); int temp=rand()%(u+1); return temp>l?temp:h-temp;}
这样之后，快速排序还有哪里可以改进呢？
我们可以发现快速排序话费大量的时间来排序很小的子数组，如果用插入排序之类的简单算法来排序这些很小的子数据，程序的子速度会更快
if(h-l<cutoff) return
如何确定cutoff的值是一个难点，这个可以通过实验来得出，比如把n固定为100000，然后对cutoff在[1,100]内的每个可能取值都运行一遍，比较运行时间
最后的算法四代码如下：
int randint(int l,int h){ srand(unsigned(time(NULL))); int temp=rand()%(u+1); return temp>l?temp:h-temp;}void qsort4(int l,int h,int cutoff){ if(l-h<cutoff) return; int r=randint(l,h); int t=x[r];x[r]=x[l];x[l]=t; t=x[l]; int i=l,j=h; while(i<j) { while(i<j&&x[j]>t) j--; x[i]=x[j]; while(i<j&&x[i]<t) i++; x[j]=x[i]; } x[i]=t; qsort4(l,i-1); qsort4(i+1,h);}void isort(int h){ for (int i = 0; i < h; ++i) { int temp=x[i];int j; for(j=i;j>0&&x[j-1]>temp;j--) { x[j]=x[j-1];count++; } x[j]=temp; }}qsort4(l,h,cutoff);isort(h);
再说快速排序