algorithm - 已排序数组的时间复杂度最低的排序算法？

Question

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

Answer 1

维基百科有一个表格显示 comparison of the best, average and worst-case performance of many different sorting algorithms .以下是摘录:

对于最佳情况输入(即预排序数据)，有很多算法具有 𝓞(𝑛) 运行时间。然而，它们中的大多数(例如冒泡排序)对于平均和最坏情况输入的运行时间为 𝓞(𝑛²)。这是您真正想要避免的事情。使用其中一种算法对一百万个项目进行排序将花费很长时间。

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

• Cubesort
• Smoothsort
• Block sort

我会推荐使用其中之一。