对已排序的数组进行排序，除了一个无序的元素

Question

我在准备比赛的时候遇到了这个问题，我无法理解。考虑数组中的一组“n”元素，除了一个出现乱序的元素之外，该数组已排序。以下哪个排序序列需要 O(n) 时间？

• 快速排序
• 堆排序
• 归并排序
• 冒泡排序

现在我已经知道最好的方法是使用插入排序，在这种情况下这将花费 O(n) 时间，但由于它另有说明，我不确定该使用哪个。

• 快速排序会很糟糕，因为数组已经排序了。
• 堆排序不会完全利用数组已排序的特性，并且会花费 O(nlogn) 时间。
• 合并排序也需要 O(nlogn)，因为它不区分输入顺序。
• 冒泡排序也需要 O(n^2)。我真的很想在这里得到一些帮助，我错过了什么吗？

Answer 1

合并排序的自然变体将在 O(n) 时间内对所描述的列表进行排序。

它的工作原理与合并排序相同，但首先识别数据中的自然运行。因此，它将识别未排序元素周围的两个运行（排序组），然后将未排序元素合并到其中一个运行中，然后将两个运行合并在一起。无论数据大小如何，这只需要两次 O(n) 合并（加上一些 O(n) 运行检测），所以它是 O(n) 。