插入排序算法 (附Python/Java/C/C++程序)

插入排序的工作方式类似于扑克牌的整理。它假设第一张牌已经理顺，然后我们选择一张未理顺的牌。如果选择的未理顺的牌比第一张牌大，它将被放在右边；否则，将被放在左边。同样，所有未理顺的牌都被取出并放到它们确切的位置。

插入排序也采用相同的方法。插入排序背后的思想是，首先它取一个元素并将其遍历已排序的数组。虽然它使用简单，但它不适用于大型数据集，因为插入排序在平均情况和最坏情况下的时间复杂度都是 O(n²)，其中 n 是元素的数量。插入排序效率低于其他排序算法，如堆排序、快速排序和归并排序等。插入排序是一种稳定的排序算法。

让我们看看插入排序的算法。

算法

步骤：

实现插入排序的简单步骤如下：

步骤 1： 如果元素是第一个元素，则假定它已经排序。返回 1。

步骤 2： 选取下一个元素并将其单独存储在一个 key 中。

步骤 3： 现在，将 key 与已排序数组中的所有元素进行比较。

步骤 4： 如果已排序数组中的元素小于当前元素，则移至下一个元素。否则，将数组中较大的元素向右移动。

步骤 5： 插入值。

步骤 6： 重复直到数组排序完成。

插入排序算法的工作原理

现在，让我们看看插入排序算法的工作原理。

为了理解插入排序算法的工作原理，让我们取一个未排序的数组。通过一个例子更容易理解插入排序。

a[] = {24, 2, 11, 6, 3}

初始

我们取第一个元素。数组的第一个元素被假定为已排序。因此，直到第 0 个索引的已排序部分是 [24]。

第一次遍历

当前元素是 2（在第 1 个索引处）。将其与左侧的所有元素进行比较。在这种情况下，元素是 24。由于 2 小于 24，将元素 2 插入到 24 之前。因此，直到第 1 个索引的已排序部分是 [2, 24]。

第二次遍历

现在，当前元素是 11（在第 2 个索引处）。将其与左侧的所有元素进行比较。在这种情况下，元素是 2, 24。由于 11 小于 24 但大于 2，将元素 11 插入到 2 和 24 之间。因此，直到第 2 个索引的已排序部分是 [2, 11, 24]。

第三次遍历

现在，当前元素是 6（在第 3 个索引处）。将其与左侧的所有元素进行比较。在这种情况下，元素是 2, 11 和 24。由于 6 小于 11 但大于 2，将元素 6 插入到 2 和 11 之间。因此，直到第 3 个索引的已排序部分是 [2, 6, 11, 24]。

第四次遍历

现在，当前元素是 3（在第 4 个索引处）。将其与左侧的所有元素进行比较。在这种情况下，元素是 2, 6, 11, 24。由于 3 小于 6 但大于 2，将元素 3 插入到 2 和 6 之间。因此，直到第 4 个索引的已排序部分是 [2, 3, 6, 11, 24]。

正如您在此处看到的，数组已完全排序。

Python/Java/C/C++/C# 中的插入排序实现

• Python
• Java
• C
• C++
• C#

输出

Before sorting array elements are: 
70 15 2 51 60 
After sorting array elements are: 
2 15 51 60 70 

复杂度分析

让我们看看插入排序在最佳情况、平均情况和最坏情况下的时间和空间复杂度。

时间复杂度

最佳情况复杂度： 当不需要排序时发生，即数组已经排序。插入排序的最佳情况时间复杂度是 O(n)。

平均情况复杂度： 当数组元素处于混乱顺序时发生。插入排序的平均情况时间复杂度是 O(n²)。

最坏情况复杂度： 当数组元素需要按相反顺序排序时发生。假设要将数组元素按升序排序，但其元素按降序排列。插入排序的最坏情况时间复杂度是 O(n²)。

空间复杂度

插入排序的空间复杂度是 O(1)。这是因为在插入排序中，交换需要一个额外的变量。

插入排序的应用

插入排序在以下情况下非常有用：

1. 列表较小或接近排序。
2. 稳定性或简单性是重要因素。
3. 由于插入排序适用于较小尺寸的数组，它与其他排序算法（如快速排序和归并排序）一起用于混合排序算法中。当子数组尺寸较小时，插入排序被用于这些递归算法中。例如，TimSort 和 IntroSort 都使用插入排序。

插入排序的优点

1. 易于实现且简单。
2. 它是一种稳定的排序算法。
3. 它适用于接近排序的列表和小型列表。
4. 它是一种原地排序算法，因此节省空间。
5. 自适应的，因为逆序对的数量与交换次数成正比。例如，在已排序的数组中，交换次数为零，因为逆序对的数量也为零。

插入排序的缺点

1. 插入排序对于大型数据集效率低下。
2. 它不如其他更高级的排序算法性能好。

结论

插入排序是一种适度的、稳定的和自适应的排序算法。它适用于小型或几乎排序的数据集。最坏情况时间复杂度使其对于大型数据集效率低下。正如我们已经讨论的，它是一种原地排序，确保最小的内存使用。

总的来说，插入排序在以下场景中很有价值：简单性、稳定性以及处理接近排序的数据很重要。