插入排序 空间复杂度

插入排序是一种简单直观的排序算法，它的基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。空间复杂度是指执行算法所需的额外内存空间，与算法的存储需求有关。

插入排序的空间复杂度是 O(1)。这是因为插入排序过程中只需要一个额外的空间来暂存当前元素，不论输入数组的大小如何，这个空间都是常数级别的。它是一种原地排序算法，不需要额外的存储空间来存放整个数组，因此空间效率很高。在最坏的情况下，即输入数组完全逆序时，插入排序的时间复杂度为 O(n^2)，但空间复杂度始终保持在 O(1)。