python插入排序奇怪的錯誤

Question

我不知道語言，數據類型或我的算法是否與它有關，但我得到這個奇怪的錯誤與我的插入排序用python編寫。我明天寫它在準備一個潛在的試題，和它的作品，但似乎只用於數字工作> = 1。我將展示給兩個不同的輸入輸出：

#Insertion Sort 
#Has some weird bug; only works for numbers >= 1. 
def insertion(arr): 
    for i in range(1,len(arr)): 
     m = arr[i] 
     for x in range(i-1,-1,-1): 
      if(arr[x] > m): 
       arr[x+1] = arr[x] 
      else: 
       arr[x+1] = m 
       break 
    return arr 

以下是設定的賦予功能的輸入：

l1 = [1,3,7,2,5,8,4,6] 
l2 = [1.1,3.7,7.0,2.5,5.1,8.3,4.0,7.9,6.0] 
l3 = [1,3,7,2,5,8,0,4,6] 
l4 = [1.1,3.7,7.0,2.5,5.1,8.3,4.0,7.9,6.0,0.3] 

以下是輸出相對於上述輸入列表

n1 = [1, 2, 3, 4, 5, 6, 7, 8] 
n2 = [1.1, 2.5, 3.7, 4.0, 5.1, 6.0, 7.0, 7.9, 8.3] 
n3 = [1, 1, 2, 3, 4, 5, 6, 7, 8] 
n4 = [1.1, 1.1, 2.5, 3.7, 4.0, 5.1, 6.0, 7.0, 7.9, 8.3] 

似乎排序功能將移動VALU一直到最開始，但隨後用列表中的最低值替換它們。我認爲這是一個非常奇怪的錯誤，但現在沒有時間去研究它（總決賽從下週開始，因爲我們在季度系統上）。我想也許這裏有人想解決這個問題。這可能只是我邏輯中的一個錯誤，但我覺得奇怪的是，它適用於所有值爲1或更大的值。

Answer 1

問題是如果m比它之前的數組arr中的每個元素都小，那麼你從未設置過arr[0] = m。如果arr[x] > m個案總是成立，那麼您從未在arr到m之間設置任何條目。所以你會一路走到前面，將第一個元素複製到第二個位置（當x爲0時，arr[x+1] = arr[x]），但從未實際插入m,arr[0] = m的第0位。一個（也許是不尋常的）的方式來做到這一點是使用Python的for... else建設，其中else情況下被調用，如果你從來沒有break出for循環：

def insertion(arr): 
    for i in range(1,len(arr)): 
     m = arr[i] 
     for x in range(i-1,-1,-1): 
      if(arr[x] > m): 
       arr[x+1] = arr[x] 
      else: 
       arr[x+1] = m 
       break 
     else: 
      arr[0] = m 
    return arr