这是在谷歌面试中问到的，我没有得到答案。更糟糕的是没有得到问题。
在讨论排序算法时，我们讨论的是已排序文件的行为。为什么我们对排序一个已经排序的文件需要多长时间感兴趣？简要解释您的答案？
最佳答案
假设问题是关于已排序的输入(不一定是文件)的行为，不同的排序算法在收到已排序的输入时表现不同:
- 在插入排序的情况下，你会得到最好的情况，即
O(n) - 在没有随机化的情况下实现快速排序，已经排序的输入将导致最坏的情况! (
O(n^2))
这两个简单示例表明，您必须在算法分析中包括排序算法对已排序输入的行为。
主要原因是在实际应用中，用户的输入往往以排序或接近排序的形式出现，举几个例子:
- almost-chronological data - 按时间顺序接收的数据，但偶尔会有一些元素位置不对(见下面的链接)
- 自然排序 - 当您增加用户数据库时，您可能会为新用户分配更高的 ID
另请参阅:
关于algorithm - 为什么我们对排序一个已经排序的文件需要多长时间感兴趣？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29745920/