package changsheng.algorithms.sort;


public class QuickSort {
	
	public static void Sort(int[] a){
		Sort(a,0,a.length-1);
	}

	public static void Sort(int[] a, int low, int high) {
		/*实际上不应该选择第一个元素作为pivot，因为第一个元素可能是极值元素，会造成递归解决大量空集*/
		/*推荐的pivot应该利用三个元素的中值分割*/
		/*1、对第一个元素、中间元素，最后一个元素，进行排序*/
		/*2、然后将排好序的三个元素的中间元素与倒数第二个元素进行交换*/

		/*另外对于个数较少的元素应该进行插入排序，或者结合堆排序*/

		if (low <= high) {
			/*先对指定范围内的值进行一次快速过程，再对这次快速过程的结果进行分解递归*/
			int mid = Partition(a, low, high);
			Sort(a, low, mid - 1);
			/*mid位置上的值为键，所以mid-1和mid+1来划分*/
			Sort(a, mid + 1, high);
		}
	}

	static private int Partition(int[] a, int low, int high) {
		/*以指定范围内数组选中第一个做为pivot*/
		int key = a[low];
		
		while (low < high) {
			/*从high至low与key进行比较*/
			while (low < high && a[high] >= key)
				high--;
			/*当这个循环结束时，high就是小于key的索引位置*/
			/*a[high] < key*/
			a[low] = a[high];

			/*从high至low与key进行比较*/
			while (low < high && a[low] <= key)
				low++;
			/*当这个循环结束时，high就是小于key的索引位置*/
			/*a[low] > key*/
			a[high] = a[low];
		}
		a[low] = key;
		return low;
	}
}