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

其中大部分都是这样说的："两者都需要 NlogN 的平均时间，但 QUICKSORT 的良好表现通常在实践中胜过 HEAPSORT。 "

有些人则更进一步，给出了量化细节：平均而言，HEAPSORT 的比较次数是 QUICKSORT 的两倍，但 HEAPSORT 避免了性能灾难性下降的可能性。

但似乎很少有人会问这样一个问题："为什么 HEAPSORT 要使用两倍的比较次数？ "

人们花费大量精力试图 "两全其美"，制造出混合排序算法，如"内省排序"（introspective sort），它递归应用 QUICKSORT，如果递归深度变大，偶尔会切换到 HEAPSORT。

Paul Hsieh 对 QUICKSORT 和 HEAPSORT 进行了深入比较。他说： " 我怀疑 HEAPSORT 的表现应该会好于其糟糕的名声，我认为这些结果证明了这一点。 " 在他的测试中，最好的编译器产生的 HEAPSORT 在 CPU 总时间上比 QUICKSORT 快约 20%。

CPU 总时间与比较次数不同。在对大约 3000 个对象的列表进行排序时，HEAPSORT 平均使用了 61000 次比较，而 QUICKSORT 平均使用了 22000 次比较。关于比较次数结果和 CPU 时间结果之间对比的解释，请参阅[他的文章]。

文章地址：http://www.azillionmonkeys.com/qed/sort.html

不过，我想解决的问题是，为什么 HEAPSORT 比 QUICKSORT 使用更多的比较。Paul Hsieh 说： " 让我印象深刻的是，我真的不明白为什么 HEAPSORT 比 QUICKSORT 慢。我也没有听说或读到过可信的解释。 "

我认为有一个简单的解释，它基于预期信息内容的概念。为了让这个问题更容易理解，让我们通过一个经典的谜题来侃侃而谈。

称重问题

给你 12 个球，除了一个较重或较轻外，其他重量都相等。同时给你一个双盘天平供你使用。每次使用天平时，你可以把 12 个球中的任意数量放在左边的盘子里，把相同数量的球放在右边的盘子里，然后按下按钮开始称量；每次称量有三种可能的结果：要么重量相等，要么左边的球重一些，要么左边的球轻一些（第三种情况如上图所示）。你的任务是设计一种策略，在尽可能少使用天平的情况下确定哪个是有问题的球，以及它比其他球重还是轻。

很多人都是通过反复试验找到谜底的。（有问题的球可以通过三次称重来确定。）但如果通过反复试验找到最终的解法，就会感觉相当复杂。有一个更好的办法。

为了尽量减少实验次数，我们当然希望最大限度地提高每次实验所获得的平均信息量。

书籍地址：http://www.inference.org.uk/mackay/itila/

我们可以快速解决称重问题，方法是始终选择具有最大熵的测量值；或者用概率术语来说，选择一种测量，使得可能有尽可能多的不同结果，并且它们都具有近似相等的概率。

排序和位（bit）

如果仅使用二进制比较产生的信息进行排序，那么每次比较产生的最大平均信息量为 1 位（bit）。

对 N 个对象进行排序所需的信息量正好是 log_2 N! 比特（假设没有关于对象的先验信息）。

使用斯特林近似法，总信息量为 T = N log_2 N - N log_2 e 。

任何排序算法所需的平均比较次数肯定都不会少于 T ，而且只有当每次比较都有 50:50 的几率进行两种选择时，才会接近 T 。

那么，为什么说：

HEAPSORT 在一般情况下不如 QUICKSORT 快？

当然，这是因为 HEAPSORT 进行比较时，其结果的先验概率并不相等。稍后我们就会知道为什么会这样。

顺便提一下，标准随机 QUICKSORT 也有同样的缺陷。令人恼火的是，所有这些算法研究者都只会说 "随机 QUICKSORT 在任何输入上都以极高的概率使用 O(N log N) 进行比较"，从而丢掉了平均成本中迷人的常数因子。荒谬的 “O” 符号！这是多么愚蠢的伪装，说“我们关心的是大 N 的渐近性能”，就好像这意味着我们不在乎 4N log N 算法和 1N log N 算法之间的差异一样！

如果我们再深入一步，计算出乘以 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 的比较结果会有所不同。）

纵轴：二分比较次数。理论曲线显示了随机快速排序的渐近结果（ 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 人。

为了实现更快的 HEAPSORT，我提出了两个改进方案：

1. 让堆更平衡。破坏优雅的堆规则，即 i 的子堆位于 (2i) 和 (2i+1)，堆从左到右填满。这样做会有什么不同吗？也许不会；也许它就像一个有一些自由选择的哈夫曼算法。

