难以理解插入排序中的一行 (Python 3)

Question

我正在查看有关插入排序的其他线程，但没有找到与我不理解的特定部分相关的答案。

我的完整插入排序算法可以在下面看到。它按预期工作，但我无法弄清楚最后一行的目的。

数组[位置] = 值

让我通过一个例子来解释：

当'for'循环开始时，索引=1。

=> 值 = 数组[1] = 3

=> 位置 = 1

=> 因为 4 > 3，索引 1 的项目与索引 0 的项目交换。

=>位置-=1

=> 位置 = 0

我们现在到了让我感到困惑的那一行：

数组[0] = 值

=> 值 = 数组[索引] = 数组[0] = 3

但是，当 'for' 循环进行第二次迭代时，索引 = 2。

所以立即 value = array[2] 和 position = 2 ?

尽管我知道这最后一行代码是必要的，但我还是看不出它有什么用。

有人可以向我解释一下这最后的逻辑步骤吗？

提前感谢您的宝贵时间和帮助。

array = [4,3,5,6,12,9,8,6]

for index in range (1, len(array)):

   value = array[index]
   position = index

   while position > 0 and array[position - 1] > value:

       array[position] = array[position - 1]
       position -= 1

   array[position] = value

Answer 1

如果没有那条线，你不会真的交换数字，对吗？

index 1: 
-> [4,3,5,6,12,9,8,6] (enters while loop)
 -> [4,4,5,6,12,9,8,6]  ("pushes" 4 to position 1)
 -> <waits for while loop to finish>
 -> [3,4,5,6,12,9,8,6] (assigns 3 to position 0 since there are no other elements > 3)

index 2:
...

Answer 2

我认为在 for 循环的开始并不是真正需要的，因为它用于在循环内部进行索引。看图

Answer 3

位置变量表示（最后）您最终将插入数字的位置。如果没有最后一行，您就不会在正确的位置 'position' 处插入数字（这将导致之后的索引为 1 ）。下面是我的插入排序代码。

def insertionSort(arr):
    length = len(arr)
    for i in range(1, length):
        currNum = arr[i]
        j = i - 1
        while j >= 0 and currNum < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
       arr[j+1] = currNum

   return arr

难以理解插入排序中的一行 (Python 3)

Trouble understanding one line in Insertion Sort (Python 3)

arrays

sorting

algorithm

insertion-sort

python-3.x