为什么 Insertion_Sort 在列表中重复数字而不是排序？

Question

我试图使用讲座提供的示例代码来实现插入排序代码，尽管逐字放置代码，插入排序函数不会按升序对数组进行排序。相反，代码给出了一个重复的数字，比如数组中的 2。

我尝试将 range 函数的最终值从 n-1 调整到 n，但它所做的只是给我 2 个数组，这两个数组都至少有 1 个重复的数字。在 while 循环下更改 array[j] 和 array[j - 1] 的位置只会将重复的数字从 2 更改为 3。

似乎没有任何东西可以对数组进行排序来给出答案 [1,2,3]，而且我不知道这段代码究竟出了什么问题，那么为什么插入排序给了我重复项而不是正确地对数组进行排序？

下面的代码是我正在使用的。

def function insertion_sort(array):
    
    n = len(array)
    
    for i in range(1, n-1): 
        j = i #j is inner index, i is inner index
        temporary = array[j]
       
        
        while (j > 0) and (array[j] < array[j-1]):
            array[j]= array[j - 1]#shift right
            j = j - 1 #move left 
            print(array)
            
        array[j] = temporary #save to final position

array = [3,2,1] #test case
insertion_sort(array)

n-1改为n时的结果：

[3, 3, 1] #3 is duplicated, 2 has disappeared

交换数组位置后的结果：

[2, 2, 1] #2 is duplicated, 3 has disappeared

Answer 1

由于您能够运行代码，我认为

function

这个词只是您在这里的帖子中的一个错误 - 它不应该在那里。

除此之外，还有以下问题：

一旦
• array[j] < array[j-1]

  进入数组已排序部分，比较

  j

  将为 false，这将阻止内部循环进行第二次迭代。你真正想要的是比较

  temporary < array[j-1]

  。通过该修复，您的函数将以升序对数组进行排序。

• range(1, n-1)

  防止循环将

  last

  值移动到其排序位置。该范围目前不包括 n-1（这就是

  range

  的工作原理）。应将其更正为

  range(1, n)

  。

您似乎期望打印排序操作的结果，但事实并非如此。在转换过程中间的某个地方有一个
• print

  语句，这会给重复项带来错误的印象。另一方面，您的代码不会显示函数调用的最终结果。您应该在

  print(array)

  的呼叫之后放置

  insertion_sort(array)

  。然后你就不会看到重复的了。
  其他一些备注：

一条评论说“j是内部索引，i是内部索引”并没有澄清任何有用的东西。

• 此外，不需要在比较运算符两边加上括号。

• 这是您的代码，其中应用了这些修复：

def insertion_sort(array):
    n = len(array)
    
    for i in range(1, n):
        j = i 
        temporary = array[j]
        while j > 0 and temporary < array[j - 1]:
            array[j] = array[j - 1]  # shift right
            j = j - 1  # move left             
        array[j] = temporary  # save to final position

array = [3,2,1]  # test case
insertion_sort(array)
print(array)  # 1 2 3

更多Python风格

在 Python 循环中，使用

j = j - 1

之类的内容更新循环变量并不常见。内部循环可以用更 Pythonic 的方式重写。

• 在迭代数组时，您还需要索引，您可以从使用 

  enumerate
函数中受益。

• 右移操作可以延迟到内循环

  之后
。届时，您可以使用切片语法一次性将多个相邻项目向右移动。
• 例如：

def insertion_sort(array):
    for i, value in enumerate(array):
        for j, other in enumerate(array):
            if other >= value:
                break  # guaranteed to occur
        # Move value back to index j, shifting the intermediate slice to the right
        array[j:i+1] = value, *array[j:i]

如果我们将内部循环变成

next()

理解式，那么：

def insertion_sort(array):
    for i, value in enumerate(array):
        j = next(j for j, other in enumerate(array) if other >= value)
        array[j:i+1] = value, *array[j:i]

我认为你的代码是有效的。但请注意，由于此比较，当前您的实现按降序对数字进行排序：

Answer 2

应该将其恢复为按升序对数组进行排序。

您的问题在于理解代码的作用。你谈论它给了你什么，但实际上你的功能并没有“给”你任何东西。您只打印出一个中间结果（就在将临时值分配回来之前，这就是您认为会得到重复项的原因）。你应该在所有处理之后替换这个 print() 或者让你的函数返回一些东西。

尝试使用各种测试用例来找出代码中可能存在的问题。 我还认为，由于您正在学习，因此您并没有完全掌握代码的作用。尝试阅读一些有关算法和 Python 的内容。