c++ - 为什么插入排序的最佳情况是大O复杂度O(n)？

以下是我的插入排序代码:

void InsertionSort(vector<int> & ioList)
{
  int n = ioList.size();
  for (int i = 1 ; i < n ; ++i)
  {
    for (int j = 0 ; j <= i ; ++j)
    {
      //Shift elements if needed(insert at correct loc)
      if (ioList[j] > ioList[i])
      {
        int temp = ioList[j];
        ioList[j] = ioList[i];
        ioList[i] = temp;
      }
    }
  }
}

该算法的平均复杂度为O(n ^ 2)。

根据我对大O表示法的理解，这是因为我们在这种情况下运行了两个循环(外循环1个n-1次，内循环1,2，... n-1 = n(n-1)/2次，因此结果，该算法的无症状复杂度为O(n ^ 2)。

现在，我已经读到最好的情况是输入数组已经排序的情况。
在这种情况下，算法的最大O复杂度为O(n)。但是我无法理解这是如何实现的，因为在两种情况下(平均情况和最佳情况)，我们都必须将循环运行相同的次数，并且必须对元素进行比较。唯一可以避免的是元素的移动。

那么复杂度计算是否也包含此交换操作的一部分？

最佳答案

是的，这是因为您的实现不正确。内部循环应该从i-1倒数到0，并且一旦发现元素ioList[j]已经小于ioList[i]，它就应该终止。

由于该终止准则，该算法在最佳情况下的执行时间为O(n):

如果输入列表已经排序，则对于任何i，内循环将立即终止，即最终执行的计算步数与外循环的执行次数成正比，即O(n)。