已排序数组的时间复杂度最小的排序算法？

Question

我有一个问题，当我们得到一个已经排序的数组时，哪种排序算法的时间复杂度最低。

Answer 1

维基百科有一个表格，显示了许多不同排序算法的最佳、平均和最坏情况性能的比较。这是摘录：

对于最佳情况输入（即预先排序的数据），有很多算法具有 () 运行时间。但是，它们中的大多数（例如冒泡排序）对于平均和最坏情况输入具有 (²) 运行时间。这是你真正想要避免的事情。使用其中一种算法对一百万个项目进行排序将需要永恒的时间。

幸运的是，其中一些算法具有 (log) 平均和最坏情况运行时间。这些如下：

• 立方体排序
• 平滑排序
• 块排序

我会建议使用其中之一。