二分与排序中等1 种解法

#912排序数组

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

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

原题

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

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

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
解释：请注意，nums 的值不一定唯一。

提示：

1 <= nums.length <= 5 * 10⁴
-5 * 10⁴ <= nums[i] <= 5 * 10⁴

查看原题

解题主线

分区把枢轴放到最终位置，并保证左侧不大于枢轴、右侧不小于枢轴，再递归处理两侧。
随机选择枢轴可减少有序输入稳定触发极端分区的风险。
挖坑分区交替从右找小值、从左找大值，指针相遇处就是枢轴最终位置。

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

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

时间复杂度： 期望 O(n log n)，最坏 O(n²)
空间复杂度： 期望 O(log n)，最坏 O(n)，来自递归栈

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);
        // 保存枢轴值后，left 位置成为可反复填充的“坑”
        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