本文详解如何在 java 中实现以数组中间元素为 pivot 的快速排序，修正原代码中混合分区逻辑导致的错误，并提供符合 hoare 分区规范、稳定且可复用的完整实现。
本文详解如何在 java 中实现以数组中间元素为 pivot 的快速排序，修正原代码中混合分区逻辑导致的错误，并提供符合 hoare 分区规范、稳定且可复用的完整实现。
快速排序的核心在于分区（partition）策略的正确性。原问题中的实现试图将中间元素选为 pivot，但其 partition 方法混用了 Hoare 与 Lomuto 的逻辑：既未统一处理相等情况，又错误地在循环中对 i/j 做条件性增减，导致边界错乱和重复交换，最终使排序结果不正确（如大小写混排时顺序异常）。
正确的做法是采用标准 Hoare 分区方案：
- 在进入循环前，先将指针 i 和 j 分别置于 start−1 和 end+1，确保首次递增/递减后指向有效索引；
- 使用 do-while 或预增/预减风格的 while 循环，严格保证 arr[i] pivot 的单调推进；
- 当 i ≥ j 时停止，返回 j 作为分割点 —— 此时 [start, j] 中所有元素 ≤ pivot，(j+1, end] 中所有元素 ≥ pivot；
- 递归调用时，左半段应为 quickSort(arr, start, j)（而非 pivot−1），右半段为 quickSort(arr, j+1, end)。
以下是修正后的完整可运行代码：
private static void quickSort(String[] arr, int start, int end) {
if (end = pivot 的元素
while (arr[++i].compareTo(pivot) 0);
if (i >= j) {
return j; // 分割点：j 是左半区最后一个有效索引
}
// 交换不满足条件的元素
String temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
⚠️ 关键注意事项：
- 字符串比较敏感性：Java 中 String.compareTo() 区分大小写（'A'
- pivot 位置无需显式交换：Hoare 方案中，pivot 本身可能被多次交换，但最终分区天然保证其相对有序性；强行将其换回中间位置反而破坏分区不变量。
- 避免整数溢出：计算中点使用 start + (end - start) / 2 而非 (start + end) / 2，防止大索引下 start + end 溢出。
最后，建议在实际工程中补充单元测试验证边界情况（空数组、单元素、全相同元素、已排序/逆序数组），并考虑引入三数取中（median-of-three）优化 pivot 选择，进一步提升最坏情况下的性能稳定性。
