三数取中法选基准可避免快排最坏情况：取首、中、尾三元素中位数作pivot并移至末尾，再用双指针三路分区，提升有序数组性能。
在 java 中实现快速排序的分区逻辑，核心是选好基准（pivot），并把数组划分为“小于 pivot”、“等于 pivot”、“大于 pivot”三部分。关键在于避免最坏情况——即每次选到最小或最大元素作 pivot，导致递归深度退化为 o(n)，总时间复杂度升至 o(n²)。这通常发生在已排序或近乎有序的数组上。
用三数取中法选 pivot，避开有序数组陷阱
不直接取首/尾/中间任一固定位置，而是取首、中、尾三个元素的中位数作为 pivot，并将其交换到末尾（或开头）再分区。这样能显著降低在单调序列中选到极值的概率。
- 计算索引：
int left = 0, right = arr.length - 1, mid = left + (right - left) / 2 - 对
arr[left]、arr[mid]、arr[right]排序（仅三次比较），把中位数放到arr[right] - 后续分区以
arr[right]为 pivot，保持标准单边扫描逻辑
双指针三路分区（Dutch National Flag 风格）
相比传统两路分区（
- 维护三个区间：
[0, lt)小于 pivot，[lt, gt]等于 pivot，(gt, n-1]大于 pivot - 初始化：
lt = 0, i = 0, gt = arr.length - 1 - 遍历中：遇到小于 pivot → 与
lt交换，lt++，i++；等于 →i++；大于 → 与gt交换，gt--（i不增）
小数组改用插入排序，剪枝递归开销
当子数组长度 ≤ 10（经验值，可调），直接插入排序比继续递归快得多，且规避了深度递归带来的栈溢出和 pivot 选择失准风险。
- 在递归入口加判断：
if (right - left + 1 - 插入排序实现简单：外层从
left+1到right，内层向左找插入位置
随机化预处理（轻量兜底）
若无法保证输入分布，可在排序前对数组做一次随机洗牌（Fisher–Yates），让任意输入在概率意义上“平均化”。这对对抗恶意构造数据特别有效，且开销仅为 O(n)。
- 使用
ThreadLocalRandom.current()避免多线程竞争 - 代码片段：
for (int i = arr.length - 1; i > 0; i--) { int j = ThreadLocalRandom.current().nextInt(i + 1); swap(arr, i, j); }
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
