Python教程-在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程序

# creating a function for insertion  
def insertion_sort(list1):  
  
        # Outer loop to traverse through 1 to len(list1)  
        for i in range(1, len(list1)):  
  
            value = list1[i]  
  
            # Move elements of list1[0..i-1], that are  
            # greater than value, to one position ahead  
            # of their current position  
            j = i - 1  
            while j >= 0 and value < list1[j]:  
                list1[j + 1] = list1[j]  
                j -= 1  
            list1[j + 1] = value  
        return list1  
            # Driver code to test above  
  
list1 = [10, 5, 13, 8, 2]  
print("The unsorted list is:", list1)  
  
print("The sorted list1 is:", insertion_sort(list1))

输出:

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

解释:

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

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

对自定义对象进行排序

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

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

让我们了解以下示例，该示例演示了如何对自定义对象进行排序。

首先，我们定义Point类：

Python程序

# Creating Point class  
class Point:  
    def __init__(self, a, b):  
        self.a = a  
        self.b = b  
  
    def __str__(self):  
        return str.format("({},{})", self.a, self.b)  
  
def insertion_sort(list1, compare_function):  
    for i in range(1, len(list1)):  
        Value = list1[i]  
        Position = i  
  
        while Position > 0 and compare_function(list1[Position - 1], Value):  
            list1[Position] = list1[Position - 1]  
            PositionPosition = Position - 1  
  
        list1[Position] = Value  
  
U = Point(2,3)  
V = Point(4,4)  
X = Point(3,1)  
Y = Point(8,0)  
Z = Point(5,2)  
  
list1 = [U,V,X,Y,Z]  
  
# We sort by the x coordinate, ascending  
insertion_sort(list1, lambda x, y: x.a > y.a)  
  
for point in list1:  
    print(point)

输出:

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

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

插入排序的时间复杂度

插入排序是一个较慢的算法；有时对于大规模数据集来说，它似乎太慢了。然而，它对于小型列表或数组是有效的。

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

插入排序的另一个重要优点是，它被称为希尔排序的流行排序算法之一。

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

结论

插入排序是一种简单但低效的算法，具有许多优点，但也有更有效的算法可供选择。

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