Python实现Insertion Sort插入排序输出错误排查修正

核心逻辑偏差说明 #

插入排序的核心执行逻辑如下：

1. 初始将数组分为两段：索引0的元素属于已排序区间，索引1到末尾的元素属于未排序区间
2. 每轮取出未排序区间的第一个元素，向前遍历已排序区间
3. 遍历过程中所有比当前待插入元素大的已排序元素，统一向后移动一位，腾出空位后将待插入元素放到正确位置
4. 重复上述流程直到未排序区间清空

你当前的实现存在两个关键错误，不符合上述逻辑：

• 内层循环范围错误：你写的reversed(range(1, i))遍历范围最大仅到i-1位置，完全没有覆盖当前轮次需要插入的array[i]元素。比如最后一轮i=5（对应元素2）时，内层循环根本不会触碰索引5的位置，这也是输出结果末尾残留2的直接原因。
• 比较逻辑错位：你的内层循环仅在已排序区间内部做相邻元素比较交换，没有锚定「当前待插入的未排序元素」做向前插入操作，本质是在已排序区间内做局部冒泡，偏离了插入排序的核心思路。

修正方案 #

标准实现（移位法，效率更高） #

不需要每次相邻交换，先缓存待插入元素，将比它大的元素统一后移，最后一次性插入即可：

def insertion_sort(array):
    for i in range(1, len(array)):
        # 缓存当前待插入的未排序元素
        current = array[i]
        # 从已排序区间的末尾开始向前比较
        j = i - 1
        while j >= 0 and array[j] > current:
            # 比当前元素大的已排序元素向后挪一位
            array[j + 1] = array[j]
            j -= 1
        # 找到插入位置，放入待插入元素
        array[j + 1] = current
    return array

to_sort = [4, 3, 1, 5, 6, 2]
print(insertion_sort(to_sort))

运行输出为[1, 2, 3, 4, 5, 6]，结果完全有序。

保留原有交换写法的修正版本 #

如果要沿用你原本的双层for循环+相邻交换的思路，只需要修正内层循环范围，让遍历覆盖到i位置的待插入元素即可：

def insertion_sort(array):
    for i in range(1, len(array)):
        # 内层循环从i位置开始向前遍历，将待插入元素逐步交换到正确位置
        for j in reversed(range(1, i + 1)):
            if array[j-1] > array[j]:
                array[j-1], array[j] = array[j], array[j-1]
            else:
                # 已找到合适位置，提前终止循环减少无效比较
                break
    return array

这里仅把你原来代码里的range(1, i)改成了range(1, i+1)，就可以覆盖待插入元素，加上break后时间复杂度和标准实现一致。

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