插入排序是一种简单的排序算法，它将未排序的元素依次插入到已排序的部分中。该算法通过构建有序子列表来一步步地将元素插入到正确的位置，直到整个列表被排序。 以下是插入排序的工作原理示例： 1. 创建一个空的有序列表（初始状态下只有一个元素）。 2. 从未排序列表中选择第一个元素，并将

当涉及到对数据数组进行排序时，有许多可以使用的排序算法。其中一种最简单的算法是插入排序，由于其相对简单和直观的特性。请继续阅读，了解插入排序到底是什么，它是如何实现的，以及它可以用来做什么，附带一个示例。

什么是插入排序？

插入排序是一种排序算法，是一种可以用来对数组进行排序的方法之一。它的工作原理并不太复杂，可以大致类比于如何对一副牌进行排序。

在这种情况下，我们首先假设牌堆中的第一张牌已经排好序了。然后，我们选择一张未排序的牌并对其进行排序。这是通过将其与第一张牌进行比较来完成的。如果选中的牌大于已排序的牌，则将其放在第一张牌的右边。如果所讨论的牌小于已排序的牌，则将其放在第一张牌的左边。

这个过程一直进行，直到所有的未排序的牌都放置在正确的位置上。插入排序通过相同类型的迭代过程对每个未排序的数据值进行排序。

由于插入排序是一个非常简单的算法，它最适用于相对较小的数据集，以及那些已经有些排序的数据集。从这个角度来看，它被称为一种自适应和高效的算法。接下来，我们将详细介绍插入排序的工作原理。

插入排序的算法

插入排序的方法可以用以下伪代码简明地表示：

插入排序(数组)
  将第一个元素标记为已排序
  对于每个未排序的元素x
    '提取'元素x
    对于j从最后一个已排序的索引到0
      如果当前元素j > x
        将已排序的元素向右移动1位
    中断循环，在此处插入x
结束插入排序

简单来说，这意味着第一个元素被假设为已排序。每个后续的元素都与第一个元素进行比较。如果它比已排序的元素小，则将其移动到第一个(0位置)。如果它比已排序的元素大，则向右移动一位。迭代继续，直到所有元素都被排序。

插入排序的内部工作原理

现在我们已经介绍了插入排序的工作原理和理论，是时候用一个合适的数组来说明这个过程了。如果我们考虑以下数据集：

我们可以假设第一个元素10已经被排好序了。之后，我们将第二个元素14单独存储起来。将14与10进行比较，我们可以看到14大于10，所以它保持在第二个位置上。这是第一次迭代，也称为第一遍。第一个元素10被存储在一个子数组中。

绿色 = 已排序的数组

对于第二次遍历，我们移动到第三个元素，即5。这与前面的元素进行比较。我们可以看出它小于前一个元素14，所以它与14交换位置。

然后算法将其与排序子数组中的元素进行比较。5也小于10，所以它被移到子数组的开头。现在排序数组有2个元素-5和10。

现在，我们进行第三次遍历。在这种情况下，选择的元素是7。这比14小，所以它向左移动一个位置并进入排序数组。然而，这不是正确的位置，因为7比10小但比5大。因此，它又向左移动了一个位置。

对于第四次遍历，我们看的是第四个元素，即14。这已经排序好了，所以现在排序数组包括5、7、10和14。

最终结果

最后，对于第五次遍历，我们取第五个元素1。这显然比14小，因此位置交换。它也比10小，所以位置再次交换。这继续进行两次，因为1是数组中最小的元素。因此，我们最终得到排序好的数组如下：

插入排序的实现

插入排序可以使用各种编程语言实现，从c、c#、c++到java、python、php和javascript。为了说明，我们将使用python进行工作。整个过程可以用以下代码表示：

def insertionsort(arr):
if (n := len(arr)) <= 1:
return
for i in range(1, n):
key = arr[i]
j = i-1
while j >=0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
arr = [10, 14, 5, 7, 1]
insertionsort(arr)
print(arr)

首先，我们将插入排序定义为数组(arr)的函数。然后，我们说如果数组的长度小于等于1，就返回数组。接下来，我们将数组的第i个位置的元素定义为关键字。

我们对计算进行了限制，只有当j大于等于索引0时才对其进行操作。根据j = i – 1，j被视为我们正在查看的任何项的左侧的值。如果它的值大于密钥，则将其位置向右移动。

最后一行arr[j+1] = key，表示此j值右侧的值成为新的密钥。因此，其余数字将根据需要进行交换。然后，从头开始，这个过程一直进行下去，直到所有数字都正确排序。

python中的插入排序：实现

让我们看看在spyder环境中如何实现此功能。我们将使用之前的相同数组来清楚地说明这一点。请参阅下面的实现代码：

在python中实现插入排序。

©jingzhengli.com

一个重要的要点是在使用python时缩进非常重要。如果缩进使用不正确，您会收到类似下面的错误消息。

收到错误消息。

©jingzhengli.com

插入排序的最佳和最差使用情况

尽管插入排序用途广泛，但与任何算法一样，它都有最佳和最差的情况。这主要取决于时间和空间复杂度。

插入排序的时间复杂度

每种情况的时间复杂度可以用下表描述：

可以看到，在最佳情况下，时间复杂度等于o(n)。这意味着不需要排序，因为数组已经排序好了。因为算法必须在确定数组已排序之前检查每个值，所以时间复杂度是线性的。也就是说，复杂度与输入大小成线性比例。

然而，在平均和最坏的情况下，复杂性等于o(n2)。平均情况是数组中的元素混乱，既不升序也不降序。在最坏的情况下，元素需要以相反的顺序排序。

这是因为它们已经按升序或降序排序，并且您需要相反的顺序。这种类型的复杂性被称为二次时间复杂性，因为它依赖于n2。例如，如果输入的大小为4，那么操作次数将为16。

插入排序的空间复杂度

另一种复杂性是空间复杂性。这指的是运行算法所需的内存空间量。复杂度为o(1)意味着所需的内存量是恒定的，与输入大小无关。

这在插入排序的情况下是正确的，因为每次操作只使用一个临时变量。换句话说，一次只有一个值被排序，所以内存使用是恒定的。

应该注意的是，插入排序被认为是一种稳定的算法，这意味着相等值的元素的相对顺序保持不变。这在需要保持特定元素的顺序或需要对已部分排序的数组进行排序时非常有用。这是因为如果元素与密钥相等，则不会与密钥交换。

总结

我们已经讲解了插入排序的定义以及何时适合使用插入排序。此外，我们还考虑了它的时间和空间复杂度，并展示了它在python中的代码表示和实现。如果你想要对一个相对较小的数组进行排序，特别是其中一些元素已经有序，插入排序是最好的方法之一。