Python 中的插入排序演算法
- 在 Python 中執行插入排序的步驟
- Python 中的插入排序演算法
- Python 中插入排序的實現
- Python 中插入排序演算法的複雜度
- Python 中插入排序的特點
- Python 中的二進位制插入排序
插入排序演算法的機制就像撲克牌。最初，我們拿第一張卡片並假設它已經排序。
因此，剩餘的卡片是未排序的列表。然後，我們將一張一張地從這個未排序的列表中挑選卡片，並將它們與排序列表中的卡片進行比較。
這樣，我們就可以為卡片找到合適的位置並相應地放置它。重複這個過程為我們提供了分類的卡片包。
插入排序也以這種方式工作。顧名思義，我們在插入元素的同時進行比較。
在 Python 中執行插入排序的步驟
讓我們取一個包含這些元素的未排序陣列：
15, 11, 17, 3, 5
我們採用已經按約定排序的第一個元素。
`15`, 11, 17, 3, 5
我們將從第二個元素到最後一個元素迴圈遍歷 i = 1 到 i= 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 中。
然後，我們使用一個變數來儲存最後一個元素的索引值。這樣，我們可以使用 t 和 key_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 中的實現。
插入排序對於少量元素的排序是有效的，但是對於大集合我們應該使用其他演算法，例如合併排序和快速排序。該演算法的簡單性使其脫穎而出。