Java快速排序算法整理(一)

package boke.sort;

/**
 * 快速排序
 * 
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.05.24
 * 
 */
public class QuickSort {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int maxSize = 10000;
		QuickSort bs = new QuickSort(maxSize);

		for(int i = 1; i <= 1000; i++) {
			int v = (int) (Math.random()*1000);
			bs.insert(v);
		}
		bs.output(); // 原始输出
		bs.quickSort(); // 排序
		bs.output(); // 排序输出

	}

	private long[] a; // 整型数据容器
	private int nElems; // 元素个数

	/**
	 * 构造方法
	 * 
	 * @param maxSize
	 */
	public QuickSort(int maxSize) {
		a = new long[maxSize];
		nElems = 0;
	}

	/**
	 * 容器放入数据
	 * 
	 * @param value
	 */
	public void insert(long value) {
		a[nElems++] = value;
	}

	/**
	 * 输出容器数据
	 */
	public void output() {
		for (int j = 0; j < nElems; j++) {
			System.out.print(a[j] + " ");
		}
		System.out.println("");
	}

	/**
	 * 快速排序
	 */
	public void quickSort() {
		recQuickSort(0, nElems - 1);
	}

	/**
	 * 快速排序
	 * 
	 * @param left
	 * @param right
	 */
	private void recQuickSort(int left, int right) {
		if (right - left <= 0) {
			return;
		} else {
			long pivot = a[right]; // 最右边的元素
			int partition = partitionIt(left, right, pivot);
			recQuickSort(left, partition - 1); // 左段排序
			recQuickSort(partition + 1, right); // 右段排序
		}
	}

	/**
	 * 快速排序
	 * 
	 * @param left
	 * @param right
	 * @param pivot
	 * @return
	 */
	private int partitionIt(int left, int right, long pivot) {
		int leftPtr = left - 1;
		int rightPtr = right;

		while (true) {
			while (a[++leftPtr] < pivot) {
				;
			}

			while (rightPtr > 0 && a[--rightPtr] > pivot) {
				;
			}

			if (leftPtr >= rightPtr) {
				break;
			} else {
				swap(leftPtr, rightPtr);
			}
		}
		swap(leftPtr, right);
		return leftPtr;
	}

	/**
	 * 交换
	 * 
	 * @param leftPtr
	 * @param rightPtr
	 */
	private void swap(int leftPtr, int rightPtr) {
		long temp = a[leftPtr];
		a[leftPtr] = a[rightPtr];
		a[rightPtr] = temp;

	}
}