快速排序

package com.kingdee.gmis.algorithm;

public class QuickSort2 {

	public void quickSort(int[] arrs) {
		quickSort(arrs, 0, arrs.length - 1);
	}

	private void quickSort(int[] arrs, int l, int r) {
		if (l >= r) {
			return;
		}
		int pivotIdx = getPivotIdx(l, r);
		swap(arrs, pivotIdx, r);
		int k = partition(arrs, l - 1, r, arrs[r]);//这里是l - 1
		swap(arrs, k, r);
		quickSort(arrs, l, k - 1);
		quickSort(arrs, k + 1, r);
	}

	private void swap(int[] arrs, int idx1, int idx2) {
		int tmp = arrs[idx1];
		arrs[idx1] = arrs[idx2];
		arrs[idx2] = tmp;
	}

	private int getPivotIdx(int l, int r) {
		return (r + l) / 2;
	}

	private int partition(int[] arrs, int l, int r, int pivot) {
		while (l < r) {
			while (arrs[++l] < pivot)
				;
			while (r > l && arrs[--r] > pivot)
				;
			swap(arrs, l, r);
		}
		return l;
	}
}