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符号的理解,这是因为在这种情况下我们运行两个循环(外部一个n-1次,内部一个1,2,… n-1 = n(n-1)/ 2次因此由此产生的算法的无症状复杂性为O(n ^ 2).

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

那么复杂性计算也涉及这种交换操作的一个组成部分？