插入排序不工作

Question

我曾嘗試在python

a=[int(x) for x in input().split()] 
for i in range(1,len(a)): 
    temp=a[i] 
    for k in range (i,1,-1): 
     a[k]=a[k-1] 
     if a[k]<temp: 
      a[k]=temp 
      break 
print(a) 

輸入用於插入排序如下代碼：6 4 3 2 5 8 1

輸出：[6,4，4,4 ，4，5，8]

Answer 1

它不起作用因爲您的實現有問題。
當試圖移動部分排序列表時，您通過指定a[k] = a[k-1]來覆蓋現有的數字 - 但a[k]的前一個值在哪？

一個非常基本的解決方案（尚未就位，因爲定義了單個列表上的原始定義）可能看起來像這樣。

inp = '1 4 6 3 1 6 3 5 8 1' 

# 'a' is the input list 
a = [int(x) for x in inp.split()] 
# 'r' is the sorted list 
r = [] 
# In the original descriptions, insertion sort operates 
# on a single list while iterating over it. However, this 
# may lead to major failurs, thus you better carry the 
# sorted list in a separate variable if memory is not 
# a limiting factor (which it can hardly be for lists that 
# are typed in by the user). 

for e in a: 
    if not len(r): 
     # The first item is the inialization 
     r.append(e) 
    else: 
     # For each subsequent item, find the spot in 'r' 
     # where it has to go. 
     idx = 0 
     while idx < len(r) and r[idx] < e: idx += 1 
     # We are lazy and use insert() instead of manually 
     # extending the list by 1 place and copying over 
     # all subsequent items [idx:] to the right 
     r.insert(idx, e) 
print(r)