长风破浪会有时，直挂云帆济沧海。——李白

/** *  * @author Jason Li 2014-5-29 
 *         快速排序， 类似于合并排序，基本思想是：
 *         把待排序的元素分成两部分， 以一个主元(Pivot Element)为界，
 *         主元左边元素都不大于主元，主元右边元素都不小于主元，然后对左右部分递归此过程。
 *  *         算法的关键是分区的划分，即主元取值的选择， 这里主元是取最右边值作为主元值。 */public class QuickSortTest {	public static void main(String[] args) {		int[] dataArray = { 2, 6, 4, 9, 1, 7, 8, 3, 5 };		QuickSort(dataArray, 0, dataArray.length - 1);		System.out.println(Arrays.toString(dataArray));	}	// 快速排序	private static void QuickSort(int[] dataArray, int startIndex, int endIndex) {		if (startIndex < endIndex) {			int pivotIndex = Partion(dataArray, startIndex, endIndex);			QuickSort(dataArray, startIndex, pivotIndex - 1); // 递归主元左边部分			QuickSort(dataArray, pivotIndex + 1, endIndex); // 递归主元右边部分		}	}	// 分割待排序区域，返回主元位置，使主元左边元素都不大于主元，主元右边元素都不小于主元	private static int Partion(int[] dataArray, int startIndex, int endIndex) {		int pivot = dataArray[endIndex]; // 最后一个元素值为主元的值		int smallIndex = startIndex - 1;		for (int largeIndex = startIndex; largeIndex < endIndex; largeIndex++) {			// 从左开始，遂个与主元值值比较，如果小则依次放到左边			if (dataArray[largeIndex] <= pivot) {				smallIndex++;				swap(dataArray, smallIndex, largeIndex);			}		}		swap(dataArray, smallIndex + 1, endIndex);// 主元值与第一个不小于主元的值做交换		return smallIndex + 1;	}	// 两个数组元素交换	private static void swap(int[] dataArray, int i, int j) {		// 如果是同一元素，或存储的值一致则不用做交换		if (i != j && dataArray[i] != dataArray[j]) {			int temp = dataArray[i];			dataArray[i] = dataArray[j];			dataArray[j] = temp;		}	}}