Hoare分区法快速排序教程与代码实现

本文深入剖析了快速排序中Hoare分区法的正确实现要点，聚焦于以数组中间元素为pivot时常见逻辑混淆问题——特别是原代码混用Hoare与Lomuto分区策略导致的边界错乱、重复交换和排序失效；通过严格遵循Hoare规范（预置指针、do-while式推进、以j为分割点）、修正字符串大小写敏感性处理、规避整数溢出及强调pivot无需手动归位等关键细节，提供了一套稳定、可复用、经过原理验证的Java实现，并辅以工程化建议如单元测试和三数取中优化，助你真正掌握高效排序的底层逻辑。

本文详解如何在 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 和 arr[j] > 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 <= start) return;
    int pivotIndex = partition(arr, start, end);
    quickSort(arr, start, pivotIndex);     // 左区间包含 pivotIndex
    quickSort(arr, 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; // 分割点：j 是左半区最后一个有效索引
        }

        // 交换不满足条件的元素
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

⚠️ 关键注意事项：

• 字符串比较敏感性：Java 中 String.compareTo() 区分大小写（'A' < 'a'，ASCII 值 65 < 97），因此 "A" 会排在 "a" 之前。若需忽略大小写排序，应改用 String.CASE_INSENSITIVE_ORDER.compare(a, b) 或预处理转小写。
• pivot 位置无需显式交换：Hoare 方案中，pivot 本身可能被多次交换，但最终分区天然保证其相对有序性；强行将其换回中间位置反而破坏分区不变量。
• 避免整数溢出：计算中点使用 start + (end - start) / 2 而非 (start + end) / 2，防止大索引下 start + end 溢出。

最后，建议在实际工程中补充单元测试验证边界情况（空数组、单元素、全相同元素、已排序/逆序数组），并考虑引入三数取中（median-of-three）优化 pivot 选择，进一步提升最坏情况下的性能稳定性。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《Hoare分区法快速排序教程与代码实现》文章吧，也可关注golang学习网公众号了解相关技术文章。