c++ - 这种冒泡排序的递归实现是否效率低下？如果可能的话如何改进？

Question

昨天我遇到了冒泡排序的递归实现，乍一看很优雅:

template <class T> void bubblesort_recursive(T data[], const int n){
    if(n==1) return;
    else{
        bubblesort_recursive(data+1, n-1);
        if(data[1]<data[0]) swap(data[1],data[0]);
        bubblesort_recursive(data+1, n-1);
    }
}

但是，我很快意识到它调用了两次递归情况，其时间复杂度的时间递归关系似乎遵循 T(n)=2T(n-1)+c，这导致了指数时间复杂度。然而，冒泡排序通常会导致 n^2 时间复杂度。我的分析是否有问题，或者这只是冒泡排序的低效实现？如果是后者，如何改进？

Answer 1

which leads to exponential time complexity.

正确。

However, bubble sort usually leads to n^2 time complexity.

正确。

how could it be improved?

如果您正在寻找复杂度为 O(𝑛²) 的冒泡排序的递归实现，那么我们需要区分两个过程:

1. 一扫冒泡
2. 对数组的较短部分重复此操作

两者都可以以递归方式实现，但它们将是不同的递归:

template <class T> void bubble_recursive(T data[], const int n) {
    if (n == 1) return;
    if (data[1] < data[0]) swap(data[1], data[0]);
    bubble_recursive(data + 1, n - 1);
}

template <class T> void bubblesort_recursive(T data[], const int n) {
    if (n == 1) return;
    bubble_recursive(data, n);
    bubblesort_recursive(data, n-1);
}

您还可以添加某些冒泡排序实现所具有的提前退出功能:当冒泡的单次扫描显示无需执行交换时，我们就知道数组已排序，并且可以停止在较短的部分上进行更多迭代:

template <class T> bool bubble_recursive(T data[], const int n) {
    if (n == 1) return false;
    bool must_swap = data[1] < data[0]; 
    if (must_swap) swap(data[1], data[0]);
    return bubble_recursive(data + 1, n - 1) || must_swap;
}

template <class T> void bubblesort_recursive(T data[], const int n) {
    if (bubble_recursive(data, n))
        bubblesort_recursive(data, n - 1);
}