我最喜欢的快速排序算法之一-白红宇

这是别人自学的，很厉害的，图还画的很好，注释写的也很详细，太赞了！

补充一点方便以后学习巩固：

快速排序是另一个分而治之排序算法。归并排序的重点在于合并，快速排序的重点在于分

对于一个数组，起始为lo，结束为hi，轴点为pivot。通过每次选取不同的轴点，将轴点移动至某一位置，使得满足下述条件。

那么如何分呢？重点在于寻找轴点轴点需要满足的条件：其左侧元素都比其小，右侧元素都要比其大

转自：https://yq.aliyun.com/articles/680896?spm=a2c4e.11163080.searchblog.145.531c2ec1tDGVbS&do=login&accounttraceid=d9bd2178-2d75-4147-bc5f-a2075143e318

这是一篇自学文章,如果有错误地方请及时指出

基本思想就是,确定一个在数组中的值,这个值可以将数组分裂为两部分,然后这两部分再分别找到那个中间值,然后再分别按照中间值在切分数组,直到最后不可切分了,也就排序完成了,如下图

67f7eb76a52df8935e01d29e07c2debbab931217

好了下面将是一次排序的大概流程图

ecf8c9a0626b3c623276c4fe6770d87e3b24510c

JAVA代码实现：

public static void main(String[] args) {  int[] arrs = {7,12,3,5,8,15,9,6,6,6,6,19,-2};  quickSort(arrs,0,arrs.length - 1);  System.out.println(Arrays.toString(arrs));}private static void quickSort(int[] arrs, int l, int r) {  if (l < r){      //index就算返回回来的分割点      int index = getindex(arrs,l,r);      //有了分割点就知道怎么分割两段数据序列了      quickSort(arrs,l,index-1);      quickSort(arrs,index+1,r);  }} private static int getindex(int[] arrs, int l, int r) {  int base = arrs[l]; //取第一个值做base值  //保证不判断过头  while (l < r){      //arrs[r] > base 只要比base大的值就继续找,找到比base小的或者相等的      //就不满足条件就可以确定值的下标了      while (l < r && arrs[r] >= base){          //进来就代表比base大          r --;      }      //到这就算找到<=base的值了,然后赋值给left      arrs[l] = arrs[r];      //开始寻找比base大的值,流程跟上一个while一样      while (l < r && arrs[l] <= base){          l ++;      }      //到这就算找到>=base的值了,然后赋值个right      arrs[r] = arrs[l];  }  //然后将base值赋值给right  arrs[r] = base;  //返回这个分割点,即right  return r;}

这里是快速排序的改进版，参考邓俊辉老师讲授：

做出下列改进，根据L、G、U三者大小关系的不变性，将数组分为四个部分：

轴点最初还是选取a[0]，L左界是lo，L右界是mi，G左界是mi+1，G右界是k，U左界是k，U右界是hi。

对于元素x逐个与轴点比较，若小于归为L，若大于归为G。当G区间足够大时，平滑式移动会比较复杂，在此采用滚动式移动比较简便，只要将x与G[mi+1]进行交换。为何能交换呢？因为G中元素均比x大，L中元素均比x小，这一条件始终满足。

遍历完成时，区间U会根据与轴点的大小，分别归入L、G，U会被完全分解，最终消失。最后一步，候选轴点与L右界进行交换，候选轴点归位，名副其实。

如上所示可以归纳为：

watermark,type_ZmFuZ3poZW5naGVpdGk,shado

另一种改进版的快速排序方法实现：

int partition(int a[], int lo, int hi) {	swap(a[lo],a[lo+rand()%(hi-lo+1)]);//随机交换，避免最坏情况的发生 	int pivot = a[lo];	int mi=lo;	for(int i=lo+1;i<=hi;i++)//自左向右考察每个a[i] 		if(a[i]
     
       a[low..m–1], pivot, a[m+1..high]    	quickSort(a, low, m-1); // 递归地将左子阵列排序    	// a[m] = pivot 在分区后就被排序好了    	quickSort(a, m+1, high); // 然后将右子阵列排序  	}}