如何为已实现分区的Java快速排序算法添加递归逻辑？

嘿，我太懂这种感觉了——手动推演快排逻辑溜得很，分区代码也搞定了，结果到递归这儿突然卡壳，完全不知道怎么把分区和递归串起来对吧？别担心，咱们一步步来拆解！

先理清楚递归的核心逻辑 #

快排的本质是分治思想：每次分区后，基准值（pivot）已经处于它最终应该在的位置了——左边的元素都比它小，右边的都比它大。你要做的，就是对基准值左边的子数组、右边的子数组，重复同样的排序操作，直到子数组小到不需要排序（比如只有1个元素或者空数组）。

结合你的分区代码，补全递归部分 #

假设你已经实现了标准的分区函数（比如下面这个Lomuto分区，选最后一个元素当基准值），咱们直接把递归逻辑加进去：

// 你已经搞定的分区函数：返回基准值最终的索引位置
private static int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1; // 标记小于pivot的元素的最后位置
    
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            // 交换arr[i]和arr[j]，把小于pivot的元素移到左边
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 把基准值放到它的最终位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[right];
    arr[right] = temp;
    
    return i + 1;
}

// 对外暴露的快排入口
public static void quickSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return; // 空数组或单个元素直接返回
    }
    // 调用递归核心函数，初始边界是整个数组
    quickSort(arr, 0, arr.length - 1);
}

// 递归核心逻辑
private static void quickSort(int[] arr, int left, int right) {
    // 🔴 递归终止条件：子数组为空或只有一个元素，无需排序
    if (left >= right) {
        return;
    }
    
    // 第一步：分区，得到基准值的最终索引
    int pivotIndex = partition(arr, left, right);
    
    // 第二步：递归排序基准值左边的子数组（left 到 pivotIndex-1）
    quickSort(arr, left, pivotIndex - 1);
    // 第三步：递归排序基准值右边的子数组（pivotIndex+1 到 right）
    quickSort(arr, pivotIndex + 1, right);
}

关键细节解释 #

• 递归终止条件：left >= right 是必须的，不然会无限递归下去。比如当子数组只有一个元素时，left等于right，直接返回；如果基准值是子数组的第一个元素，左边没有元素，left会大于right，同样直接返回。
• 为什么要排除pivotIndex？：分区后，基准值已经在正确的位置了，不需要再参与排序，所以递归的子区间要跳过它。

测试一下效果 #

可以加个main函数验证：

public static void main(String[] args) {
    int[] arr = {10, 7, 8, 9, 1, 5};
    System.out.println("排序前：");
    for (int num : arr) {
        System.out.print(num + " ");
    }
    
    quickSort(arr);
    
    System.out.println("\n排序后：");
    for (int num : arr) {
        System.out.print(num + " ");
    }
}

运行后会输出：

排序前：
10 7 8 9 1 5 
排序后：
1 5 7 8 9 10 

其实递归部分就是把分区后的两个子数组再丢给快排函数处理，核心就是记住把大问题拆成小问题，每个小问题用同样的方法解决，是不是瞬间清晰了？

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