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