QuickSort

思想

找到一个基准，将要排序的数据分成两部分， 一部分比另一部分所有元素都小。 然后按照这个方式递归的对这两部分数据进行快速排序。

排序过程

1. 从数列中找一个基准
2. 从右往左找到小于基准的值，替换掉i（对应的值），从左往右找到大于基准的值，替换掉j，重复，直到 i >= j，用基准替换这个i；这个过程完成之后，基准位于中间位置。
3. 递归的把基准前后的子序列进行排序。

实现

public void quickSort(int[] a, int l, int r) {
	if (l < r) {
		int i, j, x;
		i = l;
		j = r;
		x = a[i];
		
		while (i < j) {
		// 从右往左找到不大于x的
			while (i < j && a[j] > x) 
				j--;
			if (i < j) {
				a[i++] = a[j];
			}
		// 从左往右找到不小于x的
			while (i < j && a[i] < x)
				i++;
			if (i < j) {
				a[j--] = a[i];
			}
		}
		a[i] = x;
		quickSort(a, l, i - 1); //递归排序基准左边
		quickSort(a, i + 1, r); //递归排序基准右边
	}
}