sorting - 使用插入排序对几乎排序的数组进行排序

Question

1. 关于几乎已排序数组的插入排序，它需要线性时间。但这只有在我们的实现中有一个 if 条件才能在数组已排序时跳出循环，对吧？

2. 对于小数据集上的插入排序，为什么优先选择插入排序？因为快速排序和合并排序的比较/操作数量较少？

Answer 1

是的，几乎排序的数组需要线性时间，因为您很早就脱离了比较循环。一旦将元素插入到正确的位置，就无需遍历排序数组的其余部分。

我想这是因为您正在利用有关已排序数组的知识，而在快速排序中，您将每个元素放在正确的位置，然后对剩余的元素进行排序。