手撕快排

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

https://leetcode.cn/problems/sort-an-array/description/

手撕快排

随机数+双指针

import java.util.Random;

class Solution {
    private final Random random = new Random();

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

    public void quickSort(int[] nums, int l, int r) {
        if (l >= r) return;

        // 1. 随机选下标
        int p = l + random.nextInt(r - l + 1);
        
        
        // 这样可以严格保证最后的 j 一定小于 r，绝生死循环
        swap(nums, l, p);
        int pivotVal = nums[l]; 
        
        int i = l;
        int j = r;

        while (true) {
            // 因为 pivotVal 就是 nums[l]，所以第一次循环 i 必然停在 l
            while (nums[i] < pivotVal) i++;
            while (nums[j] > pivotVal) j--;

            if (i >= j) break;

            swap(nums, i, j);
            i++;
            j--;
        }

        // 3. 使用 j 来切分
        quickSort(nums, l, j);
        quickSort(nums, j + 1, r);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}