为什么平均情况下插入排序为Θ（n ^ 2）？

为了回答这个问题，我们首先确定如何评估插入排序的运行时间。如果我们可以为运行时找到一个很好的数学表达式，则可以 *** 纵该表达式以确定平均运行时间。

我们需要获得的主要观察结果是插入排序的运行时间与输入数组中的反转次数密切相关。数组中的反转是一对元素A
[i]和A [j]的相对顺序错误-即，i <j，但A [j] <A [i]。例如，在此数组中：

0 1 3 2 4 5

有一个反转：应该切换3和2。在此数组中：

4 1 0 3 2

有6个反演：

• 4和1
• 4和0
• 4和3
• 4和2
• 1和0
• 3和2

反转的一个重要属性是排序后的数组中没有反转，因为每个元素都应小于其后的所有元素，并大于其后的所有元素。

之所以如此重要，是因为在插入排序中完成的工作量与原始数组中的反转数量之间存在直接的联系。要看到这一点，让我们回顾一些用于插入排序的快速伪代码：

• 对于i = 2 .. n ：（假设1索引）
  • 设置j = i-1。
  • 而A [j]> A [j + 1]：
  • 交换A [j]和A [j + 1]。
  • 设置j = j-1。

通常，当确定像这样的函数完成的工作总量时，我们可以确定内部循环完成的最大工作量，然后将其乘以外部循环的迭代次数。这将给出一个上限，但不一定是一个严格的界限。一种更好的方法来说明完成的全部工作是要认识到有两种不同的工作来源：

• 外循环，计数为2、3，…，n和
• 内部循环，执行交换。

该外循环总是使Θ（n）起作用。但是，内部循环的工作量与整个算法运行期间进行的交换总数成正比。要查看该循环将执行多少工作，我们需要确定在算法的所有迭代中进行了多少次总交换。

这就是反转发生的地方。请注意，在运行插入排序时，它总是交换数组中的相邻元素，并且仅在两个元素形成反转时才交换它们。那么，执行交换之后，数组中的总反转数会怎样？好，以图形方式，我们有：

 [---- X ----] A[j] A[j+1] [---- Y ----]

在此，X是阵列中位于交换对之前的部分，Y是阵列中位于交换对之后的部分。

假设我们交换A [j]和A [j + 1]。反转次数会怎样？好吧，让我们考虑一下两个元素之间的任意转换。有6种可能性：

• 两个元素都在X中，或者两个元素都在Y中，或者一个元素在X中，一个元素在Y中。然后反转仍然存在，因为我们没有移动任何这些元素。
• 一个元素在X或Y中，另一个元素在A [j]或A [j + 1]中。然后，反转仍然存在，因为元素的相对顺序没有改变，即使它们的绝对位置可能已经改变。
• 一个元素是A [j]，另一个是A [j + 1]。然后，在交换之后，反转将被删除。

这意味着在执行交换之后，我们仅将反转的数量减少了一个，因为只有相邻对的反转已消失。这是非常重要的，因为以下原因：如果我们从I反转开始，则每个交换将使该数目恰好减少1。一旦没有反转，就不再执行交换。因此，
交换次数等于反转次数 ！

鉴于此，我们可以将插入排序的运行时间准确地表示为Θ（n + I），其中I是原始数组的求逆数。这符合我们的原始运行时范围-
在排序数组中，存在0个反转，并且运行时为Θ（n + 0）=Θ（n），在反向排序数组中，存在n（n-1）/ 2个反演，并且运行时间为Θ（n + n（n-1）/
2）=Θ（n 2）。好漂亮！

因此，现在我们有了一种分析给定特定数组的插入排序运行时的超精确方法。让我们看看如何分析其平均运行时间。为此，我们需要对输入的分布进行假设。由于插入排序是一种基于比较的排序算法，因此输入数组的实际值实际上并不重要。只有它们的相对顺序才真正重要。在下面的内容中，我将假设所有数组元素都是不同的，尽管如果不是这种情况，则分析不会有太大变化。我要指出的是，到达那里后，情况会发生变化。

为了解决这个问题，我们将引入一堆形式为X ij的指标变量，其中X ij是一个随机变量，如果A [i]和A
[j]构成一个倒数，则为1，否则为0。这些变量将有n（n-1）/ 2个，每对不同的元素对一个。请注意，这些变量说明了数组中每个可能的反转。

给定这些X，我们可以定义一个新的随机变量I，该变量等于数组中反转的总数。这将由X的总和得出：

I =ΣX ij

我们对E [I]（数组中期望的反转数）感兴趣。使用期望的线性，这是

E [I] = E [ΣX ij ] =ΣE [X ij ]

因此，现在，如果我们可以获得E [X ij ] 的值，则可以确定预期的反转次数，并因此确定预期的运行时间！

幸运的是，由于所有X ij都是二进制指示符变量，因此

E [X ij ] = Pr [X ij = 1] = Pr [A [i]和A [j]是反演]

那么，给定一个无重复的随机输入数组，A [i]和A [j]是反演的概率是多少？好吧，一半时间A [i]小于A [j]，另一半时间A [i]大于A
[j]。（如果允许重复，则有一个偷偷摸摸的额外术语来处理重复，但我们暂时将其忽略）。因此，A [i]和A [j]之间存在求逆的概率为1 /2。因此：

E [I] =ΣE[X ij ] =Σ（1/2）

由于总和中有n（n-1）/ 2个项，因此得出

E [I] = n（n-1）/ 4 =Θ（n 2）

因此，根据预期，将有Θ（n 2）反演，因此，预期运行时将为Θ（n 2 + n）= Θ（n 2）。这解释了为什么插入排序的平均情况行为是Θ（n
2）。

希望这可以帮助！