我的插入 python 排序总是将第二个数字放在开头

Question

我的代码大部分工作正常，除了一个小错误，它会将第二个元素放在开头，而不管值如何，例如1,6,2,9,3,8,4,7,5,0 会变成 6,0,1,2,3,4,5,7,8,9

我试过稍微改变 FOR 循环中的数字，但除此之外真的看不出问题所在

def InsertionSort(array):
    for i in range(len(array)):
        for j in range(len(array)):
            if array[i] <= array[j+1]:
                new = array.pop(i)
                array.insert(j+1,new)
                break
            elif array[i] > array[j+1]:
                continue
        print (array)

Answer 1

任何时候您修改正在循环访问的集合时，您都可能会得到与预期不同的行为。当您从集合中删除项目时尤其如此，因为它会扰乱当前索引。

这是一个简单地交换元素顺序的示例（同时还打印调试信息，以便您可以准确地看到发生了什么）：

def insertionSort(my_list):
    # for every element in our array
    for index in range(1, len(my_list)):
        current = my_list[index]
        position = index

        while position > 0 and my_list[position-1] > current:
            print("Swapped {} for {}".format(my_list[position], my_list[position-1]))
            my_list[position] = my_list[position-1]
            print(my_list)
            position -= 1

        my_list[position] = current

    return my_list

my_list = [8,2,1,3,5,4]

print(insertionSort(my_list))

Answer 2

这里的问题是，你将第二个元素的位置与第一个元素调换了位置，但后来不再比较它了。

这里的实现与您的很接近，只是为了处理所有条目而稍作改动

ar =[1,6,2,9,3,8,4,7,5,0]
def InsertionSort(array):
    for i in range(len(array)):
            val = array[i]
            while( i > 0 and array[i-1] > val):
                array[i] = array[i-1]
                i = i - 1
            array[i] = val
    print (array)

InsertionSort(ar)

我的插入 python 排序总是将第二个数字放在开头

My insertion python sort is always placing the second number at the beginning

python

list

sorting

iteration

insertion-sort