Java实现维基百科Lomuto分区快速排序失败，求问题排查

嘿，我完全理解你现在的焦虑——期末考在即，照着维基百科的伪代码写快排却始终跑不对，肯定急坏了！咱们先把Lomuto分区的核心逻辑理清楚，再一步步排查你代码里可能踩的坑。

首先，先明确维基百科上Lomuto分区的标准伪代码（避免你记错细节）：

function partition(A, lo, hi) is
pivot := A[hi]
i := lo - 1
for j := lo to hi - 1 do
if A[j] ≤ pivot then
i := i + 1
swap A[i] and A[j]
swap A[i + 1] and A[hi]
return i + 1

最容易踩的几个坑（也是你代码大概率出问题的地方） #

• Pivot选择错误：Lomuto方案固定选A[hi]（最后一个元素）作为基准，如果你选了第一个元素或者其他位置，逻辑直接就乱了
• 循环边界错误：遍历的j必须从lo到hi-1，不能包含hi（因为那是pivot的位置）
• 返回值错误：分区完成后必须返回i+1（pivot最终的索引），而不是i
• 递归参数错误：递归排序时，左半部分是l到k-1，右半部分是k+1到r——k位置的pivot已经在正确位置，不需要再处理

完整的正确Java实现 #

下面是严格遵循Lomuto方案的原地快排代码，你可以对比自己的代码找差异：

public class QuickSortLomuto {
    private static void quickSort(Integer A[], int l, int r) {
        // 只有当左边界小于右边界时才需要排序
        if (l < r) {
            // 获取分区后pivot的索引
            int k = partition(A, l, r);
            // 递归排序左半部分（所有<=pivot的元素）
            quickSort(A, l, k - 1);
            // 递归排序右半部分（所有>pivot的元素）
            quickSort(A, k + 1, r);
        }
    }

    private static int partition(Integer A[], int lo, int hi) {
        // Lomuto方案：选最后一个元素作为基准
        int pivot = A[hi];
        // i标记"小于等于pivot的区域"的最后一个索引，初始为空区域（lo-1）
        int i = lo - 1;

        // 遍历除了pivot之外的所有元素
        for (int j = lo; j <= hi - 1; j++) {
            // 如果当前元素<=pivot，就把它加入"小于等于区域"
            if (A[j] <= pivot) {
                i++;
                // 交换到区域的下一个位置
                swap(A, i, j);
            }
        }

        // 最后把pivot放到"小于等于区域"的下一个位置，也就是它的正确位置
        swap(A, i + 1, hi);
        // 返回pivot的最终索引
        return i + 1;
    }

    // 工具方法：交换数组中两个位置的元素
    private static void swap(Integer[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    // 测试用例
    public static void main(String[] args) {
        Integer[] testArr = {3, 1, 4, 1, 5, 9, 2, 6};
        System.out.println("排序前：");
        for (int num : testArr) {
            System.out.print(num + " ");
        }
        quickSort(testArr, 0, testArr.length - 1);
        System.out.println("\n排序后：");
        for (int num : testArr) {
            System.out.print(num + " ");
        }
    }
}

关键逻辑解释 #

1. 分区过程：i始终指向小于等于pivot的最后一个元素，初始时这个区域为空（lo-1）。遍历每个元素时，只要它<=pivot，就把它交换到i+1的位置，同时i右移，扩大这个区域。
2. pivot归位：遍历结束后，i+1的位置就是pivot应该在的地方——左边全是<=它的元素，右边全是>它的元素。
3. 递归逻辑：把数组分成左右两部分，分别递归排序，因为pivot已经在正确位置，不需要再处理它。

你可以把自己的代码和上面的对比，重点检查partition方法的循环边界、pivot选择、返回值，还有quickSort的递归参数，应该就能找到问题啦！

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