Sort

2.1.2

2018-6-30
Sort

2.1.2 # 解答 # 最多会被交换 n 次，只要将一个有序数列循环右移一位就可以构造这样的情况。 例如： 平均每个元素被交换了 N/N=1 次。（总共 N 个元素，总共发生了 N 次交换）。

2.1.3

2018-6-30
Sort

2.1.3 # 解答 # 你需要一个逆序的数组。 例如： 9 8 7 6 5 4 3 2 1 i=0 条件满足 8 次，1 和 9 交换，1 8 7 6 5 4 3 2 9。 i=1 条件满足 6 次，2 和 8 交换，1 2 7 6 5 4 3 8 9。 i=2 条件满足 4 次，3 和 7 交换，1 2 3 6 5 4 7 8 9。 i=3 条件满足 2 次，4 和 6 交换。1 2 3 4 5 6 7 8 9。 ...

2.1.5

2018-6-30
Sort

2.1.5 # 解答 # 条件是： j > 0 && less(a[j], a[j - 1]) 第一个条件属于循环计数用的条件，与数组元素无关； 第二个条件当 a[j] 和 a[j - 1] 是一组逆序对时满足，因此这个条件总是为假 = 数组没有逆序对 = 数组有序。 因此只要输入已经排好序的数组即可。 逆序对：指序列中顺序相反的两个数，例如 1 2 3 4 5 7 6 8 9 中的 7 6。 另请参阅 # 逆序对-维基百科

2.1.6

2018-6-30
Sort

2.1.6 # 解答 # 插入排序更快。 选择排序无论如何都需要 $n + (n-1) + (n-2) + … + 1 = \frac{n^2}{2}$ 次比较。 插入排序在这种情况下只需要 n 次比较。（所有主键相同 = 数组已排序）

2.1.7

2018-6-30
Sort

2.1.7 # 解答 # 假设比较的开销小于等于交换的开销，此时选择排序更快，具体比较见下表。 排序方法 比较次数 交换次数 插入排序 ~N^2/2 ~N^2/2 选择排序 ~N^2/2 N

2.1.8

2018-6-30
Sort

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。 ...

2.1.10

2018-6-30
Sort

2.1.10 # 解答 # 对于部分有序的数组，插入排序比选择排序快。 这个结论可以在中文版 P158， 英文版 P252 找到。