Java快排算法及实现

　　快排的思想是：对于一个待排的序列，我们每次都以这个序列的最左边的数字作为基准数，然后从这个序列的最左边和最右边的位置开始遍历(右边先开始)，实现从左边开始找比这个基准数大的数字，从右边开始找比这个基准数小的数字，找到了之后就交换这两个位置的数字，然后继续遍历，最后退出条件是当两个方向的遍历指针相重叠时，交换此时的位置的元素和基准数，这样子就实现了，基准数左边的都是比它小的元素，而右边都是比它大的元素，然后再对这个基准数左右两边的子序列进行递归即可。

　　递归的实现如下：

package common.test;

public class QuickSortUtils {

	public static void sort(int num[], int left, int right) {
		quickSort(num, left, right);
	}

	private static void quickSort(int num[], int left, int right) {
		/* 如果只有一个元素的话则直接返回退出 */
		if (left >= right) {
			return;
		}
		/* 每次快排的基准数都选择是待排序列的最左元素 */
		int key = num[left];
		/* 使用两个指针来从左往右和从右往左来遍历位置 */
		int i = left;
		int j = right;
		/* 每次递归的退出条件就是当i和j两个指针相遇的时候 */
		while (i < j) {
			/* 右边的指针先开始移动,并且退出条件是要找到比key的值小的元素,以交换到序列的左边去 */
			while (num[j] >= key && i < j) {
				j--;
			}
			/* 左边的指针后移动，退出条件是要找比Key的值大的元素来交换到右边去 */
			while (num[i] <= key && i < j) {
				i++;
			}
			/* 都找到了各自的数字就在此进行交换 */
			int temp = num[j];
			num[j] = num[i];
			num[i] = temp;
		}
		/* 这样子一次排序完了之后再交换key和num[i]的元素,让key的左边都是比它小的元素,右边都是比它大的元素 */
		num[left] = num[i];
		num[i] = key;
		/* 然后再对左右两个子序列递归快排 */
		quickSort(num, left, i - 1);
		quickSort(num, i + 1, right);

	}

	public static void main(String[] args) {
		int num[] = { 3, 4, 5, 6, 7, 8, 12, 3, 5, 2, 35, 2, 354, 2, 534 };
		QuickSortUtils.quickSort(num, 0, num.length - 1);
		for (int data : num) {
			System.out.print(data + " ");
		}
	}
}