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

问题描述 投票:-2回答:3

我是一名新的数据科学专业的学生,​​我正在努力了解插入排序算法中究竟发生了什么。

谁能告诉我一步一步发生了什么?非常感谢。

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

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)

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

python algorithm insertion-sort
3个回答
0
投票

与冒泡排序不同,插入排序不仅仅是交换数字(概念上)。

首先,它将当前索引j中的值存储在变量key中。

然后它从当前指数(i)的前一个指数i = j - 1开始,然后向后(i = i - 1)向前移动。对于每个指数,它将值与keywhile i >= 0 and A[i] > key)进行比较。如果i的值大于key,则将值向前移动一个指数(A[i + 1] = A[i]),直到找到等于或低于key的值。当找到这样的值时,key应该在排序数组之后,所以它将key放在下一个索引i+1A[i + 1] = key)。它为所有元素重复相同的过程,结果是排序数组。

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


1
投票

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]
       ^---

0
投票

该函数正在对给定的数组进行排序。首先,它从第二个元素开始迭代数组的元素:

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

然后它将元素jkey)与元素j-1A[i])进行比较:

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

如果元素j-1大于元素j它需要交换它们,所以它进行交换:

A[i + 1] = A[i]

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

© www.soinside.com 2019 - 2024. All rights reserved.