package com.itjob.algorithm;

public class QuickSort {
	/**
	 * @param args
	 */
	public static void main(String[] args) {

	}

	static void quickSort(int[] array, int front, int tail) {
		if (front < tail) {
			int pivotPosition = partition(array, front, tail);
			// 递归实现子数组的划分，每次根据不同边界来划分
			// 划分枢轴的左数组
			quickSort(array, front, pivotPosition - 1);
			// 划分枢轴的右数组
			quickSort(array, pivotPosition + 1, tail);
		}
	}

	static int partition(int[] array, int front, int tail) {
		int middle; // 用于保存中间位置
		int boundary; // 保存边界位置
		int pivot; // 保存枢轴位置
		int temp; // 保存临时值，用于值交换
		
		// 获取中间值的位置
		middle = (front + tail) / 2;
		// 得到枢轴
		pivot = array[middle];
		// 执行第一步，将枢轴与子数组中的最后一个数据项交换
		array[middle] = array[tail];
		array[tail] = pivot;

		// 执行第二步，建立一个边界(boundary),最初该边界在数组的第一个元素之前
		boundary = front;

		// 执行第三步，遍历子数组，并将每个元素和枢轴对比，并改变元素位置
		for (int i = front; i < tail; i++) {
			// 如果当前元素小于枢轴，则将该元素和边界互换，并将交换后的边界往后移一位
			if (array[i] < pivot) {
				temp = array[boundary];
				array[boundary] = array[i];
				array[i] = temp;
				boundary++;
			}
		}

		// 执行第四步，将枢轴与边界后的第一个元素交换
		temp = array[tail];
		array[tail] = array[boundary];
		array[boundary] = temp;
		// 返回边界位置
		return boundary;
	}
}
