为什么插入排序的最佳情况是O（n）而不是O（n ^ 2）？

Question

我很难理解为什么在o（n）中插入的最佳情况是排序？

     for (int i = 0; i < size; i++) {

                for (int j = i; j > 0; j--) {
                    int k = j-1;
                        if( a[j] < a[k]){
                            int temp = a[j];
                            a[j] = a[k];
                            a[k] = temp;
                        }

                }
     }

让我们考虑一个示例初始数组[1,2,3,4,5] size = 5，第一个循环将从i = 0变为size-1，第二个循环将从i变为1，但是假设，内部for循环也从0到大小-1，换句话说，内层for循环也执行（n-1）次，类似于外层for循环。我同意不会有交换，但是会有比较值，它与未排序的数组完全相等吗？那么n-1（外循环）* n-1（内循环）= n ^ 2--n + 1 = O（n ^ 2）
谁能解释我哪里错了？

Answer 1

起初，这似乎不是用于插入排序的适当代码。似乎您在以相反的方式使用冒泡排序代码。
在插入排序代码中，您不会用所有落在它前面的大元素来替换一个小元素，而是只浏览位于该元素之前或之后的所有大元素，不再是大元素，那么我们将小元素放在该位置，然后移动/移动所有其他后续元素。

作为O（n）时间的一部分：
让我们考虑五个已排序元素的数组-arr [11,13,15,17,19]。我们从第一个位置元素移动到最后一个位置。
步骤1：以要素11为例，因为它是第一个要素，所以我们保持原样。
步骤2：采用元素13，寻找位于其之前的元素（即元素11），因为13> 11，因此不再需要查看元素11之前的元素。
步骤3：采用元素15，寻找以下元素：落在它之前（即元素13），因为15> 13，因此不再需要查看落在它之前的元素（即元素15）。
步骤4：取元素17，寻找落在它之前的元素（即元素15），如17> 15，因此不再需要查看15之前的元素。
步骤5：以元素19为例，查找位于其之前的元素（即元素17），如19> 17，因此不再需要查看位于17之前的元素。

正如我们看到的，对于五个已经排序的元素，我们只需要5个比较，因此对于“ n”个排序的元素，我们只需要O（n）比较。

我希望以上示例可以澄清您的疑问。

Answer 2

您的代码始终以 O(n^2) 运行。当您找到元素应该在的位置时，您必须中断内部 for 循环。