本文详解如何在 java 中实现以数组中间元素为基准（pivot）的快速排序，修正原代码中混合分区逻辑导致的错误，并提供稳定、可复用的 hoare 分区方案及完整示例。
本文详解如何在 java 中实现以数组中间元素为基准（pivot）的快速排序，修正原代码中混合分区逻辑导致的错误，并提供稳定、可复用的 hoare 分区方案及完整示例。
快速排序的核心在于分区（partition）策略的正确性。原问题中的实现混淆了 Hoare 与 Lomuto 两种经典分区方式：既试图用 Hoare 的双向扫描逻辑，又混入了 Lomuto 风格的边界处理和 pivot 交换逻辑，导致分区后左右子数组划分错误（例如 pivot - 1 与 pivot + 1 的递归调用不匹配返回索引语义），最终引发排序结果错乱（如大小写混排异常、重复元素位置错误等）。
关键修复点有三：
- 统一采用 Hoare 分区法：该方法天然支持以任意位置（如中间）选取 pivot，且返回的是“左子数组右边界”，因此递归调用应为 quickSort(arr, start, pivot) 和 quickSort(arr, pivot + 1, end)，而非 pivot - 1；
- 预增/预减指针避免死循环：初始化 i = start - 1、j = end + 1，并在 while 循环内先 ++i / --j 再比较，确保指针始终向中心移动且不会越界；
- 严格基于 compareTo() 的升序语义：所有比较均使用 String.compareTo()，自然支持 ASCII 序（大写字母 'A'–'Z' 在小写 'a'–'z' 之前），无需额外大小写转换——这也解释了为何输入含大小写混合时原输出 A A B C D F g Z b c d e 是错误的（g 和 Z 位置颠倒，且 b c d e 被错误移到末尾）。
以下是修正后的完整、可直接运行的实现：
private static void quickSort(String[] arr, int start, int end) {
if (end <= start) return;
int pivotIndex = partition(arr, start, end);
quickSort(arr, start, pivotIndex); // 左半区：[start, pivotIndex]
quickSort(arr, pivotIndex + 1, end); // 右半区：[pivotIndex + 1, end]
}
private static int partition(String[] arr, int start, int end) {
// 选取中间元素作为 pivot（下标取整，自动处理偶数长度）
int mid = start + (end - start) / 2;
String pivot = arr[mid];
int i = start - 1;
int j = end + 1;
while (true) {
// 从左向右找第一个 >= pivot 的元素
while (arr[++i].compareTo(pivot) < 0);
// 从右向左找第一个 <= pivot 的元素
while (arr[--j].compareTo(pivot) > 0);
if (i >= j) {
return j; // Hoare 分区返回左子数组的最后一个有效索引
}
// 交换不满足条件的元素
String temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}使用示例与验证：
public static void main(String[] args) {
String[] arr = {"D", "C", "B", "A", "A", "Z", "g", "F", "e", "d", "c", "b"};
quickSort(arr, 0, arr.length - 1);
System.out.println(java.util.Arrays.toString(arr));
// 输出：[A, A, B, C, D, F, Z, b, c, d, e, g]
}✅ 正确输出符合字典序升序：所有大写字母（ASCII 65–90）排在小写字母（ASCII 97–122）之前，且相同字母按出现顺序稳定排列（注意：此实现不保证稳定排序，因交换可能改变相等元素相对位置；若需稳定性，应改用归并排序或带索引的增强快排）。
注意事项：
- 该实现对空数组、单元素、已排序/逆序数组均鲁棒；
- 时间复杂度平均为 O(n log n)，最坏（如每次选到极值）为 O(n²)；可通过随机化 pivot 位置进一步优化；
- 若需忽略大小写排序，可在 compareTo() 前统一转为 toLowerCase()，但需注意这会改变原始字符串内容，建议使用 String.CASE_INSENSITIVE_ORDER.compare(a, b) 替代。
掌握 Hoare 分区的指针移动逻辑与递归边界语义，是写出正确、高效快排的关键——中间 pivot 不仅提升平均性能，更避免了首/尾元素退化情形。
