快速排序

2020-04-19

字数统计: 923字 | 阅读时长≈ 3分

简介

快速排序，可能是应用最为广泛的排序算法，它实现简单，适合于各种不同输入数据，并且一般来讲比其他排序算法都快很多，并且是原地排序(只需要一个很小的辅助栈)，将长度为N的数组排序所需的时间和NlgN成正比

基本原理：将一个数组分为两个子数组，将两部分独立排序，当两子数组都有序时，整个数组也就自然有序了，不需要归并子数组。

快速排序与归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。

算法主要步骤：

从数组中跳出一个元素，称为基准；
重新排列数组，所有元素比基准值小的就放到基准的前面，所有比基准值大的就放到基准的后面，与基准相同的可以放到任一边
分别对基准两边的元素按照这个步骤再次排序，最后就能得到两边有序的数组，整体上就是有序数组了

具体分析

动图演示

strategy

算法实现与分析

public class QuickSort{

	public static void sort(Comparable[] a){
		sort(a,0,a.length-1);
	}

	//对a[lo,hi]范围的元素进行快速排序
	private static void sort(Comparable[] a,int lo, int hi){
		//如果数组元素数量小于等于1，就直接返回
		if(lo>=hi){
			return ;
		}

		//将a[lo,hi]中选取一个元素，以此元素将a[lo,hi]进行切分，并返回切分后此元素的索引值
		int j = partition(a,lo,hi);
		sort(a,lo,j-1);
		sort(a,j+1,hi);
	}

	private static int partition(Comparable[] a,int lo, int hi){
		//将数组切分为 a[lo,i-1],a[i],a[i+1,hi]三部分
		int i = lo, j = hi+1;

		//选取 传入数组范围的第一个元素作为分界元素
		Comparable v = a[lo];

		//开始遍历数组传入范围的其他元素，将它们按照与分界元素的大小关系摆放位置
		while(true){

			//i从lo+1开始向右遍历元素，如果元素比v小，就不动,如果i到达右边界就结束循环
			while(less(a[++i],v)){
				if(i==hi){
					break;
				}
			}
			//j从hi开始向左遍历元素，如果元素比v大，就不动,如果i到达右边界就结束循环
			while(less(v,a[--j])){
				if(j==lo){
					break;
				}
			}

			//经过上面两个while语句，如果能到达这里，那么a[i]一定比v大，a[j]一定比v小
			if(i>=j){
				//如果两个指针已经相逢，代表所有元素都已经被遍历过了，可以结束循环了
				break;
			}

			//交换a[i] 与 a[j]的元素位置
			exch(a,i,j);
		}

		//当循环结束
		//必定是i>=j
		//而此时必定是 a[i]>=v,a[j]<=v
		//所以j其实已经到了所有元素比v小的区域，此时交换 a[lo]与a[j]
		//v就到了索引j的位置，原元素到了左半区域首部，此时左半区域仍然全都小于v，右半区域也都大于v
		//划分成功,返回j，也就是此时分界元素v的索引
		exch(a,lo,j);
		return j;
	}
}

结论：将长度为N的无重复数组排序，快速排序平均需要 ~ 2NlnN次，约等于 1.39NlgN次比较

参考

本文作者： xczll
本文链接： https://xczllgit.github.io/2020/04/19/algorithm/2020-04-19-quickSort/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！