我是一名新的数据科学专业的学生,我正在努力了解插入排序算法中究竟发生了什么。
谁能告诉我一步一步发生了什么?非常感谢。
下面是我用一些冗长的代码编写的代码,所以我希望能够理解发生了什么更好但无济于事。
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)
我不明白它是如何切换数字的。
与冒泡排序不同,插入排序不仅仅是交换数字(概念上)。
首先,它将当前索引j
中的值存储在变量key
中。
然后它从当前指数(i
)的前一个指数i = j - 1
开始,然后向后(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
)。它为所有元素重复相同的过程,结果是排序数组。
Insertion sort通过查看数组中的每个元素并将其移向数组的开头来工作,直到它比目前为止看到的所有元素都小。
要做到这一点,外部循环考虑数组中的每个元素(跳过元素0
,因为没有什么可以与它进行比较,你不想要IndexError
)。内部循环从当前的i
索引向左滑动元素,将其与数组中的每个先前元素j-1
进行比较,直到到目前为止看到的数组部分被排序。
您的调试输出过于依赖文本和数字,而不是数组的可视化,这是查看算法运行所需的全部内容。我还建议使用稍大的数组大小。
顺便说一句,我建议坚持Python camel_case
naming convention。
玩这个repl并逐步完成输出,我想你会看到发生了什么:
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]
^---
该函数正在对给定的数组进行排序。首先,它从第二个元素开始迭代数组的元素:
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循环。希望这个对你有帮助。