仅使用 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

在编程中，我们经常会遇到一些问题，特别是在使用某些工具或库的时候。有时候，错误信息可能会让人感到困惑，不知道该如何解决。

比如，有人可能在使用某个库时，突然出现了一个错误提示，这个提示可能会告诉你某个东西没有找到，或者某个功能无法正常工作。对于刚开始学习编程的人来说，这些信息可能听起来很复杂。

其实，解决这些问题的关键在于理解错误信息的含义，以及如何一步步排查问题。通常，我们可以通过查阅文档、搜索相关问题，或者向其他人请教来找到解决方案。

总之，遇到问题时不要慌张，慢慢分析错误信息，寻找解决办法，编程的过程就是不断学习和解决问题的过程。

if __name__ == "__main__":
    n = int(input("How many numbers ?\t"))    
    nums = [int(x) for x in input("Enter {} numbers\t".format(n)).split()]    

    for i in range(1,n):        
        val = nums[i]  
        for j in range(i-1,-2,-1):           
            if j < 0 : break
            if nums[j] > val:
                nums[j+1] = nums[j]
            else:                                
                break
        nums[j+1] = val

    for num in nums:
        print(num,end=' ')

    print()

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

更改（问题中提到的修复很简单，那个偶发错误是因为多了一个小小的 +1 :))：

L[j+1] = small

变更为：

L[j] = small

测试：

>>> 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 4

内层循环的结束条件是，j指向第一个小于small的值（这是通过break语句实现的）。不过，当j=0时，循环自然会结束，因此在每次最后的内层迭代中，条件可能不是你预期的那样。

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

M = range(-1, i)

但是，这样的话，你还得检查一下j是否为正数（以避免做出不想要的更改）：

if j>=0 and small<L[j]:
    L[j+1]=L[j]