迭代式Hoare快速排序仅交换两元素问题排查求助

你遇到的问题核心是代码完全没有实现算法描述中的循环迭代逻辑，同时还有几个关键细节错误，导致程序只执行了一次分区操作就直接返回了。下面逐个拆解问题：

1. 最严重的问题：缺失核心循环逻辑 #

算法描述里明确要求了多个循环跳转（比如步骤10回到步骤8、步骤13回到步骤6、步骤14回到步骤4），但你的secondMethod函数只是一次性执行了部分步骤，没有用循环来模拟这些跳转逻辑：

• 算法步骤10要求当i<=j时回到步骤8继续分区，但你调用partition后，又写了一段多余的if(i<=j)逻辑，完全没起到循环作用；
• 算法步骤13要求当l<r时回到步骤6处理左子数组，你代码里只是写了个while(true) { M=median(a); break; }，这相当于啥也没做；
• 算法步骤14要求栈不为空时回到步骤4弹出栈处理子数组，你代码里只执行了一次stackpos--就break，没有循环处理所有栈中的子数组。

这直接导致程序只完成了一次分区交换（把10和5互换），就终止了排序过程。

2. 中位数选取错误 #

算法步骤6要求从当前子数组a[l]到a[r]中选取中位数，但你的median函数是从整个数组里随机选元素，这会导致基准值可能不在当前处理的子数组范围内，破坏分区逻辑。比如这次运行可能随机选了10作为基准，导致分区只交换了10和5就结束。

3. 变量处理与算法步骤不符 #

• 算法步骤12是将j赋值给r（处理左子数组的右边界），但你代码里写的r=j后续没有用来触发循环处理左子数组；
• 栈的使用逻辑错误：算法里是把需要处理的子数组边界压入栈，然后循环弹出处理，但你代码里只压入了一次可能的右子数组，没有压入左子数组，也没有循环弹出栈元素。

修正后的迭代版Hoare快速排序代码 #

下面是按照你给出的算法逻辑修正后的代码，修复了上述所有问题：

import java.util.Random;

public class IterativeHoareQuickSort {
    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    // 从指定子数组[l, r]中随机选取基准值
    public static int median(int[] a, int l, int r) {
        Random random = new Random();
        int rnd = l + random.nextInt(r - l + 1);
        return a[rnd];
    }

    // Hoare分区方法，完成分区后返回左指针位置
    private static int partition(int[] a, int l, int r, int M) {
        int i = l;
        int j = r;
        while (i <= j) {
            while (a[i] < M) {
                i++;
            }
            while (a[j] > M) {
                j--;
            }
            if (i <= j) {
                swap(a, i, j);
                i++;
                j--;
            }
        }
        return i;
    }

    public static int[] secondMethod(int[] a) {
        int N = a.length;
        if (N <= 1) return a;

        // 用数组模拟栈，存储子数组的左右边界
        int[] left = new int[N / 2];
        int[] right = new int[N / 2];
        int stackpos = 0;

        // 初始压入整个数组的边界
        left[stackpos] = 0;
        right[stackpos] = N - 1;
        stackpos++;

        // 循环处理栈中的所有子数组
        while (stackpos > 0) {
            stackpos--;
            int l = left[stackpos];
            int r = right[stackpos];

            if (l >= r) continue; // 子数组长度为0或1，无需处理

            // 选取当前子数组的基准值
            int M = median(a, l, r);
            int i = partition(a, l, r, M);
            int j = i - 1; // 分区后j的位置是i-1

            // 将右子数组[i, r]压入栈（先压右，后压左，保证栈的LIFO顺序）
            if (i < r) {
                left[stackpos] = i;
                right[stackpos] = r;
                stackpos++;
            }

            // 将左子数组[l, j]压入栈
            if (l < j) {
                left[stackpos] = l;
                right[stackpos] = j;
                stackpos++;
            }
        }

        return a;
    }

    public static void main(String[] args) {
        int[] a = {10, 7, 8, 9, 1, 5};
        a = secondMethod(a);
        System.out.println("result :");
        for (int num : a) {
            System.out.print(num + " ");
        }
    }
}

修正点说明： #

1. 补全了栈的循环处理逻辑：用while(stackpos > 0)循环弹出栈中的子数组边界，直到栈为空；
2. 修复了中位数选取逻辑：median函数现在接收子数组的l和r参数，只在当前子数组范围内随机选基准；
3. 正确处理子数组压栈：分区后将左、右子数组的边界都压入栈，保证所有子数组都会被处理；
4. 简化了分区函数：将分区逻辑整合，返回正确的分区指针；
5. 移除了多余的无效代码：删掉了原代码中那些while(true) break的无效逻辑。

运行修正后的代码，输出会是正确的排序结果：1 5 7 8 9 10。

内容的提问来源于stack exchange，提问作者expyo