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

文章预览

原文地址：http://www.inference.org.uk/mackay/sorting/sorting.html 作者：David MacKay 许多文章都对堆排序（HEAPSORT）和快速排序（QUICKSORT）进行了比较。 其中大部分都是这样说的："两者都需要 NlogN 的平均时间，但 QUICKSORT 的良好表现通常在实践中胜过 HEAPSORT。 " 有些人则更进一步，给出了量化细节：平均而言，HEAPSORT 的比较次数是 QUICKSORT 的两倍，但 HEAPSORT 避免了性能灾难性下降的可能性。 但似乎很少有人会问这样一个问题："为什么 HEAPSORT 要使用两倍的比较次数？ " 人们花费大量精力试图 "两全其美"，制造出混合排序算法，如"内省排序"（introspective sort），它递归应用 QUICKSORT，如果递归深度变大，偶尔会切换到 HEAPSORT。 Paul Hsieh 对 QUICKSORT 和 HEAPSORT 进行了深入比较。他说： " 我怀疑 HEAPSORT 的表现应该会好于其糟糕的名声，我认为这些结果证明了这一点。 " ………………………………