从信息论的角度分析堆排序和快速排序的性能

正文

请到「今天看啥」查看全文

如果我们再深入一步，计算出乘以 N log N 的因子，或者换句话说，对数的底数，那将会更有趣。让我揭示最终结果，然后证明它。随机化 QUICKSORT 的平均成本是 N log_e 1/2N 。这是以 e 的平方根为底的对数，即以 1.649 为底的对数。

这个预期成本比理想成本 T ≈ N log2 N 高出 1/log21.649 ≈ 1.39 的因子。如果我们真的关心比较次数，我们应该寻找比快速排序更好的算法！

这里还有更多... 想象一下最后几次带中枢（pivot）的数字比较，你就会发现 QUICKSORT 的概率是不平衡的。如果前面的 100 次比较中，一边分出了 70 次，另一边分出了 30 次，那么可以很好地预测，下一次与中枢（pivot）进行比较时，第一种情况的概率为 0.7 ，另一种情况的概率为 0.3 。

回到 HEAPSORT

堆排序（HEAPSORT）的比较计数效率很低，因为它会把元素从堆的底部拉到顶部，让它们向下流动，与较大的元素交换位置。我一直觉得这很奇怪，把一个很可能很小的元素放在一个很可能很大的元素上面，然后看看会发生什么。为什么 HEAPSORT 要这么做？难道就没有人想出一个优雅的方法，把两个子堆的领导者之一提升到堆的顶端吗？

这样如何？

修改后的 HEAPSORT（肯定有人已经想到了这一点）

1. 将所有元素放入有效的最大堆中

2. 删除堆顶，创建一个空缺 "V"

3. 比较 V 正下方的两个子堆首领，将最大的那个提升到空缺中。递归重复第 3 步，重新定义 V 为新的空缺，直到堆的底部。

   （这就像 HEAPSORT 的筛选操作一样，只不过我们有效地将一个已知比其他所有元素都小的元素提升到了堆的顶端；这个最小的元素可以自动向下流动，而不需要与任何元素进行比较）。

4. 转到步骤 2

   这种方法的缺点是：它没有 HEAPSORT 的漂亮的就地排序特性。但我们可以在最后引入一个额外的交换，将“最小”元素与堆底部的另一个元素（即在堆排序中会被移除的元素）交换，并从该元素向上运行另一个筛分递归，从而再次获得这种特性。

我们称这种算法为 "快速堆排序"（Fast HEAPSORT）。它不是一种就地算法，但就像 HEAPSORT 一样，它从堆的顶部一次提取一个排序项。

FAST HEAPSORT 的性能

我评估了 Fast HEAPSORT 在随机排列上的性能。衡量性能的唯一依据是所需的二分比较次数。（Fast HEAPSORT 确实需要额外的 bookkeeping，因此 CPU 的比较结果会有所不同。）

横轴：要排序的项目数 N 。

纵轴：二分比较次数。理论曲线显示了随机快速排序的渐近结果（ 2 N ln N ）和信息论极限 log_2 N! 近似于 (N log N - N)/log 2 。

我还没有证明 Fast HEAPSORT 在每一步都接近于最大化熵，但似乎可以合理地想象，它确实可能渐近地做到这一点。毕竟，HEAPSORT 的起始堆就像是一个组织，在这个组织中，最高层的人被任命为总裁，而 A 分区和 B 分区中最高层的人被任命为副总裁；类似的组织一直持续到最低层。总裁出身于其中的一个部门，他是通过连续罢免上司而得到这份工作的。

现在，如果老板离职需要被组织中最优秀的人替代，我们显然需要比较两位副总裁；问题是，我们是否期望这将是一场势均力敌的竞争？在没有先验信息的情况下，我们没有充分的理由押注任何一位副总裁。情况中只有两种不对称性：首先，即将退休的总裁可能起初是两个部门之一的成员；其次，这两个部门的总人数可能不等。副总裁"A"可能是比"副总裁"B"稍多的人中的佼佼者；一个大村子的最优秀者更有可能击败一个小村子的最优秀者。标准的建堆方式可能会产生相当不平衡的二叉树。例如，在一个有23人的组织中，A 部门将包含 (8+4+2+1)=15 人，B 部门只有 (4+2+1)=7 人。

请到「今天看啥」查看全文