该特殊冒泡排序Java实现的时间复杂度大O表示是什么？

结论 #

该算法的最坏、平均时间复杂度均为 O(n²)，只有最优场景（待排序的下标序列已经完全升序）下时间复杂度为O(n)。通常大O表示默认指最坏时间复杂度，因此答案是O(n²)而非O(n)。

逻辑分析 #

• 这是冒泡排序的特殊变种：仅处理下标从begin开始、步长为2的元素序列（要么全是偶数下标元素，要么全是奇数下标元素），每次仅交换同组内下标差为2的相邻元素。
• 最坏场景下（比如待排序的同组元素完全逆序）：每轮外层while循环最多只能把当前最大的元素往后移动2个位置，假设同组总共有k个元素（k≈n/2），总共需要k轮外层循环才能把所有元素放到正确位置，外层循环次数为O(n)。
• 每轮内层for循环都会遍历所有同组元素，遍历次数为O(n)。
• 两者相乘得到总时间复杂度为O(n) * O(n) = O(n²)。

对应Java代码 #

public static int Sort(int[] b, int begin) {
    boolean swapped = false;
    int count1 = 0;
    int temporary;
    while (swapped == false) {
        swapped = true;
        for (int i = begin; i < b.length - 1; i+=2) {
            if (b[i] > b[i + 2]) {
                temporary = b[i];
                b[i] = b[i + 2];
                b[i + 2] = temporary;
                swapped = false;
                count1++;
            }
        }
    }
    return count1;
}

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