java快速排序

/***
 * 快速排序简单实现
 * 
 * @author bobo
 * 
 */
public class QuickSort {
	public static void main(String[] args) {
		/**
		 * 快速排序的逻辑是：在所有元素中取一个标尺（一般是第一个）将待排序序列分成两组 一组的元素 都小于这个标尺，另一组都大于或等于这个标尺
		 * 然后对每个部分再进行递归调用，直到全部完成
		 */
		int[] a = { 9,8,7,6,5,4,3,2,1,1,2,3,4,5,6,7,8,9};
		show(a);
		quickSort(a, 0, a.length - 1);
		show(a);
	}

	/***
	 * 快速排序的核心方法
	 * 
	 * @param a
	 *            待排序的序列
	 * @param begin
	 *            待排序列子序列起始位置索引
	 * @param end
	 *            待排序列子序列结束位置索引
	 */
	private static void quickSort(int[] a, int begin, int end) {
		System.out.println(begin + ">" + end);
		// 若没有必要进行排序则返回
		if (end - begin <= 1) {
			return;
		}
		// 定义此次排序的标尺元素 此处选择开始位置为标尺元素 不要些a[0] 因为要多次递归调用
		int x = a[begin];
		// 定义左右的指针
		int p1 = begin;// 左指针
		int p2 = end;// 右指针
		// 定义比较方向 true表示向右 false表示向左
		boolean dr = true;
		// 进行循环操作，条件是两个指针不相撞
		L1: while (p1 < p2) {
			// 如果方向向右
			if (dr) {
				// 从p2>p1之间进行循环查找可以进行替换的数值
				for (int i = p2; i > p1; i--) {
					if (a[i] <= x) {
						a[p1] = a[i];
						p1++;// 进行自增 左指针右移
						dr = !dr;// 转换方向
						p2 = i;// 右指针指向i
						continue L1; // 下一步循环
					}
				}
				// 如果能执行到这一步 说明没有找到小于标尺的元素，则说明序列本身就ok 则进行如下赋值
				p2 = p1;
			} else {
				// 如果方向向左
				// 从p1>p2之间进行循环查找可以进行替换的数值
				for (int i = p1; i < p2; i++) {
					if (a[i] > x) {
						a[p2] = a[i];
						p2--;// 右指针自减
						dr = !dr;// 转换方向
						p1 = i;
						continue L1;
					}
					// 如果能执行到这一步 说明没有找到小于标尺的元素，则说明序列本身就ok 则进行如下赋值
					p1 = p2;
				}
			}

		}
		// 进行递归调用
		a[p1] = x;// 填充空白处
		show(a, begin, end,p1);
		quickSort(a, begin, p1 - 1);
		quickSort(a, p1 + 1, end);

	}

	private static void show(int[] a, int begin, int end, int p1) {
		for (int i = begin; i < end + 1; i++) {
			if (i==p1) {
				System.out.print("["+a[i]+"]" + " ");
			}else {
				System.out.print(a[i]+" ");
			}
			
		}
		System.out.println();
	}

	/**
	 * 显示 数组元素
	 * 
	 * @param a
	 */
	private static void show(int[] a) {
		for (int i : a) {
			System.out.print(i + " ");
		}
		System.out.println();
	}
}