快速排序模板：原地排序的经典分治算法#

import java.util.concurrent.ThreadLocalRandom;

class QuickSortTemplate {
    public static void quickSort(int[] nums, int left, int right) {
        if (left >= right) { // 递归终止：区间长度为 0 或 1 时天然有序
            return;
        }

        int pivotIndex = ThreadLocalRandom.current().nextInt(left, right + 1); // 随机选择枢轴下标，降低退化概率
        int pivot = nums[pivotIndex]; // 枢轴值：用于三路划分

        int lt = left; // [left, lt-1] 区间都 < pivot
        int index = left; // 当前扫描指针
        int gt = right; // [gt+1, right] 区间都 > pivot

        while (index <= gt) { // 当扫描指针未越过 >pivot 区间左边界时继续
            if (nums[index] < pivot) { // 当前值应放到“小于区”
                swap(nums, lt, index); // 与 lt 交换，把小值放到前面
                lt++; // 小于区右扩
                index++; // 当前位已处理，继续向右扫描
            } else if (nums[index] > pivot) { // 当前值应放到“大于区”
                swap(nums, index, gt); // 与 gt 交换，把大值放到后面
                gt--; // 大于区左扩
            } else {
                index++; // 等于 pivot，留在中间区，直接扫描下一个
            }
        }

        quickSort(nums, left, lt - 1); // 递归排序“小于 pivot”区间
        quickSort(nums, gt + 1, right); // 递归排序“大于 pivot”区间
    }

    private static void swap(int[] nums, int first, int second) {
        int temp = nums[first]; // 临时保存 first 位置值
        nums[first] = nums[second]; // second 覆盖到 first
        nums[second] = temp; // 完成交换
    }
}