【LeetCode 912】排序数组——随机化快速排序详解

作者：逆境不可逃

技术永无止境

希望我的内容可以帮助到你！！！！

LeetCode 912「排序数组」要求我们在不调用内置排序函数的情况下，将整数数组按升序排列。数组长度最多为5 × 10⁴，并且可能包含大量重复元素，因此需要选择效率较高的排序算法。

这篇文章使用随机化快速排序解决问题。核心过程可以概括为：

随机选择一个基准值 pivot ↓ 把数组划分到 pivot 两侧 ↓ 递归排序左右两个子数组

快速排序平均时间复杂度为O(n log n)，划分过程直接在原数组上完成，不需要额外创建左右数组。

一、快速排序的基本思路

假设当前需要排序的区间为：

[5, 2, 3, 1, 4]

从中选择一个元素作为基准值。为了方便讲解，假设选中3：

pivot = 3

经过一次划分后，我们希望得到：

[小于等于 3的元素 | 3 | 大于等于3的元素]

例如：

[1, 2 | 3 | 5, 4]

此时3已经处在一个正确的分界位置。接下来只需要继续排序：

左区间：[1, 2] 右区间：[5, 4]

当左右区间也分别有序时，整个数组自然有序。

二、为什么随机选择 pivot

最简单的快速排序可以固定选择第一个元素作为基准值：

int pivot = nums[left];

但是，如果输入数组本身已经接近有序：

[1, 2, 3, 4, 5]

每次都选择第一个元素，就可能得到极不平衡的划分：

[] | 1 | [2, 3, 4, 5] [] | 2 | [3, 4, 5] [] | 3 | [4, 5]

递归深度会接近n，时间复杂度退化为O(n²)。

因此，代码在当前区间中随机选择 pivot：

int randomIndex = left + RAND.nextInt(right - left + 1);

其中：

RAND.nextInt(right - left + 1)

生成：

0 ～ right - left

再加上left，最终范围就是：

left ～ right

随机选择不能彻底消除最坏情况，但可以大幅降低持续选中最大值或最小值的概率，使算法在实际运行中更稳定。

三、先把 pivot 放到区间开头

选择好 pivot 后，代码将它与nums[left]交换：

int pivot = nums[randomIndex]; swap(nums, randomIndex, left);

交换后，当前区间可以看成：

[pivot | 尚未划分的元素]

这样做是为了把 pivot 暂时单独保存到左端。后面的双指针只需要扫描：

[left + 1, right]

等划分完成后，再把 pivot 放到最终位置。

四、使用相向双指针划分数组

初始化两个指针：

int i = left + 1; int j = right;

数组在扫描过程中保持下面的结构：

[pivot | <= pivot | 尚未处理 | >= pivot] ↑ ↑ ↑ ↑ left i-1 j+1 right

也可以理解为：

• i左边已经处理过，元素都不大于 pivot。
• j右边已经处理过，元素都不小于 pivot。
• i～j之间还没有处理。

左指针寻找大数

while (i <= j && nums[i] < pivot) { i++; }

如果nums[i] < pivot，它本来就应该留在左边，所以i继续向右移动。

循环结束后，如果i没有越界，那么：

nums[i] >= pivot

右指针寻找小数

while (i <= j && nums[j] > pivot) { j--; }

如果nums[j] > pivot，它本来就应该留在右边，所以j继续向左移动。

循环结束后，如果指针没有交错，那么：

nums[j] <= pivot

此时，nums[i]在错误的一侧，nums[j]也在错误的一侧，所以交换它们：

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

重复这个过程，直到两个指针相遇或交错。

五、用一个例子理解 partition

以数组为例：

[5, 2, 3, 1, 4]

假设随机选中了3，先将它交换到区间开头：

[3, 2, 5, 1, 4] ↑ pivot

初始化：

i = 1 j = 4

左指针开始移动：

nums[1] = 2 < 3

所以i向右移动到下标2：

[3, 2, 5, 1, 4] ↑ ↑ i j

此时nums[i] = 5，不应该留在左边。

右指针从右向左寻找：

nums[4] = 4 > 3

所以j移到下标3：

[3, 2, 5, 1, 4] ↑ ↑ i j

此时：

