双向快速排序

package nodelist;

public class QuickSort {
	public static void main(String[] args) {
		QuickSort qs = new QuickSort();
		int[] arr = new int[] { 5, 6, 2, 3, 4, 7, 8, 9 };
		qs.quickSort(arr, 0, arr.length - 1);
		for (int el : arr) {
			System.out.println(el);
		}
	}

	public void quickSort(int arr[], int left, int right) {
		if (left < right) {
			int mid = partition(arr, left, right);
			quickSort(arr, left, mid);
			quickSort(arr, mid + 1, right);
		}
	}

	private int partition(int[] arr, int left, int right) {
		int l = left;
		int r = right;
		int tmp = arr[left];
		while (l < r) {
			while (l < r && arr[r] < tmp)
				r--;
			if (l >= r) {
				break;
			} else {
				swap(arr, l, r);
			}
			while (l < r && arr[l] > tmp)
				l++;
			if (l >= r) {
				break;
			} else {
				swap(arr, l, r);
			}
		}
		arr[l] = tmp;
		return l;
	}

	/**
	 * 交换数据
	 */
	public void swap(int array[], int leftpoint, int rightpoint) {
		int temp = array[leftpoint];
		array[leftpoint] = array[rightpoint];
		array[rightpoint] = temp;
	}

}