QuickSort

package sort;

import java.util.Arrays;

/**
 * 快速排序<br>
 * 数组分三部分:<br>
 * 1、<b>中轴</b> （取数组中第一个值为中轴）。<br>
 * 2、<b>S1区域</b> （小于中轴的值）<br>
 * 3、<b>S2区域</b> （大于中轴的值） <br>
 * S1，S2排序，递归。
 * 
 * @author Administrator
 * 
 */
public class QuerySort {

	public static void main(String[] args) {
		int[] array = { 12, 3, 4, 5, 11, 2, 7, 8, 6, 9, 0 };
		sort(array, 0, array.length);
		System.out.println(Arrays.toString(array));
	}

	public static void sort(int[] array, int b, int e) {
		/** 取中轴的位置 **/
		int m = getMid(array, b, e);

		if (b < m) { // 基事件，终止条件
			/** 对S1区域排序 **/
			sort(array, b, m);
		}

		if (m + 1 < e) { // 基事件，终止条件
			/** 对S2区域排序 **/
			sort(array, m + 1, e);
		}
	}

	public static int getMid(int[] array, int b, int e) {
		int p = b; // 中轴索引
		int s1e = b; // S1区域 末端索引
		int temp = 0; // 临时空间
		/** 目前结构，中轴|未知空间 **/
		for (int i = b; i < e; i++) {
			if (array[i] < array[p]) { // S1空间增加值， s1e++
				s1e++;
				temp = array[i];
				array[i] = array[s1e];
				array[s1e] = temp;
			}
		}
		/** 目前结构，中轴|S1|S2 。将中轴值与S1末端互换位置，S1|中轴|S2 **/
		temp = array[s1e];
		array[s1e] = array[p];
		array[p] = temp;
		return s1e;
	}
}