快速排序 Quick sort

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

public class QuickSort {
	static void quickSort(int[] array, int left, int right) {
		int dp;
		if (left < right) {
			dp = partition(array, left, right);
			quickSort(array, left, dp - 1);
			quickSort(array, dp + 1, right);
		}
	}

	static int partition(int[] array, int left, int right) {
		int pivot = array[left];
		while (left < right) {
			while (left < right && array[right] >= pivot)
				right--;
			if (left < right)
				array[left++] = array[right];
			while (left < right && array[left] <= pivot)
				left++;
			if (left < right)
				array[right--] = array[left];
		}
		array[left] = pivot;
		return left;
	}

	public static void main(String[] args) {
		int[] array = { 3, -1, 0, -8, 2, 1 };

		System.out.println(Arrays.toString(array));

		quickSort(array, 0, array.length - 1);

		System.out.println(Arrays.toString(array));
	}
}