2.1.8 #

解答 #

平方级别。

如果数组中元素各不相同，那么这个结论很容易证明（一般的插入排序）。

接下来我们证明有重复元素的情况下，这个结论仍然成立：

首先对于插入排序过程中的某一时刻，我们有下图这样的一般情况：

$$ \underbrace{11…1}{a} \ \underbrace{22…2}{b} \ \underbrace{33…3}{c} \ \underbrace{13121123}{unsorted} $$

其中，1，2，3 分别代表三种不同的取值及其先后顺序。

假设这是第 i 次插入前，如果第 i 次插入的是 1，我们需要交换 b+c 次，插入 2 则需要交换 c 次，插入 3 则不需要交换。

根据题意，这是一个随机数组，我们假设其为均匀分布，那么三种取值的出现几率相等。

第 i 次插入所需要的平均交换次数即为：

$$ \frac{b+c+c}{3}=\frac{b+2c}{3} $$

第 i 次插入后，b + 2c 视插入的元素不同会出现不同的变化：

如果插入的是 1，那么 b+2c 的值不会变化。

如果插入的是 2，那么 b+2c 的值增加 1。

如果插入的是 3，那么 b+2c 的值增加 2。

同样由于三种取值的概率相等，我们得出第 i + 1 次插入平均需要交换的次数为：

$$ \frac{b+2c+\frac{0+1+2}{3}}{3}=\frac{b+2c+1}{3} $$

也就是说，平均每次插入都会使下一次插入的交换次数增加 1/3。

令 i=0，此时交换次数为 0，i+1 的交换次数即为 1/3，i+2 的交换次数即为 2/3，以此类推。

我们可以得出总交换次数：

$$ \frac{1+2+3+4+…+N}{3}=\frac{N(N-1)}{6} $$

由此证明，在元素取值为 3 种且出现概率相等时，插入排序的交换开销时平方级别的。

比较开销和交换开销类似，一般情况下比较次数=交换次数+1，除非插入的数是已知最小的数（移动到最左侧），这个时候比较次数和交换次数相等。

因此比较次数=交换次数+N-e，e 是一个不大于 N 的数，代表插入的数是已知最小的数这种情况发生的次数。

根据上式可以得出结论：在元素取值为 3 种且出现概率相等时，插入排序的比较开销也是平方级别的。

综合两个结论即可证明插入排序的开销在题目描述的情况下是平方级别的。

证明完毕。