04-快速排序

快速排序 - 递归
快速排序的原理：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。
一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引 > 从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。

【逻辑】选择第一个数位基准值，开始首尾比较，尾[length-1]基准值开始的j--找 ≥ 尾值的进行交换，首[0]基准值开始的i++找 ≤ 首值的进行交换，找到中间后，两半边各自递归
【优点】极快，数据移动少
【缺点】不稳定（原因同选择排序）

public class TestArraySort {
	public static void main(String[] args) {
		int[] nums = {1, 8, 3, 6, 2, 9, 7, 4, 5};
		quickSort(nums, 0, nums.length-1);
		System.out.println(Arrays.toString(nums)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]
	}
	
    /**
     * Java排序：快速排序
     * 说明：选一个数作为基数(一般为arr[0])，升序时，大于基数的放到右边，小于基数的放到左边
     * @param arr 整型数组
     * @param left 最小基准位置，如 0
     * @param right 最大基准位置，如 length - 1
     */
    public static void quickSort(int[] arr, int left, int right) {
        // 1.参数合法性判断
        if (null == arr || 0 == arr.length || left > right) {
            return;
        }

        // 2.快速排序主逻辑
        int i, j, baseVal;
        i = left;
        j = right;
        baseVal = arr[left]; // 起始基准位

        // 只要 i != j 那么与基准值的对比就没有完成，i++ 向右对比，j-- 向左对比
        while (i != j) {
            // 起始基准值为 arr[left] 左侧，需要先对比右侧，才能确定值是否需要放到右侧
            while (baseVal <= arr[j] && i < j) {    // 升序：先看右边，依次往左递减对比 baseVal
            //while (baseVal >= arr[j] && i < j) {  // 降序：先看右边，依次往左递增对比 baseVal
                j--;
            }
            while (baseVal >= arr[i] && i < j) {    // 升序：再看左边，依次往右递增对比 baseVal
            //while (baseVal <= arr[i] && i < j) {  // 降序：再看左边，依次往右递减对比 baseVal
                i++;
            }
            if (i < j) { // 满足条件时，且此时还是左下标比右下标小，需要交换
                int t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        // 递归左半边时，arr[i] 会成为下一次基准值；递归右半边时，arr[j+1] 为基准值
        arr[left] = arr[i]; // 把 i 索引的值赋值给了 left 索引的值
        arr[i] = baseVal;

        quickSort(arr, left, j - 1); // 基准值(arr[left]), 递归调用左半边
        quickSort(arr, j + 1, right); // 基准值(arr[j+1]), 递归调用右半边
    }
}