自定义冒泡排序无显式嵌套循环 时间复杂度是否可达O(n)？

先说结论：这个实现的时间复杂度不是O(n)，最坏情况依然是O(n²)，和传统冒泡排序没有本质区别。

• 不要被「没有显式嵌套循环」的表象迷惑，递归调用本质上就是把传统冒泡的外层循环换成了递归实现，时间复杂度看的是总操作次数，和循环的写法无关。
• 先拆解你的代码逻辑：
  第一个循环是标准的单趟冒泡逻辑，每次会把当前序列里最大的未排序元素挪到对应的末尾位置，这一步的时间开销固定是O(n)。
  第二个循环是有序性校验，只要发现任意一组逆序对，就会触发一次递归调用，然后直接终止当前循环。
• 最坏情况（比如输入完全逆序的数组，例如[5,4,3,2,1]）下，每一趟冒泡只能把一个最大元素放到正确的位置，你需要触发n-1次递归才能完成全量排序，每次递归都要执行一次O(n)的单趟冒泡，总操作次数是n + (n-1) + (n-2) + ... + 1 = n(n-1)/2，量级就是O(n²)。
• 你提到的「递归结束后立刻中断循环」，只是省掉了单次递归里第二个循环后续的无用判断，完全没有减少递归调用的次数，也没有降低每次递归的时间开销，所以不会改变时间复杂度的量级。
• 当然如果输入本身就是完全有序的，你的代码只会跑两次O(n)的循环就结束，这种最好情况的时间复杂度确实是O(n)，这和加了有序判断的优化版冒泡排序效果一致。但我们通常说的算法时间复杂度默认指最坏情况的复杂度，所以不能说这个实现的时间复杂度是O(n)。

你可以自己做个小测试：拿长度为10的完全逆序数组跑你的代码，看print(index)的输出次数，刚好是9次，也就是递归了9次，每次都要遍历接近整个数组，总操作次数接近45次，完全符合O(n²)的计算结果。

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