arrays - 对一个已经排序的数组进行排序，除了一个乱序的元素

Question

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

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

现在我已经知道最好的方法是使用插入排序，在这种情况下这将花费 O(n) 时间，但由于它告诉我们除此之外的其他方法，我不确定该使用哪个。

• 快速排序会很糟糕，因为数组已经排序。
• 堆排序不会完全利用数组排序的特性，需要 O(nlogn) 的时间。
• 合并排序也采用 O(nlogn)，因为它不区分输入顺序。
• 冒泡排序也需要 O(n^2)。真的需要一些帮助，我是否遗漏了什么？

Answer 1

natural variant of merge sort将在 O(n) 时间内对描述的列表进行排序。

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