首页 > 代码库 > 分治思想的应用之快速排序
分治思想的应用之快速排序
快速排序算法与归并排序很像,都是分治的思想。不同点在于归并排序算法是通过位置下区分两个区间,而快速排序算法是用值来区分两个区间。所以归并排序算法还需要合并的操作,而快速排序则不需要。
快速排序算法最核心的地方在于:在区间中选择一个值pivot,让大于pivot的都在它的一边,而让小于pivot的都在另一边。
private static int partititon(int[] a,int l,int r){ int idx = mid3(a,l,(l+r)/2,r); int pivot = a[idx]; //a[idx]的位置已经空了下来 int i=l,j=r; while(i<j){ while(i<idx&&a[i]<=pivot)i++; if(i<j){ a[idx]=a[i];idx=i; } while(j>idx&&a[j]>=pivot)j--; if(i<j){ a[idx]=a[j];idx=j; } } a[idx]=pivot; return idx; }
区间中选择pivot是有技巧的。一般取左中右三个位置的数中,大小排在中间的那个数。
private static int mid3(int[] a,int l,int m,int r){ return a[l]<a[m]? (a[m]<a[r]? m : a[l]<a[r]? r:l ): ( a[m]>a[r]? m : a[l]>a[r]?r:l); }
这个过程有点像填坑。首先选择pivot,把它的值空出来,它的位置记为idx。接下来就按照下面的步骤进行:
第一步:把idx左边的第一个大于pivot的数填到idx的位置,然后得到新的坑,记为idx。
第二步:把idx右边的第一个小于pivot的烽填到idx的位置,然后也得到新的坑,记为idx。
不停的重复以上两步,直到i>j。
然后就得到快速排序算法了,代码如下:
public static void quickSort(int[] a,int l,int r){ if(l<r){ int paridx = partititon(a,l,r); quickSort(a,l,paridx-1); quickSort(a,paridx+1,r); } }
非常简单。整个过程都没有明显的排序,却一直在排序。算法虽易,思想不易。且学且珍惜!
本文出自 “每天进步一点点” 博客,请务必保留此出处http://sbp810050504.blog.51cto.com/2799422/1556393
分治思想的应用之快速排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。