python - 插入排序不排序

Question

我试图在 python 中创建一个插入排序，但是返回的列表没有排序。我的代码有什么问题？

给出的参数:[3, 2, 1, 4, 5, 8, 7, 9, 6]

结果:21个3个6个4个75个8个9

Python代码:

def insertion_sort(mylist):
    sorted_list = []
    for i in mylist:
        posfound = 0 #defaults to 0
        for j in range(len(sorted_list)):
            if sorted_list[j] > i:
                sorted_list.insert(j-1, i) #put the number in before element 'j'
                posfound = 1 #if you found the correct position in the list set to 1
                break
        if posfound == 0: #if you can't find a place in the list
            sorted_list.insert(len(sorted_list), i) #put number at the end of the list
    return sorted_list

Answer 1

您需要将 sorted_list.insert(j-1, i) 更改为 sorted_list.insert(j, i) 以在位置 j< 之前插入。

insert(j-1, ..) 将在 previous 元素之前插入，在 j=0 的情况下它'将环绕并插入到最后一个元素之前。

Python data structures tutorial可能有用。