array partition quicksort

ArrayPartition.java

/**
 * 将数组分三块，中间一块是pivot[就一个元素]，左边一块是所有元素都小于pivot，右边一块是所有元素都大于pivot<br />
 * 快速排序的基础，简单易懂，居家旅行面试必备
 */
public class ArrayPartition {
	public static void main(String[] args) {
		int[] arr = { 4, 5, 3, 22, 1, 3 };
		printArray(arr, "init");
		System.out.println("pivot idx " + sort(arr, 0, arr.length - 1));
		printArray(arr, "result");
	}

	private static int sort(int[] array, int begin, int end) {
		int pivot = array[begin];
		int low = begin - 1;
		int hig = end + 1;
		while (low + 1 != hig) { // 两端往中间逼近
			if (array[low + 1] <= pivot) {
				low++;
			} else if (array[hig - 1] > pivot) {
				hig--;
			} else {
				int tmp = array[low + 1];
				array[++low] = array[hig - 1];
				array[--hig] = tmp;
			}
		}
		array[begin] = array[low]; // 把pivot替换到中间位置
		array[low] = pivot;
		return low;
	}

	private static void printArray(int[] array, String msg) {
		for (int i : array) {
			System.out.print(i + " ");
		}
		System.out.println(msg);
	}
}