插入排序算法。一步一步发生了什么？

Question

我是一名新的数据科学专业学生，我正在尝试了解插入排序算法中到底发生了什么。

任何人都可以逐步告诉我发生了什么吗？将不胜感激。

下面是我写的一段代码，有些冗长，所以我希望能更好地理解发生了什么，但无济于事。

A = [4, 1, 7, 52, 10, 12]
B = [4, 1, 7, 52, 10, 12]


def InsertionSort(A):

    for j in range(1, len(A)):

        print("***************** LOOP", j, "*********************\n")

        key = A[j]
        i = j - 1
        print("i:", i, " |  A[i]:", A[i], " |  key:", key, "\n")
        print("IS i:", i, ">= 0 and", A[i], ">", key, "?", "\n")

        while i >= 0 and A[i] > key:

            print("TRUE:", i, ">= 0 and", A[i], ">", key, "\n")

            A[i + 1] = A[i]  # left cell switches places with right cell
            i = i - 1

        A[i + 1] = key

    print("\n\n")
    print("=================== END =====================")


InsertionSort(A)
print("A (not-sorted): ", B)
print("A (sorted): ", A)

我不明白它是如何切换数字的。

Answer 1

与冒泡排序不同，插入排序不只是交换数字（概念上）。

首先，它将当前索引 j 处的值存储在变量 key.

中

然后它从当前索引 (i = j - 1) 的前一个索引 i 开始，并向后遍历 (i = i - 1) 到开头。对于每个索引，它将值与 key (while i >= 0 and A[i] > key) 进行比较。如果 i 处的值大于 key，它会将值向前移动一个索引 (A[i + 1] = A[i])，直到找到等于或小于 key 的值。当找到这样的值时，key 应该在排序数组中紧随其后，因此它将 key 放在下一个索引 i+1 (A[i + 1] = key) 处。它对所有元素重复相同的过程，结果是排序数组。

这将帮助更多 https://visualgo.net/bn/sorting?slide=8。

Answer 2

函数正在对给定的数组进行排序。首先它遍历数组的元素，从第二个元素开始：

for j in range(1, len(A)):

然后比较元素 j (key) 与元素 j-1 (A[i]):

while i >= 0 and A[i] > key:

如果元素 j-1 比元素 j 大，它需要交换它们，所以它会交换：

A[i + 1] = A[i]

现在它需要检查元素 j-2 是否也是如此，因此需要 while 循环。希望这能有所帮助。

Answer 3

Insertion sort 通过查看数组中的每个元素并将其移向数组的开头，直到它小于目前看到的所有元素。

为此，外层循环会考虑数组中的每个元素（跳过元素 0，因为没有什么可以与之比较，而且您不想 IndexError）。内部循环从当前 i 索引开始向左滑动元素，将其与数组中的每个先前元素 j-1 进行比较，直到到目前为止看到的数组部分被排序。

您的调试输出过于依赖文本和数字，而不是数组的视觉效果，这是查看算法运行所需的全部内容。我还建议使用稍大的数组大小。

顺便说一句，我建议坚持 Python camel_case naming convention.

如果您使用这段代码并逐步查看输出，我想您会明白发生了什么：

a = [7, 3, 6, 9, 4, 5, 8, 0, 1, 2]

def insertion_sort(a):
    for i in range(1, len(a)):
        j = i
        print("moving %d:" % a[j])

        while j > 0 and a[j-1] > a[j]:
            a[j-1], a[j] = a[j], a[j-1]
            j -= 1
            print(a)
            print(" " + "   " * j + "^---")

        print()

print("original: \n" + str(a) + "\n")
insertion_sort(a)

输出：

original: 
[7, 3, 6, 9, 4, 5, 8, 0, 1, 2]

moving 3:
[3, 7, 6, 9, 4, 5, 8, 0, 1, 2]
 ^---       

moving 6:
[3, 6, 7, 9, 4, 5, 8, 0, 1, 2]
    ^---

moving 9:

moving 4:
[3, 6, 7, 4, 9, 5, 8, 0, 1, 2]
          ^---
[3, 6, 4, 7, 9, 5, 8, 0, 1, 2]
       ^---
[3, 4, 6, 7, 9, 5, 8, 0, 1, 2]
    ^---

moving 5:
[3, 4, 6, 7, 5, 9, 8, 0, 1, 2]
             ^---
[3, 4, 6, 5, 7, 9, 8, 0, 1, 2]
          ^---
[3, 4, 5, 6, 7, 9, 8, 0, 1, 2]
       ^---

moving 8:
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
                ^---

moving 0:
[3, 4, 5, 6, 7, 8, 0, 9, 1, 2]
                   ^---
[3, 4, 5, 6, 7, 0, 8, 9, 1, 2]
                ^---
[3, 4, 5, 6, 0, 7, 8, 9, 1, 2]
             ^---
[3, 4, 5, 0, 6, 7, 8, 9, 1, 2]
          ^---
[3, 4, 0, 5, 6, 7, 8, 9, 1, 2]
       ^---
[3, 0, 4, 5, 6, 7, 8, 9, 1, 2]
    ^---
[0, 3, 4, 5, 6, 7, 8, 9, 1, 2]
 ^---

moving 1:
[0, 3, 4, 5, 6, 7, 8, 1, 9, 2]
                      ^---
[0, 3, 4, 5, 6, 7, 1, 8, 9, 2]
                   ^---
[0, 3, 4, 5, 6, 1, 7, 8, 9, 2]
                ^---
[0, 3, 4, 5, 1, 6, 7, 8, 9, 2]
             ^---
[0, 3, 4, 1, 5, 6, 7, 8, 9, 2]
          ^---
[0, 3, 1, 4, 5, 6, 7, 8, 9, 2]
       ^---
[0, 1, 3, 4, 5, 6, 7, 8, 9, 2]
    ^---

moving 2:
[0, 1, 3, 4, 5, 6, 7, 8, 2, 9]
                         ^---
[0, 1, 3, 4, 5, 6, 7, 2, 8, 9]
                      ^---
[0, 1, 3, 4, 5, 6, 2, 7, 8, 9]
                   ^---
[0, 1, 3, 4, 5, 2, 6, 7, 8, 9]
                ^---
[0, 1, 3, 4, 2, 5, 6, 7, 8, 9]
             ^---
[0, 1, 3, 2, 4, 5, 6, 7, 8, 9]
          ^---
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
       ^---

插入排序算法。一步一步发生了什么？

The Insertion Sort algorithm. What's happening step by step?

python

algorithm

insertion-sort