2. 将信息论思想应用于初始堆形成过程。开头的 Heapify 例程是否会进行熵明显小于一位的比较？

回到 QUICKSORT

我们也可以对 QUICKSORT 进行熵处理。QUICKSORT 之所以浪费，是因为它坚持在两种可能结果不相等的情况下进行实验。大约有一半的时间，QUICKSORT 使用的是一个“坏”支点——“坏”的意思是，这个支点超出了四分位之间的范围。而且，一旦明确了这是一个坏支点，与该支点进行的每一次比较所产生的预期信息含量都会大大低于 1 位。

有一种简单的方法可以减少 QUICKSORT 的浪费，那就是对 QUICKSORT 进行“三中值”修改：不是随机选取一个中枢（pivot），而是选取三个候选中枢，并将它们的中值作为中枢。这一修改降低了出现错误中枢的概率。但我们可以做得更好。让我们回到起点，分析 QUICKSORT 产生的信息。

当我们随机选取一个中枢元素，并将另一个随机选取的元素与之比较时，结果的熵显然是一位（bit）。这是一个完美的开端。然而，当我们将另一个元素与中枢元素进行比较时，我们立刻就进行了一个质量不高的比较。如果第一个元素 "较大"，那么第二个元素很可能也是“较大”。事实上，第二个元素“较大”的概率大约是 2/3 。（这是贝叶斯定理的一个不错的示例，我必须记住！对于 N=3 和 N=4 的物体来说， 2/3 是完全准确的；也许对所有的 N 都是这样）。 （1/3,2/3） 的熵为 0.918 bit，所以第一次比较的效率并不差——只是比完美差了 8%。从熵的角度来看，在第二次比较时我们应该比较另外两个元素。不过，让我们继续使用 QUICKSORT。如果前两个元素都被判定为比中枢元素“较大”，那么下一个元素有 3/4 的概率也被判定为“较大”（熵为 0.811 比特）。这种情况将超过一半的时间出现。

表 1 显示了在 5 个元素与中枢元素进行比较后，可能出现的状态，以及如果我们进行下一次比较，QUICKSORT 的熵。有三分之一的概率是 (0,5) 或 (5,0) （这意味着与中枢元素的所有比较都以相同的方式进行）；在这些状态下，下一次比较的熵为 0.59 ，比理想熵差 40% 。

在运行 QUICKSORT 时，我们可以利用这样的计算来做出合理的决策。例如，我们可以让自己选择继续使用当前的中枢，还是通过稍微复杂的方式从已与当前中枢比较过的元素中选取一个新的中枢，然后继续使用新的中枢。"三位中值"的起始过程可以这样描述：我们总是先将两个元素与中枢进行比较，就像标准的快速排序一样。如果我们到达状态 （1,1） ，发生的概率为 1/3 ，那么我们将继续使用当前的中枢元素；如果我们到达状态 （0,2） 或 （2,0） ，我们决定这是一个不好的中枢并丢弃它。我们会通过比较其他两个元素，选择三者中的中值作为新的中枢。这种中枢的转换需要额外的一次比较成本，但预计会产生有益的回报，即每次比较会产生更多的比特（一种说法）或一棵更平衡的树（另一种说法）。

我们可以利用信息论将 "三位中值" 方法建立在客观的基础上，也可以将其推广。

假设我们已经比较了 N 个元素中的 (M-1) 个与一个随机选中的中枢，达到了 (m1,m2) 的状态（即， m1 在左侧， m2 在右侧）。我们现在有一个选择，是继续使用同一个中枢，这在下一次比较中给我们一个预期收益 H_2(p) ，其中 p = (m1+1)/(m1+m2+2) ；还是我们可以投入到一个寻找中值的算法中，找到迄今处理的 M 个元素的中值。（中值可以找到，预期成本与 M 成正比；例如，quickselect 的成本大约是 4M 。）我们可以评估这两种选择的预期收益与成本比。如果我们决定用中枢进行更多的 (N-M) 次比较，预期收益大致是 R = (N-M)H_2(p) 比特。（这不完全正确，需要进行积分以找到准确答案。）如果我们切换到一个新的中枢，然后继续快速排序，在后续的迭代中舍弃在寻找新中枢时生成的信息（这当然是一种浪费——并为我们指出了一种新算法，在这种算法中，我们首先对元素子集进行排序，以便选择多个中枢），成本大致是 (N-M)+4(M-1) 次比较，预期收益大致是 R' = (N-M)H_2(p') 比特，其中 p' 是新中枢的排名。

如果我们近似 ，那么在下列情况下，寻找新的中枢将具有更好的收益与成本比率：