我是一名新的数据科学学生，我正在尝试了解插入排序算法中到底发生了什么。
谁能告诉我一步一步发生了什么？将不胜感激。
下面是我写的一些冗长的代码，因此我希望可以更好地理解正在发生的事情，但无济于事。
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("nn")
print("=================== END =====================")
InsertionSort(A)
print("A (not-sorted): ", B)
print("A (sorted): ", A)
我不明白它是如何切换数字的。
插入排序的工作原理是查看数组中的每个元素并将其移动到数组的开头，直到它小于到目前为止看到的所有元素。
为此，外部循环会考虑数组中的每个元素(跳过元素0因为没有什么可以与之比较的，并且您不想IndexError)。内部循环从当前i索引开始向左滑动元素，将其与数组中j-1的每个先前元素进行比较，直到对到目前为止看到的数组部分进行排序。
调试输出过于依赖文本和数字，而不是数组的视觉对象，而这正是查看算法运行情况所需的全部内容。我还建议使用稍大的数组大小。
顺便说一句，我建议坚持使用Pythoncamel_case命名约定。
如果您使用此代码并逐步浏览输出，我想您将看到发生了什么：
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]
^---
与气泡排序不同，插入排序不仅仅是交换数字(概念上)。
首先，它将当前索引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。
该函数对给定数组进行排序。首先，它从第二个元素开始迭代数组的元素：
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 循环。希望这有所帮助。