随机化快排通过每次划分前随机选基准，打破输入恶意结构，使期望时间复杂度为O(n log n)；最坏情况概率降至1/n!，避免固定pivot导致的O(n²)退化。
在 Java 中，通过随机化快速排序（Randomized Quicksort）可以有效降低最坏情况 O(n²) 出现的概率，使其在统计学意义上趋近于期望时间复杂度 O(n log n)。核心思路不是改变算法逻辑，而是打破输入数据的“恶意结构”——比如已排序、逆序或大量重复元素，这些正是传统快排退化为 O(n²) 的常见诱因。关键在于：每次划分前，随机选择一个元素作为基准（pivot），并将其与末尾（或开头）元素交换，再执行标准分区操作。
为什么随机化能规避 O(n²) 风险
确定性快排的 pivot 若总选首/尾/中位数固定位置，在面对已排序数组时会持续划分出 1 和 n−1 的子数组，导致递归深度达 n 层。而随机化 pivot 使得：
– 每次划分得到“相对平衡”子数组的概率显著提高；
– 最坏情况（每次都选到极值）发生的概率降为 1/n!（对任意固定输入）；
– 期望比较次数稳定在 ≈ 1.39 n log₂ n，与输入分布无关。
用数组实现的随机化快排（Java 示例）
以下是一个基于 原地分区（Lomuto 分区方案）、使用 int[] 数组 的简洁实现：
// 工具方法：生成 [low, high) 范围内的随机索引
private static int randomIndex(Random rand, int low, int high) {
return rand.nextInt(high - low) + low;
}
public static void randomizedQuickSort(int[] arr, int low, int high, Random rand) {
if (low
// 1. 随机选 pivot 索引，并与末尾交换
int randIdx = randomIndex(rand, low, high);
swap(arr, randIdx, high - 1);
// 2. 标准 Lomuto 分区（以 arr[high-1] 为 pivot）
int pivotIndex = partition(arr, low, high);
// 3. 递归处理左右子数组
randomizedQuickSort(arr, low, pivotIndex, rand);
randomizedQuickSort(arr, pivotIndex + 1, high, rand);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high - 1];
int i = low;
for (int j = low; j
if (arr[j]
swap(arr, i, j);
i++;
}
}
swap(arr, i, high - 1);
return i;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
实用建议与注意事项
– 务必复用同一个 Random 实例：避免在递归中新建 Random（尤其是 new Random() 无参构造），否则可能因系统纳秒时间相近导致重复种子，削弱随机性；建议传入外部创建的 Random 对象（如 new Random(System.nanoTime())）。
– 小数组改用插入排序：当子数组长度 ≤ 10 左右时，切换为插入排序，减少递归开销并提升常数因子；
– 重复元素多？考虑三路快排：若数据含大量重复值（如计数统计场景），仅随机化不够，应结合荷兰国旗分区（将数组分为 pivot 三段），避免重复递归处理相等块；
– 不适用于链表或不可随机访问结构：本方案依赖数组 O(1) 索引，若需泛型支持，可封装为 <T extends Comparable<T>> 并配合 Comparator。
验证随机化效果的小技巧
可通过统计实际递归深度或比较次数来观察稳定性：
– 对同一数组（如升序 int[10000]）运行 100 次，记录最大递归深度；
– 确认 99% 以上运行中深度 ≤ 3×log₂n（例如 n=10⁴ 时深度通常
– 对比未随机化版本：相同输入下，其深度几乎恒为 n，一目了然。
