Python 中的插入排序

與以前的冒泡排序算法相比，插入排序是一種簡單且更有效的算法。插入排序算法的概念是基於一副牌，我們根據特定的牌排序撲克牌。它有很多優點，但是在數據結構中有很多有效的算法。

打牌的時候，我們互相比較手中的牌。大多數玩家喜歡按升序排序卡片，這樣他們就可以很快看到他們可以使用的組合。

插入排序實現既簡單又容易，因為它通常在編程入門課中講授。是一個原位和穩定算法更有利於接近排序或更少的元素。

插入排序算法沒有那麼快，因為它使用嵌套循環排序元素。

讓我們理解以下術語。

• 原地:原地算法需要額外的空間，而不考慮集合的輸入大小。執行排序後，它會重寫集合中元素的原始內存位置。
• Stable:Stable 是管理初始數組中相等對象的相對順序的術語。

更重要的是，插入排序不需要預先知道數組大小，它一次接收一個元素。

插入排序的好處是，如果我們插入更多要排序的元素，算法會在適當的位置排列，而不執行完整的排序。

對於小(小於 10)尺寸的陣列來說，效率更高。現在，讓我們理解插入排序的概念。

數組實際上溢出到插入排序中的兩個部分-未排序的部分和排序的部分。

排序後的部分包含數組的第一個元素，其他未排序的子部分包含數組的其餘部分。未排序數組中的第一個元素與排序數組進行比較，這樣我們就可以將它放入適當的子數組中。

如果右側值小於左側值，它將通過移動所有元素來插入元素。

它將重複發生，直到將 all 元素插入到正確的位置。

使用插入排序排序數組下面是插入排序的算法。

• 將列表分成兩部分-已排序和未排序。
• 在給定數組上從 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](溫度= 4)

這裡的 4 小於排序子數組中的所有元素，所以我們在第一個索引位置插入它。

[ 4，10， 25，1，5]

我們在排序的子數組中有兩個元素。

現在檢查數字 25。我們已經將其保存到 temp 變量中。 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 then shift 25 to the right side and pass 溫度= 5 。

[ 1，4，10，25 ，25】放入溫度= 5

現在，我們通過簡單地放入臨時值來得到排序的數組。

【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]

說明:

在上面的代碼中，我們創建了一個名為insert _ sort(list 1)的函數。在功能內部-

• 我們定義了從 1 到 len(列表 1)遍歷列表的循環。
• 在 for循環中，在值中賦值 list1 的值，每次循環迭代時，新值將賦給值變量。
• 接下來，我們將列表 1[0…i-1]中大於值的元素移動到它們當前位置之前的一個位置。
• 現在，我們使用 while 來檢查 j 是否大於或等於 0，並且值小於列表的第一個元素。
• 如果兩個條件都成立，那麼將第一個元素移動到第 0 個索引，並減少 j 的值，以此類推。
• 之後，我們調用函數，傳遞列表並打印結果。

Python 提供了使用自定義對象更改算法的靈活性。我們將創建一個自定義類並重新定義實際的比較參數，並嘗試保持與上面相同的代碼。

我們需要重載操作符，以便以不同的方式排序對象。但是，我們可以通過使用λ函數將另一個參數傳遞給insert _ sort()函數。lambda 函數在調用排序方法時很方便。

讓我們理解以下排序自定義對象的示例。

首先，我們定義點類:

# 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 )。使用兩個循環進行迭代。

插入排序的另一個重要優點是:它被稱為 Shell 排序的流行排序算法使用。

插入排序中的輔助空格: O(1)

插入排序是一種簡單而低效的算法，它有很多優點，但也有更高效的算法可用。

在本教程中，我們討論了插入排序的概念及其使用 Python 編程語言的實現。