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} $$ ...

2.1.10

2018-6-30
Sort

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