DSA 插入排序

插入排序

插入排序算法使用数组的一部分来保存已排序的值，而数组的另一部分则保存尚未排序的值。

该算法一次从数组的未排序部分取一个值，并将其放入数组的已排序部分的正确位置，直到数组排序完成。

继续阅读以完全理解插入排序算法及其实现方式。

手动运行

在用编程语言实现插入排序算法之前，让我们手动运行一个短数组，以便了解其原理。

步骤 1：从一个未排序的数组开始。

步骤 2：可以将第一个值视为数组的初始排序部分。如果只有一个值，它肯定是有序的，对吧？

步骤 3：现在，应该将下一个值 12 移到数组排序部分的正确位置。但 12 大于 7，所以它已经在正确的位置上了。

步骤 4：考虑下一个值 9。

步骤 5：现在必须将值 9 移到数组排序部分的正确位置，所以我们要将 9 移到 7 和 12 之间。

步骤 6：下一个值是 11。

步骤 7：我们将其移到数组排序部分的 9 和 12 之间。

步骤 8：最后一个要插入到正确位置的值是 3。

步骤 9：我们将 3 插入到所有其他值的前面，因为它是最小的值。

最后，数组排序完成。

运行下面的模拟以查看上面步骤的动画效果

手动运行：发生了什么？

我们必须了解上面发生了什么，才能完全理解该算法，以便能够用编程语言实现该算法。

第一个值被视为数组的初始排序部分。

必须将第一个值之后的每个值与算法排序部分的值进行比较，以便将其插入到正确的位置。

插入排序算法必须遍历数组 4 次才能对包含 5 个值的数组进行排序，因为我们不需要对第一个值进行排序。

而且，每次算法遍历数组时，数组的剩余未排序部分都会变得更短。

现在，我们将利用学到的知识用编程语言实现插入排序算法。

插入排序实现

要以编程语言实现插入排序算法，我们需要：

1. 一个包含要排序的值的数组。
2. 一个外部循环，用于选择要排序的值。对于包含 \(n\) 个值的数组，此外部循环跳过第一个值，并且必须运行 \(n-1\) 次。
3. 一个内部循环，用于遍历数组的排序部分，以找到插入值的正确位置。如果要排序的值位于索引 \(i\) 处，则数组的排序部分从索引 \(0\) 开始，到索引 \(i-1\) 结束。

生成的代码如下所示

my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)
for i in range(1,n):
    insert_index = i
    current_value = my_array.pop(i)
    for j in range(i-1, -1, -1):
        if my_array[j] > current_value:
            insert_index = j
    my_array.insert(insert_index, current_value)

print("Sorted array:", my_array)

插入排序改进

插入排序可以进一步改进。

上面代码中首先删除一个值，然后将其插入到其他位置的方式很直观。例如，如果你用手里的牌玩插入排序，你就会按这种方式进行。如果低牌被排序到左侧，你拾起一张新的未排序的牌，并将其插入到已排序的其他牌之间的正确位置。

这种编程方式的问题在于，当从数组中删除一个值时，必须将所有在它上面的元素向下移动一个索引位置。

而且，当将删除的值再次插入数组时，还需要执行很多移位操作：所有后面的元素都要向上移动一个位置，为插入的值腾出空间。

这些移位操作可能非常耗时，尤其是对于包含很多元素的数组。

改进的解决方案

我们可以通过只移动必要的来避免大多数移位操作。

在上图中，首先复制第一个值 7，然后将值 11 和 12 向上移动一个位置，最后将值 7 放到值 11 之前的位置。

在这种情况下，移位操作的数量从 12 个减少到 2 个。

此改进在下面的示例中实现。

my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)
for i in range(1,n):
    insert_index = i
    current_value = my_array[i]
    for j in range(i-1, -1, -1):
        if my_array[j] > current_value:
            my_array[j+1] = my_array[j]
            insert_index = j
        else:
            break
    my_array[insert_index] = current_value

print("Sorted array:", my_array)

上面代码中还执行了退出内部循环的操作。这是因为，当我们已经找到当前值的正确位置时，就没有必要继续比较值了。

插入排序时间复杂度

有关时间复杂度的概括性说明，请访问 此页面。

有关插入排序时间复杂度的更详细说明，请访问 此页面。

插入排序对包含 \(n\) 个值的数组进行排序。

平均而言，每个值必须与大约 \(\frac{n}{2}\) 个其他值进行比较，才能找出插入位置。

插入排序必须大约运行 \(n\) 次循环才能将值插入到其正确位置。

我们得到插入排序的时间复杂度为

\[ O( \frac{n}{2} \cdot n) = \underline{\underline{O(n^2)}} \]

插入排序的时间复杂度可以这样显示

使用下面的模拟来查看理论时间复杂度 \(O(n^2)\)（红线）与实际插入排序的操作数量的比较。

对于插入排序，最佳情况、平均情况和最坏情况之间存在很大差异。你可以通过运行上面的不同模拟来查看这一点。

接下来是快速排序。最后，我们将看到一种更快的排序算法！