我的冒泡排序实现与标准优化版有何差异？时间复杂度均为O(n²)吗？

我的实现代码 #

def bubbleSortArray(arr):
    arr_len = len(arr)
     
    for i in range(0, arr_len):
        for j in range(i+1, arr_len):
            if arr[i] > arr[j]:
                tmp = arr[i]
                arr[i] = arr[j]
                arr[j] = tmp
 
    print(arr)

标准优化版冒泡排序代码 #

static void BubbleSortBasicOptimised(int[] dataSet)
{
    // loop n-1 times.
    for (int i = dataSet.Length - 1; i > 0 ; --i)
    {
        // keep track of whether items were swapped
        // for this iteration
        bool swapped = false;

        // for each loop, iterate through the first i
        // items (ie. the unsorted ones)
        for (int j = 0; j < i; ++j)
        {
            // if adjacent items need to be swapped
            if (dataSet[j] > dataSet[j + 1])
            {
                // swap them
                Swap(dataSet, j, j + 1);

                // indicate that we found a swap
                swapped = true;
            }
        }

        // if nothing was swapped, then we should
        // already have everything in order
        if (!swapped)
        {
            break;
        }
    }
}

你的实现相比标准优化版的问题 #

1. 逻辑偏离冒泡排序核心定义：冒泡排序的核心是相邻元素两两比较交换，通过多轮遍历逐步将较大元素“冒泡”到数组末尾。而你的实现是拿第i个元素与后续所有元素逐一比较交换，本质更接近选择排序逻辑，但比选择排序的交换次数更多（选择排序仅在找到最小值后交换一次，你每遇到更小元素就交换），效率更低。

2. 缺少提前终止优化：标准优化版通过swapped标记检测数组有序性——如果某一轮遍历无交换发生，说明数组已完全有序，可直接终止循环。你的实现无论数组是否有序，都会执行全部n轮循环，在数组接近有序时会浪费大量计算资源。

3. 未利用已排序区间特性：标准冒泡排序每轮遍历后，末尾的i个元素已处于有序状态，下一轮只需遍历前dataSet.Length - i个元素。你的实现每轮都要遍历i之后的所有元素，没有规避已排序区间的重复比较。

时间复杂度对比 #

• 最坏时间复杂度：二者均为O(n²)。当数组完全逆序时，两种实现都需要执行约n(n-1)/2次比较操作。
• 最好时间复杂度：标准优化版为O(n)（数组已有序时，仅需一轮遍历即可终止）；你的实现为O(n²)，因为无论数组是否有序，都会执行全部嵌套循环。

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