Python中的插入排序

插入排序是一种简单且比之前的冒泡排序算法更有效的算法。插入排序算法的概念基于一副扑克牌，我们根据某张牌对扑克牌进行排序。它有许多优点，但在数据结构中存在许多更高效的算法。

在玩扑克牌时，我们会比较手中的牌。大多数玩家喜欢按升序对牌进行排序，以便他们可以快速看到自己有哪些组合。

插入排序的实现简单易懂，因为它通常在初学者编程课程中教授。它是一种原地且稳定的算法，对于接近排序或元素较少的列表更有益。

插入排序算法并非非常快，因为它使用嵌套循环来排序元素。

让我们理解以下术语。

原地和稳定是什么意思？

• 原地：原地算法需要的额外空间不考虑集合的输入大小。执行排序后，它会重写集合中元素的原始内存位置。
• 稳定：稳定是指一种管理初始数组中相等对象的相对顺序的术语。

更重要的是，插入排序不需要提前知道数组的大小，并且它一次接收一个元素。

插入排序的优点是，如果我们插入更多要排序的元素，算法会在不进行完整排序的情况下将它们安排到正确的位置。

对于小型（小于 10）数组，它更有效。现在，让我们理解插入排序的概念。

插入排序的概念

在插入排序中，数组被虚拟地分成两部分 -未排序部分和已排序部分。

已排序部分包含数组的第一个元素，而其他未排序子部分包含数组的其余部分。将未排序数组中的第一个元素与已排序数组进行比较，以便我们可以将其放入适当的子数组中。

它专注于通过移动所有元素来插入元素，如果右侧的值小于左侧的值。

这将重复发生，直到所有元素都插入到正确的位置。

要使用插入排序对数组进行排序，以下是插入排序的算法。

• 将列表分为两部分 - 已排序和未排序。
• 遍历给定数组中的 arr[1] 到 arr[n]。
• 比较当前元素与下一个元素。
• 如果当前元素小于下一个元素，则与前面的元素进行比较，将较大的元素向上移动一个位置，为交换的元素腾出空间。

让我们理解下面的例子。

在下面的数组中，我们将考虑已排序数组中的第一个元素。

[10, 4, 25, 1, 5]

将10添加到已排序子数组的第一步

[10, 4, 25, 1, 5]

现在我们从未排序数组中取出第一个元素 - 4。我们将此值存储在一个名为temp的新变量中。现在，我们可以看到 10>4，所以我们将 10 移到右边，覆盖了之前存储的 4。

[10, 10, 25, 1, 5] (temp = 4)

由于 4 小于已排序子数组中的所有元素，因此我们将其插入到第一个索引位置。

[4, 10, 25, 1, 5]

我们已排序子数组中有两个元素。

现在检查数字 25。我们已将其保存在temp 变量中。25> 10 并且 25> 4，所以我们将其放在第三个位置并添加到已排序子数组中。

[4, 10, 25, 1, 5]

再次检查数字 1。我们将它保存在temp 中。1 小于 25。它会覆盖 25。

[4, 10, 25, 25, 5] 10>1，所以它再次覆盖

[4, 25, 10, 25, 5]

[25, 4, 10, 25, 5] 4>1，现在放入 temp = 1 的值

[1, 4, 10, 25, 5]

现在，我们已排序子数组中有 4 个元素。5<25，所以将 25 移到右侧，并将temp = 5移到左侧。

[1, 4, 10, 25, 25] 放入 temp = 5

现在，通过简单地放入 temp 值，我们得到了排序后的数组。

[1, 4, 5, 10, 25]

给定的数组已排序。

实施

插入的实现相对容易。我们将使用 Python 整数数组来实现。让我们理解以下示例 -

Python 程序

输出

The unsorted list is: [10, 5, 13, 8, 2]
The sorted list1 is: [2, 5, 8, 10, 13]

说明

在上面的代码中，我们创建了一个名为insertion_sort(list1)的函数。在该函数内 -

• 我们定义了一个 for 循环来遍历从 1 到len(list1)的列表。
• 在 for 循环中，将 list1 的值赋给value。每次循环迭代时，都会将新值赋给 value 变量。
• 接下来，我们将 list1[0…i-1] 中大于value的元素移动到其当前位置的前一个位置。
• 现在，我们使用 while 循环检查 j 是否大于或等于 0，以及value是否小于列表的第一个元素。
• 如果两个条件都为真，则将第一个元素移动到第 0 个索引，并减小 j 的值，依此类推。
• 之后，我们调用函数并传入列表，然后打印结果。

排序自定义对象

Python 提供了使用自定义对象更改算法的灵活性。我们将创建一个自定义类并重新定义实际的比较参数，并尝试保持与上述代码相同的代码。

我们需要重载运算符才能以不同的方式对对象进行排序。但是，我们可以通过使用lambda函数向insertion_sort()函数传递另一个参数。调用排序方法时，lambda 函数非常方便。

让我们理解以下排序自定义对象的示例。

首先，我们定义Point类

Python 程序

输出

The points are in the sorted order
(2,3)
(3,1)
(4,4)
(5,2)
(8,0)

使用上述代码，我们可以对坐标点进行排序。它可以适用于任何类型的列表。

插入排序中的时间复杂度

插入排序是一种慢速算法；有时，对于大型数据集来说，它似乎太慢了。但是，对于小型列表或数组，它是有效的。

插入排序的时间复杂度是 - O(n²)。它使用两个循环进行迭代。

插入排序的另一个重要优点是；它被一种流行的排序算法Shell sort使用。

插入排序的辅助空间：O(1)

结论

插入排序是一种简单但效率不高的算法，它有很多优点，但也有更有效的算法。

在本教程中，我们讨论了插入排序的概念及其使用 Python 编程语言的实现。