尝试理解插入排序算法

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

看看这个 while 循环。它开始时 i 的值是 1，但之后 i 会被减小。所以在最后一行，i 的最小值可能是 0，这代表列表中的第一个元素。如果你从 0 开始，i 会变成 -1，在 Python 中这是有效的，但这意味着你指向的是最后一个元素。因此，范围必须从 1 开始。

我想提一下，你在问插入排序。我觉得你的代码并没有实现插入排序，看起来更像是冒泡排序或者其他什么的。

Answer 2

插入排序算法的工作原理是从数组的开头开始，逐步建立一个长度不断增加的已排序列表。简单来说，就是先把一个元素的列表排好序，然后再加一个元素，接着再加一个，依此类推。当你建立了一个包含n个元素的已排序列表时，整个数组就算排好了。

比如，给定这个数组：

3  1  4

我们可以把它分成一个零元素的已排序列表和一个三元素的未排序列表：

| 3  1  4

现在，我们把3加到已排序列表中。因为这个列表现在只有一个元素，所以它自然是排好序的：

3 | 1  4

接下来，我们想把1加到已排序列表中。如果我们直接把1加到列表的末尾，就变成这样：

3 1 | 4

那么这个已排序列表就不再是排好序的了。为了修正这个问题，插入排序的内部循环会不断地把1和它前面的元素交换，直到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

这样做是安全的，因为任何一个元素的列表都是自动排好序的。

这实际上是作者对算法的一种优化。如果外部循环从零开始，算法也能正常工作，但他们选择从一开始，以避免不必要的循环。

希望这对你有帮助！

Answer 3

让我来简单解释一下这个问题。

首先，想象一下一个列表。这个列表“几乎”是排好序的。也就是说，前面的几个元素是有序的，但最后一个元素却不在正确的位置。所以它看起来像这样：

[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] # 错误！！

在这个时候，出现了问题。我们尝试检查key < mylist[i-1]，但当我们到达列表的开头时，i = 0，这样就检查到了列表的末尾。但此时我们应该停止向左移动……

如果我们到达了列表的开头，就不能再把我们的基准/key往左移动了，所以我们应该停止。我们更新我们的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个元素：

 [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