我对一家公司进行了书面一轮。我有一个问题有人可以帮助我吗？
以下哪个是最快的排序算法？
a - 冒泡排序
b - 壳排序
c - 堆排序
d - 快速排序
我很困惑黑白快速排序和堆排序都有 O(nlogn) 的时间复杂度。
问问题
7413 次
3 回答
10
没有“最快”的排序算法。
算法的理论性能总是取决于输入数据。在各自最坏的情况下，堆排序比快速排序快。在一般情况下，快速排序更快。有可能为每种算法制定一个定制的最佳案例，以使其优于所有其他算法。
这实际上是存在诸如Introsort之类的“混合”算法的原因：Introsort 从快速排序开始，如果它发现快速排序正在处理这个特定的输入，则切换到堆排序。
最重要的是，任何算法的实际性能都会受到它在特定硬件平台上的运行情况的显着影响。如果后者与硬件的属性更好地“同步”，理论上“快速”算法可能会惨败给原始和“慢速”算法。
于 2012-07-29T19:48:47.867 回答
4
参见维基百科：堆排序
堆排序：虽然在大多数机器上的实践中比实现良好的快速排序要慢一些，但它具有更有利的最坏情况 O(n log n) 运行时的优势
于 2012-07-29T19:48:41.943 回答
2
在一般情况下：快速排序，因为它的 O(nlgn) 运行时间常数更好。
在最坏的情况下：堆排序，因为在最坏的情况下，快速排序的运行时间是 O(n 2 )。
于 2012-07-30T12:05:52.783 回答