MergeSort、QuickSort还是HeapSort？

Question

在执行比较的次数和算法所需的内存量方面，这三种算法的相对优势是什么。它们中的哪一个的运行时间是有保证的？

Answer 1

我认为Wikipedia's coverage of this很全面，回答了你所有的问题。对照表显示了最佳、平均和最差情况下的性能、内存使用情况以及稳定性等其他特性。

Answer 2

通过查看维基百科可以很容易地回答这个问题：

http://en.wikipedia.org/wiki/Sorting_algorithm

如果您不确定如何寻找“有保证的”运行时，那么您正在寻找最坏的情况。

Answer 3

如果你想要一个直观的解释，多伦多大学的一个CS小组在20世纪80年代提出了一种称为排序的this classic animation film。值得一看，它涵盖了三种排序类型和场景，它们工作得最好(也不是很好)-以及为什么。