nums[i] = 5 >= 3 nums[j] = 1 <= 3

交换它们：

[3, 2, 1, 5, 4]

然后：

i = 3 j = 2

两个指针已经交错，扫描结束。

六、为什么 pivot 要和 j 交换

扫描结束后，数组结构大致为：

[pivot | <= pivot | >= pivot] ↑ ↑ ↑ left j i

此时j是左侧区域的最后一个位置，因此将 pivot 与nums[j]交换：

swap(nums, left, j);

得到：

[<= pivot | pivot | >= pivot] ↑ j

在前面的例子中：

交换前：[3, 2, 1, 5, 4] 交换后：[1, 2, 3, 5, 4] ↑ pivot

为什么不和i交换？

首先，i可能已经等于right + 1，这时访问nums[i]会越界。其次，即使i没有越界，它通常也指向右侧区域，可能满足：

nums[i] > pivot

如果与i交换，就可能把一个大于 pivot 的数字放到区间最左边，破坏划分结果。

而j位于左侧区域，将 pivot 放到j的位置能够保证：

j 左边的元素 <= pivot j 右边的元素 >= pivot

所以partition()最后返回j：

return j;

七、递归排序左右区间

完成一次划分后，pivot 已经位于分界位置，不需要再次参与排序。

只需要递归处理它的左右两侧：

quickSort(nums, left, pivotIndex - 1); quickSort(nums, pivotIndex + 1, right);

整体过程就是：

原数组 ↓ partition 左区间 + pivot + 右区间 ↓ ↓ 递归排序 递归排序

当区间内最多只有一个元素时，区间天然有序，可以直接返回：

if (left >= right) { return; }

八、为什么扫描时使用严格比较

代码中使用的是：

nums[i] < pivot nums[j] > pivot

而不是：

nums[i] <= pivot nums[j] >= pivot

这与重复元素有关。

假设数组中所有元素都等于 pivot：

[2, 2, 2, 2, 2]

使用严格比较时，左右指针遇到等于 pivot 的元素都会停下来，然后交换并继续向中间移动：

i → ← j

最终两个指针会在区间中间附近相遇，使 pivot 也落在靠近中间的位置，左右区间相对均衡。

如果把相等元素全部跳过，它们可能集中到同一侧，递归区间会变得很不平衡，容易退化成O(n²)。

需要说明的是，这份代码属于双路划分，不是三路快速排序。它通过严格比较，让等于 pivot 的元素分散到左右两侧。三路快速排序则会直接划分出：

小于 pivot | 等于 pivot | 大于 pivot

当数组包含大量重复元素时，三路划分通常会更直接，因为等于 pivot 的区域不需要继续递归。

九、判断子数组是否已经有序

代码还增加了一个提前结束的优化：

boolean ordered = true; for (int i = left; i < right; i++) { if (nums[i] > nums[i + 1]) { ordered = false; break; } } if (ordered) { return; }

如果当前区间已经是升序：

[1, 2, 3, 4, 5]

就不需要继续选择 pivot 和递归划分，可以直接返回。

对于整个数组已经有序的情况，只需要扫描一次，时间复杂度可以达到O(n)。

不过，这个优化不是快速排序正确运行的必要条件。它会让每个递归区间多一次有序性检查，如果更看重代码简洁，也可以删除。删除后仍然是完整的随机化快速排序。

十、完整 Java 代码

import java.util.Random; class Solution { private static final Random RAND = new Random(); public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); return nums; } // 对闭区间 [left, right] 进行快速排序 private void quickSort(int[] nums, int left, int right) { if (left >= right) { return; } // 如果当前区间已经有序，直接结束 boolean ordered = true; for (int i = left; i < right; i++) { if (nums[i] > nums[i + 1]) { ordered = false; break; } } if (ordered) { return; } int pivotIndex = partition(nums, left, right); quickSort(nums, left, pivotIndex - 1); quickSort(nums, pivotIndex + 1, right); } // 对闭区间 [left, right] 进行划分 private int partition(int[] nums, int left, int right) { // 随机选择 pivot int randomIndex = left + RAND.nextInt(right - left + 1); int pivot = nums[randomIndex]; // 把 pivot 暂时放到区间开头 swap(nums, randomIndex, left); int i = left + 1; int j = right; while (true) { // 寻找左侧第一个大于等于 pivot 的元素 while (i <= j && nums[i] < pivot) { i++; } // 寻找右侧第一个小于等于 pivot 的元素 while (i <= j && nums[j] > pivot) { j--; } if (i >= j) { break; } swap(nums, i, j); i++; j--; } // 将 pivot 放到左右区域的分界处 swap(nums, left, j); return j; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }

