插入排序不排序

Question

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

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

结果：2 1个 3个 6个 4个 7 5个 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 可能会有用。

Answer 2

与往常一样，这是一个差一错误，下面的代码已修复。我还把一些部分做得更漂亮了。

def insertion_sort(mylist):
    sorted_list = []
    for i in mylist:
        for index, j in enumerate(sorted_list):
            if j > i:
                sorted_list.insert(index, i) #put the number in before element 'j'
                break
        else:
            sorted_list.append(i) #put number at the end of the list
    return sorted_list

Answer 3

正如 Efferalgan 和 tzaman 提到的，您的核心问题是差一错误。要捕获此类错误，在每次循环迭代时打印 i、j 和 sorted_list 很有用，以确保它们包含您认为包含的内容。

这里有几个版本的算法。首先，您的代码的修复版本修复了差一错误；如果找不到插入位置，它还实现了 Efferalgan 使用 .append 的建议。

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, 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.append(i) #put number at the end of the list
    return sorted_list

这是一个稍微改进的版本，它在循环中使用 else 子句而不是 posfound 标志；它还使用切片赋值来进行插入。

def insertion_sort(mylist):
    sorted_list = []
    for i in mylist:
        for j in range(len(sorted_list)):
            if sorted_list[j] > i:
                sorted_list[j:j] = [i]
                break
        else: #if you can't find a place in the list
            sorted_list.append(i) #put number at the end of the list
    return sorted_list

最后，使用 enumerate 获取索引和项目的版本 sorted_list 而不是简单的 range 循环。

def insertion_sort(mylist):
    sorted_list = []
    for u in mylist:
        for j, v in enumerate(sorted_list):
            if v > u:
                sorted_list[j:j] = [u]
                break
        else: #if you can't find a place in the list
            sorted_list.append(u) #put number at the end of the list
    return sorted_list

插入排序不排序

Insertion sort doesn't sort

python

algorithm

insertion-sort