插入排序错误列表索引

Question

我正在尝试创建一个由 7 个随机生成的数字组成的数组，然后使用插入排序方法将这些数字从小到大排序。我浏览了几个以前回答的主题，因为这是一个非常常见的问题，但每个用户对我的代码都非常不同，这让我想知道我哪里出错了。

import random # importing the random module
arrayInsertion = []

for i in range (7): # 7 different numbers
    arrayInsertion.append(random.randint (1,10))

for i in range (1,7):
    while  i > 0 and arrayInsertion [i+1] > arrayInsertion [i]:
        arrayInsertion [i] = arrayInsertion [i-1]
        i = i - 1
print (arrayInsertion)

当运行此代码时，我收到以下错误消息：

Traceback (most recent call last): File "C:\Users\Ben\Desktop\insertion sort.py", line 8, in while i > 0 and arrayInsertion [i+1] > arrayInsertion [i]: IndexError: list index out of range

Answer 1

问题是 arrayInsertion[i + 1] 当 i = 7 然后 i 超出范围时，因为列表中只有 7 个元素。您也不记得当前值和索引。

for i in range(1, len(arrayInsertion)):
    curr = arrayInsertion[i]
    pos = i
    while pos > 0 and arrayInsertion[pos - 1] > curr:
        arrayInsertion[pos] = arrayInsertion[pos - 1]
        pos -= 1
    arrayInsertion[pos] = curr

正确的结果是：

[5, 5, 5, 6, 6, 8, 9]

为了将来使用考虑将其打包到一个函数中 def insertion_sort(a)。

Answer 2

def insert_sort(list_input):
    for unsorted_id in range(len(list_input)):
        element = list_input[unsorted_id]
        sorted_id = unsorted_id - 1
        while sorted_id >= 0 and element > list_input[sorted_id]:
            list_input[sorted_id + 1] = list_input[sorted_id]
            sorted_id -= 1
        list_input[sorted_id + 1] = element
    return list_input

Answer 3

您也可以只使用内置的 .sort() 方法

Answer 4

for i in range(1,7)

Above line of code will produce 1 to 6 sequentially (1,2,3,4,5,6)

while  i > 0 and arrayInsertion [i+1] > arrayInsertion [i]

arrayInsertion [i+1] in above line in try to access arrayInsertion[7] for i = 6 which is not present

所以它会抛出IndexError: list index out of range

插入排序错误列表索引

Insertion sort error list index

python

insertion-sort

insertion