在Python中的插入排序|极客笔记

在Python中的插入排序

插入排序算法比之前的冒泡排序算法更直观和高效。插入排序算法的概念基于一副纸牌，在这里我们根据特定的牌来排序。它有很多优点，但在数据结构中还有很多更高效的算法可用。

在打牌的过程中，我们将自己的牌与其他人的牌进行比较。大多数玩家喜欢按照升序对牌进行排序，这样他们可以快速看到自己手中有哪些组合。

插入排序的实现非常简单，因为它通常在初学者编程课程中进行教授。它是一种原地和稳定的算法，对于几乎排序或少量元素非常有用。

插入排序算法的速度不是很快，因为它使用嵌套循环来排序元素。

让我们理解一下下面的术语。

什么是原地和稳定的意思

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

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

插入排序的好处是，如果我们插入更多需要排序的元素 – 算法会将它们放在正确的位置而不进行完全排序。

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

插入排序的概念

插入排序将数组在实际上分为两部分 – 一个 未排序的部分 和一个 已排序的部分 。

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

插入排序的重点是通过将所有元素移动到左侧值较小的右侧插入元素。

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

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

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

让我们理解以下示例。

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

[10, 4, 25, 1, 5]

将10添加到有序子数组的步骤1 add 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。我们将其保存在临时变量中。 变量. 25 > 10且25 > 4，然后我们将其放在第三个位置并将其添加到已排序的子数组中。

[ 4, 10, 25, 1, 5]

再次检查数字1。我们将其保存在 临时变量中. 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) 的函数。在函数内部 –

我们使用for循环来遍历列表，从1到 len(list1) 。
在for循环中，将list1的值赋给 value 。每次循环迭代时，新的值将赋给value变量。
接下来，我们将大于 value 的list1[0…i-1]元素移动到它们当前位置的下一个位置。
现在，我们使用while循环来检查是否j大于或等于0，并且 value 小于列表的第一个元素。
如果两个条件都为真，则将第一个元素移动到0 th 索引，并减小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]
            Position = 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(n 2)。它使用两个循环进行迭代。

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

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

结论

插入排序是一种简单而低效的算法，它有许多优点，但也有更高效的算法可用。

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

在Python中的插入排序