插入排序不起作用 - 列表索引超出范围

Question

正在尝试创建插入排序但收到错误...

真的不知道为什么会这样。它也总是会错过 37

numbers = [45,56,37,79,46,18,90,81,50]

def insertionSort(items):
    Tsorted = []
    Tsorted.append(items[0])
    items.remove(items[0])
    for i in range(0,len(items)):
        print (Tsorted)
        if items[i] > Tsorted[len(Tsorted)-1]:
            Tsorted.append(items[i])
        else:
            Tsorted[len(Tsorted)-2] = items[i]
        items.remove(items[i])

insertionSort(numbers)

错误：

    if items[i] > Tsorted[len(Tsorted)-1]:
IndexError: list index out of range

Answer 1

您正在循环过程中从 items 中删除元素；因此，i 可能成为原始 items 中有效索引的值，但不再是缩短后的索引。

如果您需要从 items 中删除元素，看起来您应该等到循环结束。

Answer 2

第一件事：您要从数组中删除您在此处循环内迭代的项目：items.remove(items[i])。这通常不是一个好主意。

其次：这个算法没有实现插入排序，即使你修复了删除问题。您应该查看算法，例如这里 Insertion sort in Wikipedia。找到正确的插入位置需要另一个循环。

第三种：在其他情况下，您将覆盖而不是插入值。

Answer 3

那是因为你打电话给 tems.remove()。当 i=4 和 items=[37, 46, 90, 50] 时，您的代码失败。

所以他们已经没有索引为 4 但索引为 3 的元素，因为索引从 0 开始。

Answer 4

range(0,len(items) 只会在您的代码第一次遇到您的 for 循环时计算，此时状态 len(list) = 8。这意味着你将迭代

for i in [0,1,2,3,4,5,6,7]
    #Do stuff...

但同时您在每个循环中从列表中删除项目。所以当点击 i = 4 时，你已经迭代了你的循环 4 次并且你的 item-list 的长度只有 4，这意味着 items[4] 不再存在。

插入排序不起作用 - 列表索引超出范围

Insertion sort not working - list index out of range

python

insertion-sort

python-2.7