插入排序

插入排序是最简单的排序算法之一，因为它在特定实例中对单个元素进行排序。就性能而言，它不是最好的排序算法，但在实际场景中，它比选择排序和冒泡排序更有效。它是一种直观的排序技术。

让我们考虑一个扑克牌的例子，以便更好地理解插入排序背后的逻辑。

假设我们手里有一副牌，我们想按升序排列这些牌。为了对这些牌进行排序，我们有很多直观的方法。

其中一种方法是，我们最初可以将所有的牌都放在左手，然后我们可以一张接一张地从左手中取牌，然后在右手中构建一个已排序的排列。

假设第一张牌已经排好序，我们将选择下一个未排序的牌。如果发现未排序的牌大于所选牌，我们只需将其放在右侧，否则放在左侧。在这个过程中，左手将是未排序的，右手将是已排序的。

同样，我们将通过将剩余的未排序牌放在正确的位置来对它们进行排序。在每次迭代中，插入算法都会将一个未排序的元素放置在其正确的位置。

算法：插入排序 (A)

插入排序的工作原理

1. 我们将从假设数组的第一个元素已经排序开始。在键内，我们将存储第二个元素。

接下来，我们将把第一个元素与键进行比较，如果发现键小于第一个元素，我们将交换它们的索引或将键放置在第一个索引处。完成此操作后，我们将注意到前两个元素已排序。

2. 现在，我们将移至第三个元素，并将其与左侧元素进行比较。如果它是最小的元素，那么我们将把第三个元素放在第一个索引处。

否则，如果它大于第一个元素且小于第二个元素，那么我们将将其位置与第三个元素互换，并将其放置在第一个元素之后。完成此操作后，我们将以排序的方式排列前三个元素。

3. 同样，我们将对剩余的元素进行排序，并将它们放置在正确的位置。

考虑以下我们将借助插入排序算法排序的未排序数组的示例。

A = (41, 22, 63, 14, 55, 36)

最初，

第 1 次迭代

设置键 = 22

将 a1 与 a0 比较

由于 a0 > a1，互换它们。

第 2 次迭代

设置键 = 63

将 a2 与 a1 和 a0 比较

由于 a2 > a1 > a0，保持数组不变。

第 3 次迭代

设置键 = 14

将 a3 与 a2、a1 和 a0 比较

由于 a3 是左侧所有元素中最小的，将 a3 放在数组的开头。

第 4 次迭代

设置键 = 55

将 a4 与 a3、a2、a1 和 a0 比较。

由于 a4 < a3，互换它们。

第 5 次迭代

设置键 = 36

将 a5 与 a4、a3、a2、a1 和 a0 比较。

由于 a5 < a2，我们将元素放在它们正确的位置。

因此，数组按升序排列，因此不再需要交换。

插入排序的复杂度分析

输入：给定 n 个输入元素。

输出： 对列表进行排序所需的步骤数。

逻辑：如果给定n个元素，那么在第一次传递中，它将进行n-1次比较；在第二次传递中，它将进行n-2次；在第三次传递中，它将进行n-3次，依此类推。因此，可以通过以下方式找到总比较次数：

Output; 
(n-1) + (n-2) + (n-3) + (n-4) + ...... + 1
Sum= 
i.e., O(n2)

因此，插入排序算法的时间复杂度为O(n²)，空间复杂度为O(1)，因为它需要一些额外的内存空间用于键变量以执行交换。

时间复杂度

• 最佳情况复杂度：对于已经排序的数组，插入排序算法的最佳情况时间复杂度为O(n)，因为在这里，只有外循环运行 n 次，而内循环保持不变。
• 平均情况复杂度：插入排序算法的平均情况时间复杂度为O(n²)，当现有元素以混乱的顺序排列时，即既不是升序也不是降序时，就会发生这种情况。
• 最坏情况复杂度：最坏情况时间复杂度也是O(n²)，当我们将数组的升序排列成降序时，就会发生这种情况。
  在这个算法中，每个单独的元素都与其余的元素进行比较，因此对于每个第 n 个元素，将进行 n-1 次比较。

尤其推荐使用插入排序算法，特别是当需要排序的元素很少或数组包含很少的元素时。

空间复杂度

由于使用了额外的变量键，插入排序的空间复杂度为O(1)。

插入排序应用

插入排序算法用于以下情况

• 当数组只包含几个元素时。
• 当要排序的元素很少时。

插入排序的优点

1. 易于实现。
2. 它对小型数据集很有效。
3. 它很稳定（不会改变具有相同键的元素的相对顺序）
4. 它是就地排序（只需要常量数量 O (1) 的额外内存空间）。
5. 它是一种在线算法，可以在接收到列表时对其进行排序。