java算法之快速排序

package com.hym.test.algorithms;

public class QuickSort {
	private int[] arrayTest = { 5, 26, 1, 783, 23, 2, 62, 9, 46 };

	public void quickSort(int left, int right) {
		if (right - left <= 0) {
			return;
		} else {
			int pivot = arrayTest[right];
			int partition = partitionIt(left, right, pivot);
			quickSort(left, partition - 1);
			quickSort(partition + 1, right);
		}
	}

	public int partitionIt(int left, int right, int pivot) {
		int begin = left - 1;
		int end = right;

		while (true) {
			while (arrayTest[++begin] < pivot)
				;
			while (end > 0 && arrayTest[--end] > pivot)
				;

			if (begin >= end) {
				break;
			} else {
				swap(begin, end);
			}
		}
		swap(begin, right);
		return begin;
	}

	public void swap(int begin, int end) {
		int temp = arrayTest[begin];
		arrayTest[begin] = arrayTest[end];
		arrayTest[end] = temp;
	}

	public static void main(String args[]) {
		QuickSort sort = new QuickSort();
		sort.quickSort(0, sort.arrayTest.length - 1);

		for (int i = 0; i < sort.arrayTest.length; i++) {
			System.out.print(sort.arrayTest[i] + " ");
		}
	}
}

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

http://baike.baidu.com/view/115472.htm