尝试理解插入排序算法

Question

尝试理解插入排序算法

7

我正在阅读一些关于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

- suffa

1

维基百科上的插入排序文章可能会阐明一些概念点。 - Santa

你可以在这里观看如何操作：http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-1-administrivia-introduction-analysis-of-algorithms-insertion-sort-mergesort/ （可能需要跳过介绍，直接到28:00左右） - steabert

1

它仍然有效，但它不是插入排序... 至少它是一种比可能更慢的实现。 - rocksportrocker

@rocksportrocker，我必须反对说这不是插入排序。它确实是插入排序，只是写得不太好。我猜它源自于翻译不好的C++代码，其中使用了重复的std::swap调用。 - Winston Ewert

@Winston 不是，这是一个冒泡排序。 - Karl Knechtel

显示剩余5条评论

7个回答

6

插入排序算法是通过尝试在数组开头构建一个递增长度的有序列表来实现的。其思想是，从开始时构建一个包含一个元素的有序列表，然后是两个元素的列表，之后是三个元素的列表，以此类推，一旦构建出一个包含 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

任何单元素列表都会自动排序，因此可以保证其安全性。

这实际上是作者在算法方面的优化。如果外层循环从零开始，该算法也可以正常工作，但他们决定从一开始以避免不必要的循环迭代。

希望这可以帮到你！

- templatetypedef

这真的帮了很多，您用通俗易懂的方式将其分解，即使是像我这样的可怜、想成为程序员的人也能理解。 - suffa

2

看一下 while 循环。它以 i 的值为 1 开始，但然后会递减。因此，在最后一行，i 的最小值可以是 0，也就是列表中的第一个元素。如果你从 0 开始，i 将变成 -1，这在 Python 中是有效的，但表示的是最后一个元素。因此，范围必须从 1 开始。

我想提醒您的是，您正在要求插入排序。我不认为您的代码实现了插入排序。看起来更像冒泡排序或类似的东西。

- Achim

1

原因是：

i = j

而 mylist 是这样访问的：

mylist[i - 1]

因此，第一个值是0。如果范围从0开始，它将导致在位置-1访问mylist。

- Sander Rijken

1

但是代码中有一个检查，确保在进行此访问之前i > 0。短路检查应确保如果值超出范围，则永远不会读取该值。 - templatetypedef

1

随后设置i = j，并访问myList[i-1]。因此，j必须j >= 1。

添加：逻辑上将j = 0设置是错误的，因为在循环中访问了myList[j-1]——这只是通过对代码进行静态分析（并知道i=j）而得出的结论。即使由于while i > 0而不能在运行时发生，它也是没有意义的。如果代码中出现表达式myList[j-1]，那么它肯定是j >= 1。

- Jiri Kriz

2

但是代码中有一个检查，确保在进行此访问之前 i > 0。短路检查应该确保如果值超出范围，则永远不会读取该值。 - templatetypedef

1

第j次迭代将第j个元素插入到第j个元素之前的已排序元素中。因此，从j=0开始没有意义。在j=1的情况下，下面的子列表是myList[0:1]，它总是已排序的，并且循环将myList[1]插入到子列表myList[0:2]中。

- rocksportrocker

1

看看动画演示的插入排序这里

- Y.A.P.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Winston Ewert · Accepted Answer

让我来解释一下。

首先考虑一个列表，它是“几乎”有序的。也就是说，前面几个元素已经排序好了，但最后一个元素没有排序。因此它看起来像这样：

[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, 8, 4, 9, 3, 6]

然后我们对前三个元素进行排序

 [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