数组含I个逆序时Insertion Sort的时间复杂度（含最优/最坏情况）

插入排序的核心逻辑是：遍历数组，将每个元素向前插入到已排序区间的正确位置。这个过程中，每个元素的移动次数等于它前面比它大的元素个数，而所有元素的移动次数总和恰好等于数组中的逆序数I——因为每一次元素移动都会消除一个逆序对。

时间复杂度与逆序数的关系 #

插入排序的时间开销由两部分组成：遍历数组的固定开销（O(n)），以及处理逆序的比较、移动开销（O(I)）。整体时间复杂度为 Θ(n + I)：

• 比较次数：最少为I（每个逆序对对应一次比较），最多为I + n - 1（每个元素除第一个外，需和已排序区间所有元素比较）
• 移动次数：恰好等于I，每个逆序对对应一次元素移动

最优情况 #

当数组完全有序时，逆序数I=0。此时插入排序仅需遍历数组，每个元素仅需与前一个元素比较1次，无需移动元素。时间复杂度为 O(n)。

最坏情况 #

当数组完全逆序时，逆序数I = n*(n-1)/2（所有i<j的位置都构成逆序对）。此时每个元素都需要移动到已排序区间的最前端，比较和移动次数均为O(n²)。时间复杂度为 O(n²)。

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