快速排序

快速排序，经典的排序算法，用到了递归。

核心思想

要将一个数组排序，先随机以一个数为基准，将比其大的数放到其右边，比其小的数放到其左边，然后再递归排以这个数为中心的左半区间和右半区间。

注意点

一定要随机化选择切分元素(pivot)，否则在输入数组是有序数组或者是逆序数组的时候，快速排序会变得非常慢。

时间复杂度

时间复杂度为O(nlogn)。

空间复杂度

空间复杂度为O(h)，其中h为快速排序递归调用的层数。我们需要额外的O(h)的递归调用的栈空间，由于划分的结果不同导致了快速排序递归调用的层数也会不同，最坏情况下需O(n)的空间，最优情况下每次都平衡，此时整个递归树高度为logn，空间复杂度为O(logn)。

稳定性

不稳定。

代码示例

public int[] sortArray(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
}

/**
 * 快速排序
 *
 * @author chengzhy
 * @param nums 需要排序的数组
 * @param left 左边界
 * @param right 右边界
 * @date 2022/2/19 13:35
 */
private void quickSort(int[] nums, int left, int right) {
    if (left < right) {
        /**
         * 核心思想：以一个数为基准，将比其大的数放到其右边，比其小的数放到其左边
         * 然后再递归排以这个数为中心的左半区间和右半区间
         */
        int i = partition(nums, left, right);
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }
}

/**
 * 分隔(选取一个数作为基准，将比其大的数放到其右边，比其小的数放到其左边)
 *
 * @author chengzhy
 * @param nums 需要排序的数组
 * @param left 左边界
 * @param right 右边界
 * @date 2022/2/19 13:35
 * @return 分隔后基准数的下标值
 */
private int partition(int[] nums, int left, int right) {
    /**
     * 优化点：针对特殊测试用例：顺序数组或者逆序数组，一定要随机化选择切分元素（pivot），
     * 否则在输入数组是有序数组或者是逆序数组的时候，快速排序会变得非常慢
     */
    int randomIndex = left + new Random().nextInt(right - left + 1);
    int temp = nums[left];
    nums[left] = nums[randomIndex];
    nums[randomIndex] = temp;
    // 将区间的第一个数作为基准
    int base = nums[left];
    int i = left, j = right;
    while (i < j) {
        // 循环找比基数小和比基数大的数
        // 先去找第一个比基数小的数的位置
        while (base <= nums[j] && i < j) {
            j--;
        }
        // 再去找第一个比基数大的数的位置
        while (base >= nums[i] && i < j) {
            i++;
        }
        if (i < j) {
            // 如果i在j的左边，则交换两个位置的数
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    // 将基数放至中心位置
    nums[left] = nums[i];
    nums[i] = base;
    // 返回基数的位置
    return i;
}