Python实现插入排序(Insertion sort)未处理列表末尾元素问题排查

核心问题定位 #

你当前代码没有处理最后一个元素，以及排序逻辑异常的核心原因有4个：

• 外层循环的过滤条件错误：if user_list[index] < user_list[-1] 会直接跳过所有大于等于列表末尾元素的节点，同时末尾元素本身永远不满足「小于自身」的条件，自然全程不会被处理。
• 遍历起始位置不符合插入排序逻辑：插入排序默认第一个元素属于已排序区间，应该从索引1（第二个元素）开始遍历待插入节点，你从索引0开始属于无效操作。
• 变量冗余：你定义的sorted_list全程没有参与排序逻辑，仅做了初始化插入第一个元素的操作，没有实际作用。
• 内层交换逻辑错误：你当前的内层循环仅做相邻元素对比交换，没有锚定当前待插入的元素，排序逻辑不完整，即使去掉外层的错误判断也无法得到正确结果。

修复后的实现代码 #

def insertion_sort(user_list):
    # 从第二个元素开始遍历待插入节点
    for index in range(1, len(user_list)):
        current_insert_val = user_list[index]
        # 向前遍历已排序区间找插入位置
        pre_index = index - 1
        while pre_index >= 0 and user_list[pre_index] > current_insert_val:
            # 大于待插入值的元素后移一位
            user_list[pre_index + 1] = user_list[pre_index]
            pre_index -= 1
        # 插入到对应位置
        user_list[pre_index + 1] = current_insert_val
        print(user_list)
    print("\n\n最终排序结果：", user_list)


if __name__ == '__main__':
    user_list = [4, 3, 2, 10, 12, 1, 5, 6]
    insertion_sort(user_list)

运行验证 #

输入示例列表运行后，最终会输出正确的排序结果：[1, 2, 3, 4, 5, 6, 10, 12]，包含原列表的最后一个元素6。

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