Python 中的插入排序演算法

Shikha Chaudhary 2023年1月30日 2022年5月17日
  1. 在 Python 中執行插入排序的步驟
  2. Python 中的插入排序演算法
  3. Python 中插入排序的實現
  4. Python 中插入排序演算法的複雜度
  5. Python 中插入排序的特點
  6. Python 中的二進位制插入排序
Python 中的插入排序演算法

插入排序演算法的機制就像撲克牌。最初,我們拿第一張卡片並假設它已經排序。

因此,剩餘的卡片是未排序的列表。然後,我們將一張一張地從這個未排序的列表中挑選卡片,並將它們與排序列表中的卡片進行比較。

這樣,我們就可以為卡片找到合適的位置並相應地放置它。重複這個過程為我們提供了分類的卡片包。

插入排序也以這種方式工作。顧名思義,我們在插入元素的同時進行比較。

在 Python 中執行插入排序的步驟

讓我們取一個包含這些元素的未排序陣列:

15, 11, 17, 3, 5

我們採用已經按約定排序的第一個元素。

`15`, 11, 17, 3, 5

我們將從第二個元素到最後一個元素迴圈遍歷 i = 1i= 4。當 i =1 時,我們將 11 與它的前輩進行比較。由於 11 小於 15,我們移動 15 並在其前面插入 11。

`11`, `15`, 17, 3, 5

對於 i = 2,我們將 17 與其前身進行比較。這一次,因為 17 大於 11 和 15,所以它在 15 之後。

`11`, `15`, `17`, 3, 5

對於 i = 3,我們將 3 與其前任進行比較。3 現在將移至開頭。

`3`, `11`, `15`, `17`, 5

對於 i = 4,我們將 5 與其前任進行比較。5 將放置在 3 之後和 11 之前。

`3`, `5`, `11`, `15`, `17`

這就是我們在 python 中使用插入排序獲得排序陣列的方式。

Python 中的插入排序演算法

按照慣例,我們假設第一個元素已經在列表中排序。列表的其餘部分被認為是未排序的。

之後,我們將通過保持列表中已排序部分的順序,開始將未排序部分的元素插入到已排序部分。我們將使用以下步驟。

  • 從未排序的列表中選擇下一個元素並將其標記為 key
  • 選擇 key 並將其與排序列表中存在的所有元素進行比較。
  • 如果 key 元素大於排序陣列中的元素,則移動到列表中的下一個元素。否則,將列表中較小的元素向左移動。
  • 在排序列表中的正確位置插入 key,以保持排序列表中的順序。
  • 重複上述步驟,直到整個列表被排序。

Python 中插入排序的實現

下面是用 Python 語言實現插入排序的程式碼。

#Code in Python

#Function that performs Insertion sort
def Insertion_sort(arr):

    #Loop till the last element starting from the second one
    for i in range(1, len(arr)):
        
        key_ele = arr[i]

        #set the position of elements based on their value
        t = i-1
        while t >= 0 and key_ele < arr[t]:
            arr[t + 1] = arr[t]
            t -= 1
        arr[t + 1] = key_ele
        

arr = [23, 45, 22, 6, 11]
Insertion_sort(arr)
for i in range(len(arr)):
    print("% d" % arr[i])

輸出:

6
11
22
23
45

我們首先定義一個函式 Insertion_sort()。我們在這個函式中應用排序邏輯。

我們從第二項遍歷陣列,並將鍵與已排序的元素進行比較。在每次迭代中,我們將列表中的元素值儲存在另一個變數 key_ele 中。

然後,我們使用一個變數來儲存最後一個元素的索引值。這樣,我們可以使用 tkey_ele 的值來進行比較。

根據鍵元素的值,我們移動元素並將鍵放置在排序列表中。

在函式定義中,我們宣告瞭一個陣列。在 Python 中,我們稱其為列表

然後,我們呼叫 insertion_sort 函式。我們將列表作為引數傳遞給此函式。

該函式在排序後返回列表。最後,我們可以使用 for 迴圈來列印排序列表。

Python 中插入排序演算法的複雜度

時間複雜度

最佳情況下的複雜度 - 陣列已經排序。因此,不需要排序,最好情況下的複雜度是 O(n)

平均情況下的複雜度 - 陣列既不是升序也不是降序。它是隨機混雜的。平均時間複雜度為 O(n^2)

最壞情況下的複雜度 - 當陣列已經按降序排序時,按升序排列,反轉陣列。最壞情況的時間複雜度是 O(n^2)

空間複雜度

插入排序的空間複雜度是 O(1),因為我們需要一個額外的變數來執行交換操作。

插入排序演算法基於增量正規化,是一種穩定演算法。

Python 中插入排序的特點

  • 該演算法易於實現。
  • 插入排序對於處理一小組元素是有效的。
  • 我們甚至可以在已經排序的資料上使用它。它是一種自適應演算法。

Python 中的二進位制插入排序

二元插入排序是插入排序的臨時版本,它有助於減少在正常插入排序中發生的比較次數。

這個想法很簡單——我們使用二進位制搜尋來找到鍵的正確位置。這樣,我們可以將第 i 次迭代的搜尋複雜度從 O(i) 降低到 O(log i)

然而,最壞情況的複雜度仍然是 O(n^2)

綜上所述,我們瞭解了插入排序及其在 Python 中的實現。

插入排序對於少量元素的排序是有效的,但是對於大集合我們應該使用其他演算法,例如合併排序和快速排序。該演算法的簡單性使其脫穎而出。

相關文章 - Python Sort