为什么插入排序是排序或近似排序数组的最佳算法？

Question

所以我猜它是因为它只是比较 A[k] 和 A[k-1]，并在一次扫描中实现，但它仍然不清楚。有人可以更好地解释一下吗？谢谢

Answer 1

此链接显示了不同类型数据集的排序算法的图形表示。正如您所看到的，当数据排序后，算法复杂度降低到 N。这相当于作为输入的元素数量。

提供的链接清楚地展示了如何提高效率。