Java递归冒泡排序出现超时（TLE）问题，求原因排查

问题描述 #

我编写了递归实现的冒泡排序Java代码，但运行时出现超时（Time limit exceeded）问题，恳请帮忙排查原因。

代码如下：

public static void bubbleSort(int[] arr, int index, int j){
        if (index == arr.length) return;
        if (j == arr.length-1) return;
        if (arr[j] > arr[j+1]) {
            int temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
        bubbleSort(arr, index, j+1);
        //print(arr);
        bubbleSort(arr, index+1, 0);
    }

函数调用方式：bubbleSort(arr, 0, 0);

超时原因 #

你的递归逻辑存在重复递归调用的致命问题，直接导致时间复杂度飙升至O(2^n)，远超过正常冒泡排序的O(n²)，最终触发超时：

• 每一次bubbleSort(arr, index, j+1)执行完毕返回后，都会立刻调用bubbleSort(arr, index+1, 0)
• 这意味着同一个index会被多次触发递归，而非正常逻辑中每个index仅对应一轮j的遍历。比如数组长度为3时，index=0阶段会触发两次index=1的递归，完全是冗余计算。

修复方案 #

方案1：拆分内外层递归（逻辑更清晰） #

把冒泡的外层轮次和内层遍历拆成两个递归函数，确保每轮index仅对应一次完整的j遍历：

public static void bubbleSort(int[] arr, int index) {
    // 所有元素排序完成，终止递归
    if (index == arr.length - 1) return;
    
    // 完成一轮冒泡，把当前最大元素移到未排序部分末尾
    bubbleInner(arr, 0, index);
    
    // 进入下一轮冒泡
    bubbleSort(arr, index + 1);
}

// 负责单轮内的元素比较交换
private static void bubbleInner(int[] arr, int j, int index) {
    // 遍历到未排序部分的末尾，终止内层递归
    if (j == arr.length - 1 - index) return;
    
    if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
    }
    
    // 继续当前轮的内层遍历
    bubbleInner(arr, j + 1, index);
}

调用方式改为：bubbleSort(arr, 0);

方案2：保留原双参数结构 #

调整终止条件后的逻辑，确保只有当j遍历完当前轮所有元素后，才触发下一轮index的递归：

public static void bubbleSort(int[] arr, int index, int j) {
    // 所有轮次完成，终止递归
    if (index == arr.length - 1) return;
    
    if (j == arr.length - 1 - index) {
        // 当前轮遍历完成，进入下一轮
        bubbleSort(arr, index + 1, 0);
        return;
    }
    
    if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
    }
    
    // 继续当前轮的内层遍历
    bubbleSort(arr, index, j + 1);
}

调用方式仍为bubbleSort(arr, 0, 0);

两个方案都将时间复杂度拉回O(n²)，消除了冗余递归，解决超时问题。

内容的提问来源于stack exchange，提问作者Deepak kumar soni