排序-快排

    快排平均时间复杂度O(nlogn)，平均空间复杂度O(logn)。效率和使用比较多的排序算法。

快排基本思想

• 从数组取出一个数，叫基数（privot）

• 遍历数组，将数组中的数按照大于和小于基数，分布在基数的两边

• 将左右两个数组再次重复以上步骤，直到分成的子数组数量只要1个或2个

快排退出递归的边界

• 当某个区域只剩下一个数字或0个数字的时候就不需要排序了

• start 存在 等于middle，等于middle-1；end存在等于middle，等于end-1，则start == end 或end+1 = start情况下退出递归

• 进一步推理，start >= end 则退出递归，因为start正常情况下都小于end

基数选择

• 选择第一个做为基数

• 选择最后一个做为基数

• 随机选择基数，随机选择基数时间复杂度最优

分区算法

• 简单分区算法，从left开始，遇到比基数大的，则交换到数组最后并将right减1，直到left和right相遇，再将基数和中间的数交换，返回中间值的下标

• 双指针分区算法

快排优化

• 随机获取基数

• 防止数组正序或逆序，先将数组用洗牌算法打乱

洗牌算法

    每次从未处理的数据中，随机取一个数字，将其放入数字末尾。即JDK的Collections.shuffle()

class Solution {

    public int[] sortArray(int[] nums) {
        quickSort(nums);
        return nums;
    }

    private void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int start, int end) {
        if (start == end || start == end + 1) {
            return;
        }

        int middle = partition(arr, start, end);

        quickSort(arr, start, middle - 1);
        quickSort(arr, middle + 1, end);
    }

    /**
     * 快排分区
     * <p>
     * 我要成为亿万富翁
     * 我要财富自由
     *
     * @param arr
     * @param start
     * @param end
     * @return
     */
    private int partition(int[] arr, int start, int end) {
        Random rand = new Random();
        int middle = rand.nextInt((end - start) + 1) + start;

        // 将基数放在第一位
        swap(arr, middle, start);
        // 基数
        int privot = arr[start];

        int left = start + 1;
        int right = end;

        while (left < right) {
            while (left < right && arr[left] <= privot) left++;
            while (left < right && arr[right] >= privot) right--;
            if (left < right) {
                swap(arr, left, right);
                left++;
                right--;
            }
        }

        if (left == right && arr[right] > privot) right--;
        swap(arr, start, right);
        return right;
    }

    /**
     * 交换数组arr 下标 i j  的数据
     *
     * @param arr
     * @param i
     * @param j
     */
    private void swap(int[] arr, int i, int j) {
        if (i == j) return;
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[j] ^ arr[i];
        arr[i] = arr[i] ^ arr[j];
    }
}