python - Python 中的插入排序

Question

我有一份 Python 作业，结果脑子一片空白。所以我应该使用插入排序进行 O(nˇ2) 练习。 例如，我有两个列表 [] 和 [5,8,1,1]，程序应该通过从第一个列表中删除值并按正确的顺序插入另一个列表，将值从一个列表插入到另一个列表中: [][5,8,1,1] = [5][8,1,1] = [5,8][1,1] = [1,5,8][1] = [1,1, 5,8][]

我想出了一些东西，不知道我是否走在正确的轨道上，但这似乎是最合理的。缩进是有序的，但在这里复制代码不知何故弄乱了它。 P.S 对爱沙尼亚语感到抱歉，必须用爱沙尼亚语编写代码。

def pisteMeetod2(t2ishulk):
    tulemus = [] #new list
    hulgacopy = t2ishulk[0:len(t2ishulk)] #main list
    for el in t2ishulk: #going through first list
        if not tulemus: #if list empty (which it at the beginning is) then from here
            tulemus.append(el)
            del hulgacopy[0]
        else:
            for elemendid in tulemus: #check if there is a lower element from new list
                n = 0
                if hulgacopy[0] <= tulemus[n]:
                    tulemus.insert(n-1,el)
                    del hulgacopy[0]
                    break
                n = n + 1

所以现在我遇到了如何处理第二个循环的问题。在完成检查结果列表中名为“tulemus”的元素后，如果没有找到任何匹配项，我应该如何继续我的代码，以便它将“el”附加到 tulemus 中。

Answer 1

您可以将 else 子句添加到内部 for 循环:

for elemendid in tulemus: #check if there is a lower element from new list
    n = 0
    if hulgacopy[0] <= tulemus[n]:
        tulemus.insert(n, el)
        del hulgacopy[0]
        break
    n = n + 1
else:
    tulemus.append(el)
    del hulgacopy[0]

如果循环没有使用break终止，它的主体就会被执行。您可以在 Python 的 official tutorial 中阅读有关循环的 else 子句的更多信息。 .

另请注意，如果您在迭代时找到插入点，则应使用 tulemus.insert(n, el) 而不是 tulemus.insert(n-1, el) 在那里插入当前元素。否则，当 n == 0 时，您最终会在列表末尾(索引 -1)插入。