algorithm - 合适的排序算法

Question

我有点不确定我对以下问题的回答。请帮忙：

假设给你一个包含 N 个整数的列表。除一个整数之外的所有整数都按数字顺序排序。确定一种排序算法，它将在 O(N) 时间内对这种特殊情况进行排序，并解释为什么这种排序算法在这种情况下达到 O(N) 运行时间。

我认为这是插入排序，但不确定为什么会这样。

谢谢！！

Answer 1

插入排序是自适应的，并且对于基本上排序的数据集是有效的。它可以在 O(n+d) 中对几乎排序的数据进行排序，其中 d 是反转次数，在您的情况下 d 是 1。