只使用For循环在Python中实现插入排序

Question

我尝试只使用for循环实现插入排序，并编写了以下代码：

def isort(L):    #implementation with a for loop
    for i in range(1,len(L)):
        small = L[i]
        M = range(i)
        M.reverse()
        for j in M:
            if small<L[j]:
                L[j+1]=L[j]
            else:
                break
        L[j+1] = small
    return L

L = [5,4,3,2,1]
M = isort(L)
print M

这给出了输出[5,1,2,3,4]。有人能指出我在哪里出错吗

Answer 1

一个错误是由一个小错误引起的

L[j+1] = small

收件人：

^{pr2}$

测试：

>>> isort([5, 4, 3, 2, 1])
[1, 2, 3, 4, 5]

---

然而，您的代码还有一些其他的东西，如图所示-它在很多时候都不能工作。只要稍作调整，我们就能让它发挥作用：

def isort(L):
    for i in range(1,len(L)):
        small = L[i]
        M = range(-1, i)
        M.reverse()
        for j in M:
            if j>=0 and small<L[j]:
                L[j+1]=L[j]
            else:
                break
        L[j+1] = small
    return L

测试：

>>> isort([4, 5, 3, 2, 1])
[1, 2, 3, 4, 5]

Answer 2

这有点棘手：

我将内循环范围函数取为range(j, -2, -1)，因此内部循环总是在前面的一个位置中断，所以最后一个语句arr[j + 1] = key工作得很好

arr = [5, 4, 3, 2, 1]
for i in range(1, len(arr)):
    j = i - 1
    key = arr[i]
    for j in range(j, -2, -1):
        if j < 0 or key >= arr[j]:
            break
        else:
            arr[j + 1] = arr[j]

    arr[j + 1] = key

Answer 3

内部循环的后置条件是j指向小于small的第一个值（这是通过break调用实现的）。然而，当j=0时，循环自然存在，因此在最后一次内部迭代中，条件不是您所期望的。在

为了解决这个问题，我建议从-1初始化M：

M = range(-1, i)

但是，您还必须检查j是否为正（以避免做出您不希望进行的更改）：

^{pr2}$