为什么冒泡排序和插入排序的性能相同，即O(n^2)

Question

我执行了以下代码来检查冒泡排序和插入排序所需的迭代和交换次数。尽管(参见下面的代码)插入排序的迭代次数和交换次数都是冒泡排序的一半，但是为什么两者都有相同的大O复杂度

static void bubbleSortExample()
    {
        int iterationCount=0;
        int swaps=0;
        int [] arr={2,6,1,4,8,7,10,3};
        int temp=0;
        for(int i=0; i< arr.length; i++)
        {
            iterationCount=iterationCount+1;
            for(int j=0; j<arr.length-1; j++)
            {
                iterationCount=iterationCount+1;
                if(arr[j]> arr[j+1])
                {
                    swaps= swaps+1;
                    temp= arr[j+1];
                    arr[j+1]= arr[j];
                    arr[j]= temp;
                }
            }
        }
        System.out.println("Bubble Sort----Iteration count are : " + iterationCount + " and swaps are : " + swaps);
    }
    //Bubble Sort Example Ends


    //Insertion Sort Example Starts
    static void insertionSortExample()
    {
        int iterationCount=0;
        int swaps=0;
        int [] arr={2,6,1,4,8,7,10,3};

        for(int i=1;i< arr.length;i++)
        {
            iterationCount=iterationCount+1;
            int key=arr[i];// this is the number that needs to be inserted in its correct position
            for(int j=i-1; j >= 0;  j--)
            {
                iterationCount=iterationCount+1;
                if(key < arr[j])
                {
                    swaps= swaps+1;
                    int t= arr[j];
                    arr[j]=key;
                    arr[j+1]=t;

                }
            }
        }
        System.out.println("Insertion Sort----Iteration count are : " + iterationCount + " and swaps are : " + swaps);
    }

输出

Bubble Sort----Iteration count are : 64 and swaps are : 9
Insertion Sort----Iteration count are : 35 and swaps are : 9

Answer 1

请记住，该表示法仅表达了算法在n增长时的行为。线性因子总是从中删除。所以它并没有说明一个算法是否很快，它只是说明了当你增加n时，它将花费更多的时间来完成。

Answer 2

在第i次迭代的冒泡排序中，你有n-i-1次内部迭代(n^2)/2，但是在插入排序中，你在第i步有最大的i次迭代，但平均是i/2，因为你可以在找到当前元素的正确位置后提前停止内循环。

所以你有(sum from 0 to n) /2，它是(n^2) /4个总数；

这就是插入排序比冒泡排序快的原因。