基于Hoare分区策略的快速排序算法详解与实现

快速排序概述

快速排序（quicksort）是一种基于比较的排序算法，由tony hoare发明。其核心思想是“分而治之”：从数组中选择一个元素作为“枢轴”（pivot），通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比枢轴小，另一部分的所有数据都比枢轴大。然后，再对这两部分数据分别进行快速排序，递归地完成整个排序过程。

快速排序的性能高度依赖于枢轴的选择和分区策略。常见的枢轴选择有选择第一个元素、最后一个元素、中间元素或随机元素。分区策略主要有Lomuto分区和Hoare分区。本文将重点介绍并实现基于Hoare分区策略的快速排序。

Hoare分区策略详解

Hoare分区策略是快速排序最初提出的分区方法，它使用两个指针从数组两端向中间移动，以实现元素的重新排列。我们这里实现的Hoare-like分区会确保枢轴最终位于其正确位置，并且其左右两侧的元素分别小于等于和大于等于枢轴。

核心思想

1. 选择枢轴： 通常选择当前子数组的第一个元素作为枢轴值（pivotVal）。
2. 双指针移动： 初始化两个指针 i 和 j，i 从子数组的起始位置开始，j 从子数组的结束位置（不包含）开始。
3. 交替搜索与元素移动：
   • 指针 j 从右向左移动，直到找到一个小于等于 pivotVal 的元素。
   • 如果 i < j，将 arg[j] 移动到 arg[i] 的位置。
   • 指针 i 从左向右移动，直到找到一个大于等于 pivotVal 的元素。
   • 如果 i < j，将 arg[i] 移动到 arg[j] 的位置。
   • 这个过程持续进行，直到 i 和 j 相遇或交叉。
4. 枢轴归位： 当 i 和 j 相遇或交叉时，循环结束。此时，j 指针的位置就是枢轴的最终位置。将最初保存的 pivotVal 放置到 arg[j]。
5. 返回枢轴索引： 返回 j 作为枢轴的最终索引。

getPivotIndex 方法实现

以下是实现Hoare分区策略的关键方法 getPivotIndex 的详细解析：

private static int getPivotIndex(int[] arg, int startIndex, int endIndex) {
    int pivotVal = arg[startIndex]; // 1. 选择子数组的第一个元素作为枢轴值
    int i = startIndex;
    int j = endIndex; // 注意：这里的 endIndex 是 exclusive，表示子数组的结束索引+1

    // 遍历直到指针 i 和 j 相遇或交叉
    while (i < j) {
        // 2. 指针 j 从右向左移动，寻找小于等于 pivotVal 的元素
        // --j 是因为 endIndex 是 exclusive，所以 j 实际从 arg[endIndex - 1] 开始向左遍历
        while (i < j && (arg[--j] >= pivotVal));
        // 如果找到，并且 i 仍在 j 的左侧，将 arg[j] 移动到 arg[i] 的位置
        if (i < j)
            arg[i] = arg[j];

        // 3. 指针 i 从左向右移动，寻找大于等于 pivotVal 的元素
        // ++i 是因为 i 实际从 arg[startIndex] 开始向右遍历
        while (i < j && (arg[++i] <= pivotVal));
        // 如果找到，并且 i 仍在 j 的左侧，将 arg[i] 移动到 arg[j] 的位置
        if (i < j)
            arg[j] = arg[i];

    } // End Outer while

    // 4. 将枢轴值放置到其最终排序位置
    arg[j] = pivotVal;
    // 5. 返回枢轴的最终索引
    return j;
}

注意事项：

算家云

高效、便捷的人工智能算力服务平台

37

查看详情

• endIndex 参数在Java中通常表示不包含的结束索引（exclusive），例如 Arrays.sort(array, 0, array.length)。在 getPivotIndex 方法中，j 的初始值是 endIndex，因此 arg[--j] 实际上是从 arg[endIndex - 1] 开始向左遍历。
• 内部 while 循环中的 i < j 条件是必要的，以防止指针越界。
• 当 arg[--j] >= pivotVal 或 arg[++i] <= pivotVal 时，指针会继续移动。只有当找到不满足条件的元素时，才会停止并进行潜在的赋值操作。
• 这种赋值方式 (arg[i] = arg[j] 和 arg[j] = arg[i]) 实际上是利用了 pivotVal 的临时存储，实现了元素的移动，使得小于枢轴的元素最终集中在左侧，大于枢轴的元素集中在右侧。

快速排序主算法实现

quickSort 方法是递归地调用分区方法，并对子数组进行排序的核心。

static void quickSort(int[] arg, int startIndex, int endIndex) {
    // 递归终止条件：当子数组的长度小于2时，表示无法再分区，或者已经排序完成
    if (endIndex - startIndex < 2)
        return;

    // 获取枢轴的最终位置
    int pivotIndex = getPivotIndex(arg, startIndex, endIndex);

    // 对枢轴左侧的子数组进行快速排序
    quickSort(arg, startIndex, pivotIndex);
    // 对枢轴右侧的子数组进行快速排序
    quickSort(arg, pivotIndex + 1, endIndex);
}

注意事项：

• 基准情况 (Base Case): endIndex - startIndex < 2 是递归的终止条件。这意味着当子数组只包含一个元素或为空时，它已经是排序好的，无需进一步处理。
• 递归调用:
  • quickSort(arg, startIndex, pivotIndex)：对枢轴左侧的子数组进行排序。注意，这里的 pivotIndex 是枢轴所在的最终位置，因此左侧子数组的范围是 [startIndex, pivotIndex)。
  • quickSort(arg, pivotIndex + 1, endIndex)：对枢轴右侧的子数组进行排序。右侧子数组的范围是 [pivotIndex + 1, endIndex)。

完整示例代码

以下是包含 main 方法的完整Java实现，

以上就是基于Hoare分区策略的快速排序算法详解与实现的详细内容，更多请关注php中文网其它相关文章！