二分与排序中等1 种解法

#912排序数组

将整数数组按升序原地排序并返回；这里整理旧源码中的随机化快速排序。

#数组#排序#快速排序#分治

解题主线

分区把枢轴放到最终位置，并保证左侧不大于枢轴、右侧不小于枢轴，再递归处理两侧。

随机选择枢轴可减少有序输入稳定触发极端分区的风险。

挖坑分区交替从右找小值、从左找大值，指针相遇处就是枢轴最终位置。

解法 1：随机枢轴挖坑快速排序

把随机枢轴交换到左端，交替搬运右侧较小值和左侧较大值，枢轴归位后递归排序两侧。

时间复杂度

期望 O(n log n)，最坏 O(n²)

空间复杂度

期望 O(log n)，最坏 O(n)，来自递归栈

912. 排序数组 · 随机枢轴挖坑快速排序

java

import java.util.concurrent.ThreadLocalRandom;

final class Solution {
    public int[] sortArray(int[] nums) {
        if (nums == null) throw new IllegalArgumentException("nums must not be null");
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left >= right) return;
        int pivotIndex = partition(nums, left, right);
        quickSort(nums, left, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, right);
    }

    private int partition(int[] nums, int left, int right) {
        int randomIndex = ThreadLocalRandom.current().nextInt(left, right + 1);
        swap(nums, left, randomIndex);
        int pivot = nums[left];
        int low = left;
        int high = right;

        while (low < high) {
            while (low < high && nums[high] >= pivot) high--;
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivot) low++;
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }

    private void swap(int[] nums, int first, int second) {
        int temporary = nums[first];
        nums[first] = nums[second];
        nums[second] = temporary;
    }
}

把随机枢轴交换到左端，交替搬运右侧较小值和左侧较大值，枢轴归位后递归排序两侧。

旧文件两个 partition 都服务于同一快速排序策略，未作为重复解法拆分；保留并启用了修正后的挖坑版本。

边界与易错点

旧 partition1 的第二段扫描错误地判断 nums[right] 而不是 nums[left]，且 sortArray 从未调用它；整理后修正条件并让快速排序实际使用该分区。
分区内移动指针时必须始终检查 left < right，避免越界或死循环。
快速排序最坏时间 O(n²)、最坏递归深度 O(n)；随机化改善期望表现但不消除最坏情况。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q912_sort.java