鸡尾酒摇排序时间复杂度疑问：最好情况是否与最坏情况同为O(n²)？

核心结论 #

你提到的情况是成立的：给定的这个CocktailShakerSort实现，其最好情况时间复杂度与最坏情况一致，均为O(n²)。下面分三种情况详细分析：

1. 最好情况（数组已完全有序） #

给定的实现没有添加「本轮是否发生交换」的判断逻辑，即便数组已经有序，算法仍会执行完整的循环流程：

• 初始l=1，r=n，进入while l < r循环
• 第一次正向遍历：从i=l到r-1，所有元素都满足A[i] <= A[i+1]，无交换；随后r=r-1
• 第一次反向遍历：从i=r-1 downto l，同样无交换；随后l=l+1
• 上述过程会持续进行，直到l >= r才终止循环。整个过程的总遍历次数为(n-1)+(n-2)+(n-3)+...+1，属于O(n²)级别的时间复杂度。

2. 最坏情况（数组完全逆序） #

当数组完全逆序时，每一轮正向和反向遍历都会触发大量交换，但遍历的次数和最好情况完全一致：

• 每一轮都会对当前未排序的区间进行完整的双向扫描，总操作次数同样是(n-1)+(n-2)+...+1，时间复杂度为O(n²)。

3. 平均情况 #

鸡尾酒排序是冒泡排序的双向变种，其平均时间复杂度与冒泡排序一致，为O(n²)。因为大部分情况下，数组的无序状态需要多轮双向扫描才能完成排序，总操作次数依然是二次方级别。

优化提示 #

如果要将最好情况时间复杂度优化到O(n)，只需在每一轮遍历后添加一个交换标记：若本轮正向+反向遍历都没有发生交换，说明数组已经有序，直接跳出while循环即可。

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