我最喜欢的快速排序算法之一

  1. 云栖社区>
  2. 博客>
  3. 正文

我最喜欢的快速排序算法之一

sjynegh 2019-04-03 20:55:58 浏览338
展开阅读全文
  1. 这是别人自学的,很厉害的,图还画的很好,注释写的也很详细,太赞了!
  2. 补充一点方便以后学习巩固:
  3. 快速排序是另一个分而治之排序算法。归并排序的重点在于合并,快速排序的重点在于分
  4. 对于一个数组,起始为lo,结束为hi,轴点为pivot。通过每次选取不同的轴点,将轴点移动至某一位置,使得满足下述条件。
  5. 那么如何分呢?重点在于寻找轴点轴点需要满足的条件:其左侧元素都比其小,右侧元素都要比其大
  6. 转自:https://yq.aliyun.com/articles/680896?spm=a2c4e.11163080.searchblog.145.531c2ec1tDGVbS&do=login&accounttraceid=d9bd2178-2d75-4147-bc5f-a2075143e318
  7. 这是一篇自学文章,如果有错误地方请及时指出
  8. 基本思想就是,确定一个在数组中的值,这个值可以将数组分裂为两部分,然后这两部分再分别找到那个中间值,然后再分别按照中间值在切分数组,直到最后不可切分了,也就排序完成了,如下图 

 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三者大小关系的不变性,将数组分为四个部分:
20190112101956696.png


轴点最初还是选取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小,这一条件始终满足。
20190112102812425.png


遍历完成时,区间U会根据与轴点的大小,分别归入L、G,U会被完全分解,最终消失。最后一步,候选轴点与L右界进行交换,候选轴点归位,名副其实。
20190112103510571.png
如上所示可以归纳为:

 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]<pivot)//若[k]小于轴点,则将其 
			swap(a[++mi],a[i]);//与[mi]交换,L向右扩展 
	swap(a[lo],a[mi]);//候选节点归位(名副其实) 
	return mi;//返回轴点的秩 
} 
void quickSort(int a[], int low, int high) 
{
  	if (low < high) 
	{
    	int m = partition(a, low, high); // O(N)
    	// a[low..high] ~> a[low..m–1], pivot, a[m+1..high]
    	quickSort(a, low, m-1); // 递归地将左子阵列排序
    	// a[m] = pivot 在分区后就被排序好了
    	quickSort(a, m+1, high); // 然后将右子阵列排序
  	}
}


 

网友评论

登录后评论
0/500
评论
sjynegh
+ 关注