时间和空间复杂度

时间复杂度：

• 最佳情况： O(n)
  • 当数组已经排好序时，插入排序只需遍历一遍即可确认排序顺序。
• 平均情况和最坏情况： O(n²)
  • 在平均情况和最坏情况下，时间复杂度为二次，因为对于每个元素，我们可能都需要与已排序部分中的所有元素进行比较并移动元素。

空间复杂度：

• O(1)
  • 插入排序是一种“原地”算法，这意味着它不需要与输入规模成比例的额外内存。
  • 无论输入规模如何，排序所使用的空间都保持不变。

总结：

• 插入排序适用于小型数据集或几乎排好序的数组。
• 由于其二次时间复杂度，它不太适合大型数据集。
• 它的空间复杂度是常数，因此对于任何输入规模都能高效利用内存。