排序－快速

快速排序是通用排序中（针对内存中）最为流行的算法，其时间效率为O(n * log n)。

其关键算法是基于划分的排序。

划分只将数组中任意一个元素作为枢纽值，经过交换，使得数组中排列成所有小于枢纽的数值都在枢纽左边，而所有大于枢纽的数值都在枢纽右侧，然后返回枢纽的位置。注意，枢纽的选择可以是任意的。

快排选择将给定数组范围的的第一个数字作为枢纽，然后将数组分为两部分，大于枢纽的，小于枢纽的。然后对这两部分递归调用快速排序。

 

快排在极端情况下可能出现效率底下问题，这与枢纽的选取的策略有关，加入数组完全逆序，则枢纽总会选取指定范围中最大的值，只是一次简单交换，没有将数组有效划分两个部分。因此可以调整枢纽选取策略来修正这个问题，比如在给定范围中前中后三个位置选取三个值，选择值为中间的位置作为枢纽，这样可以一定程度上避免极端问题。

其他速度较快的，且很少出现极端情况的排序方法见希尔排序

代码如下：

class Quick {
	public static void main(String[] args) {
		int[] a = {6,9,5,4,2,45,23,45,53,3,7};
		int pos = getPartitionPos(a,0,a.length);
		sort(a,0,a.length);
		println(a);
	}

	public static void println(int[] a) {
		for(int i: a) System.out.print(i + " ");
		System.out.println();
	}

	public static void sort(int[] a,int begin, int end) {
		if(begin >= end) return;
		int pos = getPartitionPos(a,begin,end);
		sort(a,begin,pos);
		sort(a,pos + 1, end);
	}

	private static int getPartitionPos(int[] a, int begin, int end) {
		int pos = begin;
		int value = a[begin];
		while(true) {
			while(begin < end && a[--end] > value);	//从结尾向左找到第一个比枢纽小的数值
			while(begin < end && a[++begin] < value);	//从结尾向右找到第一个比枢纽大的数值
			if(begin < end) { //如果需交互
				a[pos] = a[end];	//将比枢纽小的值放在空位
				a[end] = a[begin];	//将比枢纽大的值放在原来从右向左第一个比枢纽小的值的位置上
				pos = begin;	//将从左向右第一个比枢纽大的值的位置标志为空位
			} else break; 
		}
		if(pos != begin) { //如果空位与结束位置不等
			a[pos] = a[begin];	//将空位置为结束时位置的值
			a[begin] = value;	//将结束位置放置枢纽
		} else a[pos] = value;	
		return begin;
	}
}

  同样代码还可以这样：

class Quick2 {
	public static void main(String[] args) {
		int[] a = {1501,545,414,78,3,18,611,578,114,125,94,67,157};
		sort(a,0,a.length);
		print(a);
	}
	public static void sort(int[] a,int p1,int p3) {
		if((p3-p1) <= 1) return;
		int p2 = get(a,p1,p3);
		sort(a,p1,p2);
		sort(a,p2+1,p3);
	}
	public static int get(int[] a,int b, int e) {
		int pos=b, temp=a[b];
		boolean dir = true;
		while(b<e) {
			if(dir) {
				if(a[--e] <= temp) {
					a[pos] = a[e];
					pos = e;
					dir = false;
				}
			} else {
				if(a[++b] >= temp) {
					a[pos] = a[b];
					pos = b;
					dir = true;
				}
			}
		}
		a[pos] = temp;
		return pos;
	}

	private static void print(int[] a) {
		for(int i: a) System.out.print(i + " ");
		System.out.println();
	}

}