数组{2,3,…,n,1}是否属于冒泡排序的最坏情况？

你的冒泡排序实现代码如下：

void bubbleSort(int * arr, int size)
{
    for ( int i = size; i > 1; i-- ) // i is size of Unsorted array
    {
        bool swapped = false;
        for ( int j = 0 ; j <= i-2; j++ )
        {
            if ( arr[j] > arr[j+1] )
            {
                swap(arr+j, arr+j+1);
                swapped = true;
            }
        }
        if ( swapped == false )
        {
            break;
        }
    }
}

针对你的疑问，解答如下：

• 最坏情况的判定依据：
  学术场景下讨论算法的最坏情况，核心依据是渐近复杂度，而非实际运行时间的细微差异。只要输入让算法无法触发提前终止逻辑（也就是你说的每轮至少有一次交换），导致算法执行最高阶的时间复杂度（这里是Θ(n²)），就属于最坏情况输入。

• 两类数组是否都属于最坏情况：
  按照《Data Structures with C (Schaum's Outline Series)》中以比较次数作为关键操作的衡量标准，你构造的{2,3,4,5,1}和完全逆序数组的比较次数完全一致——都是n(n-1)/2次，且都不会触发提前break，因此两者都属于冒泡排序的最坏情况输入。
  实际运行时间的差异来自交换操作的次数：完全逆序数组每次比较都需要交换，而{2,3,4,5,1}仅需交换n-1次，但这种差异属于常数级别的操作开销，不会影响渐近复杂度的判定，也不违背以关键操作次数定义最坏情况的规则。

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