排序算法的效率

Question

我正在为明天的一次非常重要的面试做准备，有一件事情让我遇到了很大的麻烦：排序算法和 BigO 效率。

知道什么数字很重要？最好、最差或平均效率？

Answer 1

最差，其次是平均值。要意识到所谓的“隐藏常数”的现实影响。也是 - 例如，经典的快速排序算法在最坏的情况下为O（n ^ 2），平均为O（n log n），而在最坏的情况下mergesort为O（n log n），但quicksort将胜过mergesort在实践中。

Answer 2

当然，所有这些都很重要。您必须了解一种算法在一般案例中的好处在最坏的情况下会变成可怕的赤字，或者最糟糕的情况并不是那么糟糕，但最好的情况并不是那么好，而且它只适用于未分类的数据等

Answer 3

简而言之。

排序算法的效率会因输入数据和任务而异。

• 可以归档的排序最大速度为n*log(n)
• 如果数据包含排序的子数据，最大速度可以比 n*log(n) 更好
• 如果数据由重复项组成，排序可以在接近线性的时间内完成
• 大多数排序算法都有其用途

大多数快速排序变体的平均情况也是 n*log(n)，但它们通常比其他未高度优化的算法更快。当它不稳定时它会更快，但稳定的变体只会慢一点。主要问题是最坏的情况。最好的休闲修复方法是 Introsort。

大多数合并排序变体的最佳情况、平均情况和最坏情况都固定为 n*log(n)。它很稳定并且相对容易扩展。但它需要一个相对于总项目大小的二叉树（或其模拟）。主要问题是内存。最好的休闲修复是 timsort。

排序算法也因输入的大小而异。我可以提出一个新手说法，超过 10T 大小的数据输入，没有匹配的合并排序变体。

Answer 4

我建议你不要只记住这些事实。了解他们为何如此。如果我正在采访你，我会确保提出问题，告诉我你了解如何分析算法，而不仅仅是可以吐出你在网页或书中看到的东西。此外，面试前一天不是进行此项学习的时间。

祝你好运！请在评论中报告它是如何发生的！

Answer 5

我刚刚在我的大学接受了一组面试......

每种算法都有其优点，否则它不存在。 因此，更好地了解您正在研究的算法的优点。它在哪里做得好？如何改进？

我猜你自己需要在执行此操作时阅读各种效率符号。注意最坏的情况，并注意平均情况，最好的情况很少见。

你的面试最好。

Answer 6

您可能还想查看在存在特定条件时可以使用的其他类型的排序。例如，考虑Radix排序。 http://en.wikipedia.org/wiki/Radix_sort