高效实现快速排序：Hoare分区法详解

private static int getPivotIndex(int[] arg, int startIndex, int endIndex) {
    int pivotVal = arg[startIndex]; // 选择子数组的第一个元素作为基准值
    int i = startIndex;
    int j = endIndex; // 注意：endIndex在此处是独占的，即子数组范围是 [startIndex, endIndex-1]

    while (i < j) {
        // 从右向左遍历，寻找第一个小于基准值的元素
        // 遇到大于等于基准值的元素时，j指针继续向左移动
        while (i < j && (arg[--j] >= pivotVal));
        // 如果找到小于基准值的元素（且i < j），将其移动到i指针当前位置
        if (i < j)
            arg[i] = arg[j];

        // 从左向右遍历，寻找第一个大于基准值的元素
        // 遇到小于等于基准值的元素时，i指针继续向右移动
        while (i < j && (arg[++i] <= pivotVal));
        // 如果找到大于基准值的元素（且i < j），将其移动到j指针当前位置
        if (i < j)
            arg[j] = arg[i];

    } // 当i >= j时，循环结束，此时i和j指向同一个位置，即基准值的最终位置

    // 将基准值放到其最终的排序位置
    arg[j] = pivotVal;
    // 返回基准值的索引
    return j;
}

static void quickSort(int[] arg, int startIndex, int endIndex) {
    // 基本情况：如果子数组的长度小于2，则无需分区，直接返回
    // 数组长度为0或1时，认为已经有序
    if (endIndex - startIndex < 2)
        return;

    // 调用getPivotIndex方法进行分区，获取基准值的最终索引
    int pivotIndex = getPivotIndex(arg, startIndex, endIndex);

    // 递归排序基准值左侧的子数组
    quickSort(arg, startIndex, pivotIndex);
    // 递归排序基准值右侧的子数组
    quickSort(arg, pivotIndex + 1, endIndex);
}

public class QuickSort_Impl {

    public static void main(String[] args) {
        int[] unsortedArray = {12, 3, 45, 23, 6, -4, -6, 10, 1, 8};

        // 调用快速排序方法
        // 注意：endIndex通常是数组长度，表示排序范围是 [0, unsortedArray.length-1]
        quickSort(unsortedArray, 0, unsortedArray.length);

        // 打印排序后的数组
        System.out.println("排序后的数组：");
        for (int i : unsortedArray)
            System.out.print(i + " ");
        System.out.println();
    }

    /**
     * 快速排序主方法
     *
     * @param arg        待排序数组
     * @param startIndex 子数组起始索引（包含）
     * @param endIndex   子数组结束索引（不包含）
     */
    static void quickSort(int[] arg, int startIndex, int endIndex) {
        // 基本情况：如果子数组的长度小于2，则无需分区，直接返回
        if (endIndex - startIndex < 2)
            return;

        // 调用getPivotIndex方法进行分区，获取基准值的最终索引
        int pivotIndex = getPivotIndex(arg, startIndex, endIndex);

        // 递归排序基准值左侧的子数组
        quickSort(arg, startIndex, pivotIndex);
        // 递归排序基准值右侧的子数组
        quickSort(arg, pivotIndex + 1, endIndex);
    }

    /**
     * Hoare分区法实现，将数组根据基准值分为两部分，并返回基准值的最终索引
     *
     * @param arg        待分区数组
     * @param startIndex 子数组起始索引（包含）
     * @param endIndex   子数组结束索引（不包含）
     * @return 基准值的最终索引
     */
    private static int getPivotIndex(int[] arg, int startIndex, int endIndex) {
        int pivotVal = arg[startIndex]; // 选择子数组的第一个元素作为基准值
        int i = startIndex;
        int j = endIndex; // 注意：endIndex在此处是独占的，即子数组范围是 [startIndex, endIndex-1]

        // 当i < j时，双指针继续移动和交换
        while (i < j) {
            // 从右向左遍历，寻找第一个小于基准值的元素
            // j指针先自减，再进行比较
            while (i < j && (arg[--j] >= pivotVal));
            // 如果找到小于基准值的元素，将其移动到i指针当前位置
            if (i < j)
                arg[i] = arg[j];

            // 从左向右遍历，寻找第一个大于基准值的元素
            // i指针先自增，再进行比较
            while (i < j && (arg[++i] <= pivotVal));
            // 如果找到大于基准值的元素，将其移动到j指针当前位置
            if (i < j)
                arg[j] = arg[i];

        } // 循环结束时，i和j指向同一个位置，即基准值的最终位置

        // 将基准值放到其最终的排序位置
        arg[j] = pivotVal;
        // 返回基准值的索引
        return j;
    }
}