试图了解插入排序算法

Question

我正在阅读一些关于Python,数据结构以及算法分析和设计的书籍.我想真正理解编码的内部和外部,并成为一个有效的程序员.要求本书澄清是很困难的,因此我对stackoverflow的问题.我真的觉得算法和递归具有挑战性...我在下面发布了一些代码(插入排序),我正在试图理解究竟发生了什么.一般来说,我明白应该发生什么,但我并没有真正了解方法和原因.

从尝试分析Python Idle上的代码片段,我知道:

key (holds variables) = 8, 2, 4, 9, 3, 6

然后:

i (holds the length) = 7 ( 1, 2, 3, 4, 5, 6, 7)

我不知道为什么在第一行使用1:range(1,len(mylist)).任何帮助表示赞赏.

mylist = [8, 2, 4, 9, 3, 6]

for j in range(1,len(mylist)):
    key = mylist[j]
    i = j
    while i > 0 and mylist[i-1] > key:
        mylist[i] = mylist[i - 1]
        i -= 1
        mylist[i] = key

Answer 1

让我试着打破这个.

首先考虑一个清单.它"几乎"排序.也就是说,前几个元素已排序,但最后一个元素未排序.所以它看起来像这样:

[10, 20, 30, 50, 15]

显然,15是在错误的地方.那么我们如何移动呢？

    key = mylist[4]
    mylist[4] = mylist[3]
    mylist[3] = key

这将切换到15和50,所以现在列表看起来像:

[10, 20, 30, 15, 50]

但我们想在一个循环中多次这样做.为此,我们可以做到:

while ???:
    key = mylist[i]
    mylist[i] = mylist[i-1]
    mylist[i-1] = key
    i -= 1

该循环将一次回到一个位置,交换两个元素.每次都会将失序位置移回一个位置.但我们怎么知道何时停止？

让我们再看一下我们的列表以及我们想要做出的动作:

[10, 20, 30, 50, 15]
[10, 20, 30, 15, 50]
[10, 20, 15, 30, 50]
[10, 15, 20, 30, 50]
# stop! we are sorted now!

但是最后一次有什么不同？每当我们将第一个位置移回时,这是因为15小于左边的元素,这意味着它没有排序.如果那不再是真的,我们就应该停止前进.但我们可以轻松应对:

key = mylist[i]
while key < mylist[i-1]:
    mylist[i] = mylist[i-1]
    mylist[i-1] = key
    i -= 1

好的,但如果我们现在尝试对此列表进行排序,则会发生:

[10,20,1] [10,1,20] [1,10,20] #ERROR !!

此时出现了一些不好的事情.我们尝试检查键<mylist [i-1],但是当我们到达开头时,i = 0,这将检查列表的结尾.但是我们应该在此时停止向左移动......

如果我们到达列表的开头,我们就无法进一步移动数据/键,所以我们应该停止.我们更新while循环来处理:

key = mylist[i]
while i > 0 and key < mylist[i-1]:
    mylist[i] = mylist[i-1]
    mylist[i-1] = key
    i -= 1

所以现在我们有了一种对几乎排序的列表进行排序的技术.但是我们如何使用它来整理整个列表呢？我们一次对部分列表进行排序.

 [8, 2, 4, 9, 3, 6]

首先,我们排序前1个元素:

 [8, 2, 4, 9, 3, 6]

然后我们排序前两个元素:

 [2, 8, 4, 9, 3, 6]

然后我们排序前3个元素

 [2, 4, 8, 9, 3, 6]

等等等等

 [2, 4, 8, 9, 3, 6]
 [2, 4, 8, 9, 3, 6]
 [2, 3, 4, 8, 9, 6]
 [2, 3, 4, 6, 8, 9]

但是我们怎么做呢？带有for循环

for j in range(len(mylist)):
    i = j
    key = mylist[i]
    while i > 0 and key < mylist[i-1]:
        mylist[i] = mylist[i-1]
        mylist[i-1] = key
        i -= 1 

但我们可以跳过第一次,因为一个元素的列表显然已经排序.

for j in range(1, len(mylist)):
    i = j
    key = mylist[i]
    while i > 0 and key < mylist[i-1]:
        mylist[i] = mylist[i-1]
        mylist[i-1] = key
        i -= 1 

一些没有任何区别的小改动将我们带回原始代码

for j in range(1, len(mylist)):
    key = mylist[j]
    i = j
    while i > 0 and key < mylist[i-1]:
        mylist[i] = mylist[i-1]
        i -= 1 
        mylist[i] = key

Answer 2

插入排序算法的工作原理是尝试在数组的开头建立一个增加长度的排序列表.我们的想法是,如果你从开头构建一个单元素的排序列表开始,然后是一个双元素列表,然后是一个三元素列表等,一旦你构建了一个n元素排序列表,你已经整理了整个数组并完成了.

例如,给定数组

3  1  4

我们可以将它拆分为零元素排序列表和三元素未排序列表:

| 3  1  4

现在,我们在排序列表中添加3.由于该列表现在只有一个元素长,它会自动排序:

3 | 1  4

现在,我们要在排序列表中添加1.如果我们只是在列表的末尾添加1,如下所示:

3 1 | 4

然后排序列表不再排序.为了解决这个问题,插入排序代码的内部循环通过将1与之前的元素连续交换直到它处于正确的位置来工作.在我们的例子中,我们交换1和3:

1 3 | 4

由于1现在位于数组的开头,因此我们不再需要移动它.这就是内循环运行的原因i > 0; 一旦新的元素(指数i)是在阵列的开始,还有之前没有任何可以是任何更大.

最后,我们通过在排序列表中添加4来更新数组.由于它处于排序位置,我们完成了:

1 3 4

我们的数组现在按排序顺序排列.

现在,问你原来的问题:为什么外环从1开始？这是一个可爱的优化技巧.这个想法是任何单元素数组必须自动排序.这意味着算法可以从数组的第一个元素是单元素排序列表开始.例如,给定数组

2  7  1  8

插入排序算法可以尝试像这样拆分这个数组,在前面放置一个空的排序列表:

| 2  7  1  8

但稍微快一点的选择是将列表拆分为:

2 | 7  1  8

这保证是安全的,因为任何单元素列表都会自动排序.

这实际上是作者对算法的优化.如果外部循环从零开始,该算法将完美地工作,但是他们只是决定在一个处启动它以避免不必要的循环迭代.

希望这可以帮助!