插入排序python我的排序代码无法正常排序，如何解决？

Question

插入排序python
我的排序代码无法正常排序，会重复同一元素，我找不到我哪错了

# 定义函数 insertion_sort 接受参数 list_sort，并返回插入排序结果。
def insertion_sort(list_sort):
    for i in range(1, len(list_sort)):
        x = list_sort[i]
        for j in range(i - 1, 0, -1):  # 从 i-1 开始，直到 j 为 0
            if list_sort[j] > x:
                list_sort[j + 1] = list_sort[j]  # 向右移动元素
            else:
                list_sort[j + 1] = x  # 插入 x
                break
    return list_sort


# 测试代码
list_sort = list(map(int, input().split()))
x = insertion_sort(list_sort)
print(x)

我的输入是14 15 171 23 1 4 67 87 46 27 252 345 4 25 33 45 98
输出是[14, 14, 14, 14, 15, 23, 25, 27, 33, 45, 46, 67, 87, 98, 171, 252, 345]
我该怎样才能解决

Answer 1

下午好🌅🌅🌅
本答案参考ChatGPT-3.5

问题分析：

插入排序是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。在上述代码中，j 应该从 i-1 开始，直到 j 为 -1，而不是 0，否则第一个元素将被跳过，导致排序失败；同时，插入排序的步骤应该是把当前元素插入到正确的位置，而不是直接把当前元素替换成正确的元素，因此需要增加一个 break 语句来中断内层循环。

解决方案:

1.将内层循环的范围改为从 i-1 开始，直到 -1 。

2.在找到正确位置后，使用 break 语句中断内层循环。

修改后的代码如下：

def insertion_sort(list_sort):
    for i in range(1, len(list_sort)):
        x = list_sort[i]
        j = i-1
        while j>=0 and list_sort[j]>x:
            list_sort[j+1] = list_sort[j]
            j -= 1
        list_sort[j+1] = x
    return list_sort

测试一下：

14 15 171 23 1 4 67 87 46 27 252 345 4 25 33 45 98

输出：

[1, 4, 4, 14, 15, 23, 25, 27, 33, 45, 46, 67, 87, 98, 171, 252, 345]