排序算法之快速排序

快速排序可能是应用最广泛的排序算法了。流行的原因是因为它实现简单、适用于各种不同的输入数据且在一般的应用中比其他算法都要快得多。快速排序属于原地排序，不需要额外的空间（相对于归并排序）。快速排序算法的时间复杂度为NlogN。

快速排序和归并排序类似，也是分治思想是应用。归并排序每次将数组一分为二，将两边都排序之后再合并。快速排序算法是每次将数组进行切分，保证切分点在相对于两边的子数组是有序的。左边的子数组都不大于切分点，右边的字数组都不小于切分点。

public class QuickSort extends AbstractSort implements Sort {

	@Override
	public void sort(Comparable[] a) {
		 sort(a,0,a.length - 1);
	}
	
	public void sort(Comparable[] a,int lo,int hi){
		if(hi<=lo) return;//递归结束条件
		int j = partition(a,lo,hi);
		//递归对子数组进行排序
		sort(a,lo,j-1);
		sort(a,j+1,hi);
	}

	/**
	 * 切分
	 * 使a[lo]左边元素不大于本身，右边元素不小于本身
	 */
	private int partition(Comparable[] a, int lo, int hi) {
		int i = lo,j = hi + 1;
		Comparable v = a[lo];
		while(true){
			while(less(a[++i],v)){//从左往右直到遇到一个比v大的元素
				if(i==hi) break;
			}
			while(less(v,a[--j])){//从右往左直到遇到一个比v小的元素
				if(j==lo) break;
			}
			if(i>=j){
				break;
			}
			exch(a, i, j);
		}
		exch(a, lo, j);
		return j;
	}
	public static void main(String[] args) {
		QuickSort sort = new QuickSort();
		Integer[] data = RandomFactory.randomInt(3000000, 40000);
		//sort.show(data);
		long t = System.currentTimeMillis();
		sort.sort(data);
		t = System.currentTimeMillis() - t;
		//sort.show(data);
		System.out.println("quick sort");
		System.out.println("is sorted:"+sort.isSorted(data));
		System.out.println("time consumed:" + t);
	}
}

运行结果比归并算法还稍快一点：

quick sort
is sorted:true
time consumed:1373

从排序算法代码中可以看出，算法中的切分操作发生在下一层递归之前。而归并算法的合并操作是在下一层递归之后进行的。这一点上看，快速排序有一点自上而下的味道，归并算法更类似于撒网搜网的感觉。