这种递归实现的冒泡排序是否低效？如何对其进行优化？

问题分析结论 #

你的分析完全正确，没有错误。该实现的时间复杂度递推式确实为T(n) = 2T(n-1) + c，对应O(2ⁿ)的指数级时间复杂度，远高于常规冒泡排序的O(n²)。

这个版本属于设计严重失误的低效冒泡排序实现：它虽然能输出正确的排序结果，但逻辑存在完全没必要的冗余。第一次递归已经对data+1起始的n-1个元素完成排序，仅交换data[0]和data[1]不足以把data[0]放到整个区间的正确位置，因此代码又补充了第二次完全重复的递归调用补全逻辑，最终也导致了指数级的时间开销。

优化方案 #

优化核心是去掉冗余的递归调用，回归冒泡排序的本质逻辑：每一轮遍历把当前区间的最值移动到端点，再递归处理剩下的子区间即可，仅需要单次递归调用。

基础优化版本（和迭代版冒泡性能一致）

template <class T> void bubblesort_recursive(T data[], const int n){
    if(n == 1) return;
    // 单次遍历将当前区间最大的元素交换到末尾
    for(int i = 0; i < n - 1; i++){
        if(data[i] > data[i+1]) swap(data[i], data[i+1]);
    }
    // 仅需一次递归，处理前n-1个元素即可
    bubblesort_recursive(data, n - 1);
}

该版本的时间复杂度递推式为T(n) = T(n-1) + O(n)，平均、最坏时间复杂度为O(n²)，和常规迭代版冒泡排序完全一致。

进阶优化版本（加入提前终止逻辑）

常规冒泡排序可以加入交换标记做提前终止：如果某一轮遍历没有发生任何交换，说明整个数组已经完全有序，可以直接终止排序，不需要继续递归。优化后最好场景（输入数组已有序）下时间复杂度可以降到O(n)：

template <class T> void bubblesort_recursive(T data[], const int n){
    if(n == 1) return;
    bool is_sorted = true;
    for(int i = 0; i < n - 1; i++){
        if(data[i] > data[i+1]){
            swap(data[i], data[i+1]);
            is_sorted = false;
        }
    }
    // 本轮无交换，数组已有序，直接终止递归
    if(is_sorted) return;
    bubblesort_recursive(data, n - 1);
}

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