八个重量不相等的小球,每次只能放两个球到天平上,现如何只用16次将这八个球重量排序?

16次是可行的,因为8个球最多有8!中排序。然而测量16次,最多产生2^16种分支。8!< 2^16,故理论上可行。但是究竟要如何去称?

我的回答

很有意思的一个问题,通过16次比较确实是有解的,《计算机程序设计艺术》(俗称TAOCP)里面提到了一种叫做”合并插入排序”的方法:

  1. 首先将8个小球划分成4对,通过 4 次比较我们可以得到 $b_1 \leq a_1, b_2 \leq a_2, b_3 \leq a_3, b_4 \leq a_4$;
  2. 对 $a_1$, $a_2$, $a_3$, $a_4$ 排序,通过 5 次比较(这里应该没有问题,用归并排序就可以),假设最后我们得到 $a_1 \leq a_2 \leq a_3 \leq a_4$,此时集合 $\left\{ b_1,a_1,a_2,a_3,a_4 \right\}$ 的所有元素顺序确定;
  3. 现在考虑插入 $b_3$ (对的你没看错,不是 $b_2$ ),因为 $b_3 \leq a_3$, 所以只需二分查找它在集合 $\left\{ b_1,a_1,a_2 \right\}$ 中的位置然后插入,需要 2 次比较,此时集合 $\left\{ b_1,a_1,a_2,b_3,a_3,a_4 \right\}$ 的所有元素顺序确定;
  4. 这时候再考虑插入 $b_2$, 因为 $b_2 \leq a_2$, 因此至多需要在集合 $\left\{ b_1,a_1,b_3 \right\}$ 中二分查找然后插入,需要 2 次比较,此时集合 $\left\{ b_1,a_1,b_2,a_2,b_3,a_3,a_4 \right\}$ 的所有元素顺序确定;
  5. 最后插入 $b_4$, 此时需要在集合 $\left\{ b_1,a_1,b_2,a_2,b_3,a_3 \right\}$ 中二分查找它的插入位置然后插入,需要 3 次比较,此时集合 $\left\{ b_1,a_1,b_2,a_2,b_3,a_3,b_4,a_4 \right\}$ 顺序确定,排序完成!

统计一下比较次数 4 + 5 + 2 + 2 + 3 = 16,不多不少!

最后解释一下最违反常理的一点吧,为什么要先插入 $b_3$ 而不是 $b_2$, 这也是”合并插入排序”的精髓所在,总结起来一句话:

在 $x$ 个有序元素中 $(2^{n-1} \leq x < 2^n)$ 二分查找插入的位置,都只需要 $n$ 次比较。

“合并插入排序”本质上就是最大限度地利用好这个性质以减少比较次数。