当数组近乎有序且k为常数时，INSERTION SORT的时间复杂度是多少？

插入排序的核心逻辑是：遍历数组时，将当前元素向前与已排序部分的元素逐一比较，交换到它的正确位置。

针对题目中**每个元素与其正确位置的偏移量最多为k（k为常数）**的场景：

• 每个元素在插入过程中，最多只需要向前比较并移动k次——因为它距离自己的最终位置不会超过k个位置
• 数组共有n个元素，总操作次数为 n * O(k)，由于k是固定常数，O(k) 等价于常数级操作，因此整体时间复杂度为 O(n)

对比普通插入排序的最坏情况（逆序数组，每个元素需移动n次，总复杂度O(n²)），这种近乎有序且偏移量受限的场景下，插入排序的效率会大幅提升到线性级别。

内容的提问来源于stack exchange，提问作者m615