5. 最优排序¶
如果我们想找出可能使用的比较次数绝对最少的排序算法，会怎样？ 很可能其结果不适用于通用场合。 但请考虑一下与体育锦标赛的类比。 在体育中，两支队伍或两个选手之间的"比较"意味着双方进行一场比赛。 这相当昂贵（至少与计算机中的一点点簿记相比如此），也许值得用相当多的簿记来换取减少需要比赛的场次。 如果我们想弄清楚如何举办一场锦标赛，使它以最少的总比赛场次给出所有队伍的精确排名次序，那该怎么办？ 当然，我们假设每场比赛的结果都是"准确的"，也就是说，我们不仅假设 A 与 B 比赛的结果总是相同（至少在锦标赛的时段内如此），而且假设结果之间的传递性也成立。 在实践中这些假设并不现实，但许多锦标赛组织都在暗中采用这类假设。 像大多数锦标赛组织者一样，我们可以干脆接受这些假设，并想出一个进行比赛的算法，根据我们得到的结果给出某种排名次序。
回忆插入排序：我们把第 \(i\) 个元素放入前 \(i-1\) 个元素组成的有序子线性表中。 如果我们修改标准的插入排序算法，用二分查找来确定第 \(i\) 个元素在有序子线性表中的位置，会怎样？ 这个算法称为 二分插入排序 。 作为一种通用排序算法，它并不实用，因为我们（在平均情况下）需要移动大约 \(i/2\) 个元素，才能为刚插入到有序子线性表中的新元素腾出位置。 但如果只数比较次数，二分插入排序就相当不错。 而且我们可以借用二分插入排序的一些思想，向使用排序所需绝对最少的比较次数的算法靠近。
考虑对五个元素运行二分插入排序时会发生什么。 我们需要做多少次比较？ 我们可用一次比较把第二个元素加到第一个元素之后，然后用两次比较加入第三个元素。 加入第四个元素只需要两次比较，因为我们先与已排序的三个元素中处在中间的那个比较，然后视情况再看第一个或第三个。 但当把第五个元素插入四个元素构成的有序线性表时，在最坏情况下我们需要做三次比较。 注意进行这次插入时具体发生了什么。 我们把第五个元素与第二个元素比较。 如果第五个更大，就必须与第三个比较；如果还是更大，就必须与第四个比较。 一般而言，二分查找什么时候最有效？ 当线性表中有 \(2^i - 1\) 个元素时。 它最没效率的时候，是线性表中有 \(2^i\) 个元素时。 所以，如果可能的话，我们安排插入次序，避免把元素插入规模为 \(2^i\) 的线性表，就能做得稍好一些。
如果有十个元素要排序，我们可以先用五次比较把元素配成五对，再用刚才描述的方法（再用七次比较）对五个获胜者进行排序。 现在需要处理的就是原来的那些失败者。 我们可以把这一过程推广到任意数目的元素：
用 \(\lfloor \frac{n}{2} \rfloor\) 次比较把所有结点两两配对。
递归地对获胜者排序。
把失败者折叠进去。
我们使用二分插入来放置失败者。 然而，我们可以自由选择最佳的插入次序，同时记住这样一个事实：对 \(2^i\) 到 \(2^{i+1} -1\) 个项，二分查找的代价相同。 例如，对规模为 4、5、6 或 7 的线性表，二分查找在最坏情况下需要三次比较。 所以我们选择插入次序以优化二分查找，这意味着选择一种次序，避免使子线性表的规模增大到跨越 \(2^{i+1}\) 边界而需要额外比较。 这种排序称为 归并插入排序 ，也称为 Ford and Johnson 排序 。
归并插入排序在最小化比较次数方面相当不错，但它是最优的吗？ 我们从 排序下界证明 知道，任何排序算法都不可能快于 \(\Omega(n \log n)\) 。 确切地说，排序的 信息论下界 可以证明为 \(\lceil \log n!\rceil\) 。 也就是说，我们可以证明精确的 \(\lceil \log n!\rceil\) 次比较的下界。 对所有不超过 \(n = 12\) 的值，归并插入排序给出的比较次数等于这个信息论下界。 在 \(n = 12\) 时，归并插入排序需要 30 次比较，而信息论下界只有 29 次比较。 不过，对于这么少的元素数量，可以对比较的每一种可能的排列进行穷举研究。 结果表明，当 \(n=12\) 时，事实上不存在任何比较排列能使下界低于 30 次比较。 因此，在这种情况下信息论下界是过低估计，因为 30 确实是能做到的最佳。
把 \(n\) 个元素的最优最坏代价记为 \(S(n)\) 。 我们知道 \(S(n+1) \leq S(n) + \lceil \log (n+1)\rceil\) ，因为我们可以对 \(n\) 个元素先排序，再对最后一个元素用二分插入。 对所有 \(n\) 和 \(m\) ， \(S(n+m) \leq S(n) + S(m) + M(m, n)\) ，其中 \(M(m, n)\) 是归并两个有序线性表的最佳时间。 对 \(n = 47\) ，结果证明我们可以做得更好：把线性表分成 5 和 42 两段，然后进行归并。 因此，归并插入排序并非完全最优。 但它已经极好，对数目不大的元素几乎是最优的。 .. odsascript:: AV/Bounds/binaryinsertsortCON.js .. odsascript:: AV/Bounds/mergeinsertsortCON.js
