Java实现快速排序无法正确排序，请求排查partition方法问题

开发者阿泽

2026-6-20

快速排序实现错误排查：Partition方法返回值错误

你的快速排序核心问题出在partition方法的返回值上：

你在partition方法最后将pivot交换到了i+1的位置，但返回的是i，这导致递归时的分界点错误。
正确的返回值应该是i+1——因为这个位置才是pivot最终的正确索引，后续递归需要以此为界，分别排序左半部分（low到pi-1）和右半部分（pi+1到high）。

修正后的Partition方法

仅需修改返回值一行：

int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = (low-1);
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            
            // Swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    // Swap arr[i+1] and arr[high] (or pivot)
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    
    return i+1; // 此处从i改为i+1
}