Java实现快速排序（二）

快速排序是一种分治法的思想，主要思想是首先找一个“基准”元素，将所有比基准元素大的元素放到基准元素右边，所有比基准元素小的元素放到基准元素左边，这样基准元素在整个序列中的最终位置就确定了，同时，基准元素经序列分为两个子序列，对子序列进行上述同样的操作，最终就能得到有序的序列。

package 排序算法;

public class 快速排序二 {
	public static void main(String[] args) {
		int[] a = { 21, 3, 324, 23, 534, 5, 34 };
		quickSort(a, 0, a.length - 1);
		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i] + " ");
		}
	}

	// 快速排序
	private static void quickSort(int[] a, int left, int right) {
		int split_point;
		if (left < right) {
			split_point = partition(a, left, right);
			quickSort(a, left, split_point - 1);
			quickSort(a, split_point + 1, right);
		}

	}

	/**
	 * 以第一个元素为基准，将元素分成左右两部分，左边的都比基准小，右边的都比基准大。 返回基准位置
	 * 
	 * @param a
	 * @param left
	 * @param right
	 * @return
	 */

	private static int partition(int[] a, int left, int right) {
		int i = left, j = right, pivot = a[left]; // 以第一个元素为基准
		while (i < j) {
			for (; i < j && a[j] >= pivot; j--)
				; // 从右边找一个比pivot小的数
			a[i] = a[j]; // 将这个数放到左边空位，空位是由pivot或之前比pivot大的数留出来的
			for (; i < j && a[i] < pivot; i++)
				; // 从左边找一个比pivot大的数
			a[j] = a[i]; // 将这个数放到右边空位
		}
		a[i] = pivot;
		return i;
	}
}

partition 函数的功能就是将整个序列分成左右两部分，中间是基准元素的最终位置，这个函数分别从右边j和左边i开始找，总的比较次数为子序列的长度-1，(第一个是pivot不用比较)，且i