arrays - 在给定条件下哪种排序采用 O(n)

Question

我正在准备一场比赛并偶然发现了这个问题:考虑一组 n 个元素，除了一个元素出现乱序外，这些元素已排序。以下哪项需要 O(n) 时间？

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

我的推理如下:

• 我知道合并排序即使在最好的情况下也需要 O(nlogn)，所以这不是答案。
• 快速排序也将花费 O(n^2)，因为数组几乎已排序。
• 可以选择冒泡排序，但前提是我们对其稍作修改以检查是否在传递中进行了交换。
• 可以选择堆排序，就像我们创建排序数组的最小堆一样，它需要 O(n) 时间，因为只有一个人不在位，所以他需要 logn。

因此我认为它是堆排序。这个推理正确吗？我想知道我是否遗漏了什么。

Answer 1

让我们从冒泡排序开始。根据我的经验，我使用的大多数资源都是定义的冒泡排序，其停止条件是在迭代中不执行任何交换(参见例如 Wikipedia )。在这种情况下，冒泡排序确实会在线性步数后停止。但是，我记得我偶然发现了说明迭代次数恒定的描述，这使您的情况成为二次方。因此，关于这个案例，我只能说“可能是”——这取决于比赛评委使用的定义。

关于合并排序和快速排序，您是正确的——这两种算法的经典版本都对每个输入强制执行 Θ(n log n) 行为。

但是，您关于堆排序的推理对我来说似乎是不正确的。在堆排序的典型实现中，堆的构建顺序与所需的最终顺序相反。因此，如果您决定构建一个最小堆，算法的结果将是相反的顺序，我猜这不是想要的。另一方面，如果您决定构建最大堆，堆排序显然会花费大量时间上下筛选元素。

因此，在这种情况下，我会选择冒泡排序。