十一、为什么这段代码能够完成排序

可以从三个方面理解它的正确性。

partition 完成了有效划分

执行完partition()后：

pivot 左边的元素 <= pivot pivot 右边的元素 >= pivot

因此，pivot 已经处在一个合法的排序位置。

递归解决规模更小的问题

接下来分别排序：

[left, pivotIndex - 1] [pivotIndex + 1, right]

这两个区间都比原区间更小。

递归最终会结束

当区间长度小于或等于 1 时：

left >= right

方法直接返回。

所以，左右子数组最终都会变得有序，再加上中间的 pivot，整个数组也就有序了。

十二、复杂度分析

时间复杂度

如果每次划分都比较均衡，递归树大约有log n层，每一层总共扫描n个元素：

O(n) × O(log n) = O(n log n)

因此，随机化快速排序的期望时间复杂度为：

O(n log n)

如果每次随机选中的 pivot 恰好都是当前区间的最大值或最小值，划分会极不平衡，最坏时间复杂度仍然是：

O(n²)

随机选择 pivot 降低了这种情况持续发生的概率，但不能提供严格的最坏O(n log n)保证。如果必须保证最坏时间复杂度，可以使用堆排序或归并排序。

空间复杂度

划分过程只使用几个变量：

partition 额外空间：O(1)

额外空间主要来自递归调用栈：

平均空间复杂度：O(log n) 最坏空间复杂度：O(n)

稳定性

快速排序不是稳定排序。相同数值的元素可能因为交换而改变原来的相对顺序。

十三、实现时需要注意的细节

随机范围要包含 right

当前区间是闭区间[left, right]，长度为：

right - left + 1

所以应该写成：

left + RAND.nextInt(right - left + 1)

少写一个+1，就永远选不到right。

递归区间不能再次包含 pivot

partition()返回后，pivot 已经确定位置，所以递归范围应当是：

[left, pivotIndex - 1] [pivotIndex + 1, right]

如果仍然把 pivot 包含进去，可能造成重复处理，甚至无法正常结束递归。

双指针移动时必须检查边界

应该先判断：

i <= j

再访问nums[i]或nums[j]：

while (i <= j && nums[i] < pivot)

Java 的&&具有短路特性。当i > j时，不会继续访问数组，因此可以避免下标越界。

重复元素不能全部推向同一侧

这里要保留严格比较：

nums[i] < pivot nums[j] > pivot

这样遇到等于 pivot 的元素时，两边指针都会停下并继续向中间收缩。

单独运行时需要导入 Random

LeetCode 编辑器可能已经提供常用导入，但在普通 Java 文件中应显式添加：

import java.util.Random;

十四、总结

这道题使用了随机化双路快速排序，核心有四步：

1. 在当前区间随机选择 pivot 2. 把 pivot 临时放到区间开头 3. 使用相向双指针完成划分 4. 递归排序 pivot 左右两侧

其中最值得理解的是partition()：

[pivot | <= pivot | 未处理 | >= pivot] ↓ [<= pivot | pivot | >= pivot]

随机 pivot 用来降低极端划分连续出现的概率；严格的<和>比较则让重复元素分散到两侧，避免全部集中在一个递归区间。

面试时可以这样回答：

我使用随机化快速排序。每次从当前区间随机选择一个 pivot，把它交换到区间开头，然后通过相向双指针寻找左侧大于等于 pivot 的元素和右侧小于等于 pivot 的元素并进行交换。指针交错后，将 pivot 与右指针位置交换，从而得到左侧不大于 pivot、右侧不小于 pivot 的划分，再递归排序左右区间。随机选择 pivot 可以降低有序输入导致退化的概率，算法期望时间复杂度为O(n log n)，平均递归空间为O(log n)。