排序算法 - 快速排序详解

对于一组数据，选择一个基准元素（base），通常选择第一个或最后一个元素，通过一轮扫描，比base小的元素都在base左边，比base大的元素都在base右边，对左右子序列用相同的方法递归排序，直到序列中所有数据均有序为止。

快速排序，说白了就是给基准数据找其正确索引位置的过程。

以 [19,97,09,17,01,08] 为例，以第一个元素19为base，定义左右两个指针 L和 R，分别从两端开始扫描。从右向左找比19小的数，替换L所在位置的元素。再从左往右找比19大的数，然后替换R所在位置的元素。重复此过程直至L和R重合（两个指针指向同一元素），base替换此元素，此时第一轮结束。再递归排序base左右两部分的元素。

首先R从后向前扫描，如果扫描到的值大于基准数据就让R减1，然后继续往前扫描，直到发现有元素比该基准数据的值小(如上图中08<=base)，就将R位置的值赋值给L位置 ,结果如下:

然后交替移动L下标：L从前往后扫描,如果扫描到的值小于基准数据就让L加1，然后继续向后扫描，直到发现有元素大于基准数据的值(如上图97>=base)，就再将L位置的值赋值给R位置的值,指针移动并且数据交换后的结果如下:

然后交替移动R下标，向前移动，直到扫描到小于基准数的值，如上图继续扫描到 01 <= 19，则就将R位置的值赋值给L位置 ,结果如下:

然后继续交替移动L下标，向后移动，如上图L一直向后扫描，09比基准数小，继续后移，17比基准数小，继续后移，这时候L和R重合，则base替换此元素。

左子序列都比19小，右子序列都比19大

然后对左右子序列重复以上操作即可。

public class QuickSort {

	public static void main(String[] args) {
		int[] array = new int[]{100, 89, 66, 1, -1, 30, 5, 85, -25};

		quickSort(array, 0, array.length - 1);

		System.out.println(Arrays.toString(array)); // [-25, -1, 1, 5, 30, 66, 85, 89, 100]
	}

	
	private static void quickSort(int[] arr, int left, int right) {

		if (left < right) {
			// 每次分割的点pos
			int pos = partition(arr, left, right);

			// 左子序列 比base小的数字的数组
			quickSort(arr, left, pos - 1);
			// 右子序列 比base大的数字的数组
			quickSort(arr, pos + 1, right);
		}

	}


	private static int partition(int[] arr, int left, int right) {
		// 基准数据
		int base = arr[left];
		while (left < right) {
			// 从后向前找，比base大，right--
			while (left < right && arr[right] >= base) {
				right--;
			}
			// 比base小，替换left所在位置的数字
			arr[left] = arr[right];

			// 从前向后找，比base小，left++
			while (left < right && arr[left] <= base) {
				left++;
			}
			// 比base大，替换right所在位置的数字
			arr[right] = arr[left];

		}
		// 此时left=right，用base替换这个位置的数字
		arr[left] = base;
		return left; // 返回base的正确位置
	}
}

勞