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

作者逆境不可逃技术永无止境希望我的内容可以帮助到你LeetCode 912「排序数组」要求我们在不调用内置排序函数的情况下将整数数组按升序排列。数组长度最多为5 × 10⁴并且可能包含大量重复元素因此需要选择效率较高的排序算法。这篇文章使用随机化快速排序解决问题。核心过程可以概括为随机选择一个基准值 pivot ↓ 把数组划分到 pivot 两侧 ↓ 递归排序左右两个子数组快速排序平均时间复杂度为O(n log n)划分过程直接在原数组上完成不需要额外创建左右数组。一、快速排序的基本思路假设当前需要排序的区间为[5, 2, 3, 1, 4]从中选择一个元素作为基准值。为了方便讲解假设选中3pivot 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²)。因此代码在当前区间中随机选择 pivotint 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 j1 right也可以理解为i左边已经处理过元素都不大于 pivot。j右边已经处理过元素都不小于 pivot。ij之间还没有处理。左指针寻找大数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()最后返回jreturn 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。递归区间不能再次包含 pivotpartition()返回后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 的元素时两边指针都会停下并继续向中间收缩。单独运行时需要导入 RandomLeetCode 编辑器可能已经提供常用导入但在普通 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)。