为什么插入排序的最好情况下，时间复杂度为O(n)？

Question

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

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)。但我无法理解这是如何可能的，因为在两种情况下（平均和最佳情况）我们都必须运行相同数量的循环并比较元素。唯一避免的是元素的移动。

因此，复杂性计算是否也涉及这个交换操作的组成部分？

- Arun

Answer 1

是的，这是因为您的实现有误。内部循环应该从 i-1 开始向下计数到 0，并且它应该在找到已经小于 ioList[i] 的元素 ioList[j] 后立即终止。

正是由于这个终止条件，使得算法在最好情况下以 O(n) 的时间复杂度运行：

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

- jogojapan

---

我认为...在内部循环中，为了找到 ioList[i] 正确的位置，我们必须比较从 ioList[o] 到 ioList[j]（其中 j <= i-1）的所有元素...我不明白，在不比较第i个元素之前的所有元素的情况下，如何找到第i个元素的正确位置？ - Arun

这是因为在处理第i个元素时，你已经处理了外层循环中的i-1，i-2等元素。你需要意识到，在最初的一轮中（i==0），内层循环根本没有工作要做，在第二轮中它处理一个元素，在第三轮中它处理两个元素，但其中一个元素已经在上一轮中被处理过了，以此类推。因此，在外层循环的任何一步中，向后进入内层循环意味着进入一个已经处理过并保证排序的区域。 - jogojapan

还不清楚吗？考虑这个未排序的列表3、55、7、1、2、60... 在第一次遍历中，我考虑55，因为55比3大，所以我什么也不做...下一次遍历我考虑7...7比55小，所以我交换它... 下一次遍历我考虑1...1比它之前的所有元素都小...(只有在与所有先前的元素进行比较后才会知道)...所以我将其交换到第0个元素...以此类推...因此，在每次迭代中，我们必须比较特定元素之前的所有元素...至少我是这样认为的... - Arun

是的，没错。请记住，O(n)的限制仅适用于最佳情况，即输入列表已经排序的情况。您示例中的输入列表未排序。 - jogojapan

我认为你说的是正确的。要找到位置，我应该在找到比当前元素大的元素时立即跳出循环。我的内部循环也管理着移位...这就是为什么它必须按照目前的方式迭代的原因。 - Arun

Answer 2

你的“插入排序”实现很差。

在你的内部循环中，你不应该扫描所有大于ioList[i]的元素并交换到i-1。相反，你应该从i-1向后扫描，直到找到正确的位置来插入新元素（也就是说，直到找到一个小于或等于新元素的元素），然后将其插入那里。如果输入已经排序，则总是立即找到正确的插入点，因此内部循环不会执行i-1次，只会执行一次。

你的排序方法在平均情况下也比插入排序要差，因为每次外部循环迭代你都会进行i+1次操作--其中一些操作只是比较，而另一些操作是比较后跟着交换。插入排序只需要做平均一半的操作，因为对于随机/平均输入，正确的插入点位于初始排序段的一半。还可以避免交换，这样每个操作只是一个比较加上一个复制。

- Steve Jessop