java中的递归冒泡排序TLE

Question

我已经编写了代码来进行冒泡排序递归。但我超出了时间限制。谁能帮我弄清楚为什么我超出了时间限制。

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);

我不明白为什么我会超出时间限制

Answer 1

每个函数执行上下文不应该有两个递归调用，而应该只有一个。否则，递归调用的次数是指数 O(2^𝑛)，而您只需要 O(n²) 次

bubbleSort

的调用。

使用

if

条件来决定您需要两个递归调用中的哪一个：

    if (j < arr.length - 2) {
        bubbleSort(arr,index,j+1);
    } else {
        bubbleSort(arr,index+1,0);
    }

你甚至可以让条件更严格一点，因为在冒泡排序的每个阶段，数组末尾的已排序分区都会增长：

    if (j < arr.length - 2 - index) {

您还可以删除

j

上的停止条件。