3

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

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)。但我不明白这是怎么可能的，因为在这两种情况下（平均情况和最佳情况）我们都必须运行相同次数的循环并且必须比较元素。唯一避免的是元素的移动。

那么复杂度计算是否也涉及到这个交换操作的一个组件呢？

4

2 回答 2

8

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

正是由于该终止标准，算法在最佳情况下在 O(n) 时间内执行：

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

于 2012-11-05T09:34:15.360 回答
7

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

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

Your sort is also worse than insertion sort on average, since you always do i+1 operations for each iteration of the outer loop -- some of those ops are just a comparison, and some are a comparison followed by a swap. An insertion sort only needs to do on average half that, since for random/average input, the correct insertion point is half way through the initial sorted segment. It's also possible to avoid swaps, so that each operation is a comparison plus a copy.

于 2012-11-05T09:35:21.193 回答