一、概念及原理

插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。

二、插入排序過程

如下圖所示，插入排序的實現思路顧名思義，就是不斷地在一個已經是有序的數組中，尋找合適位置并插入新元素。

三、具體實現步驟為:

首先我們把整個數組拆分為有序區間和未排序區間，有序區間在插入排序一開始只有一個元素，就是數組的第一個元素。

接在有序區間之后的一個元素就是準備插入的元素，在圖中就是標為綠色的元素，在有序區間內尋找位置并插入。

其尋找邏輯為：從后往前依次進行比較，如果待插入元素大于當前元素，則將待插入元素插入到當前元素的后一位，如果待插入元素小于當前元素，則將當前元素后移一位。不斷重復該過程直至到數組的最后一位

四、具體實現的python代碼為:

def insertion_sort(num_list):length = len(num_list)if length <= 1:return num_listfor i in range(1, length):j = i-1 # 表示已排好序的最大索引value = num_list[i] # 未排序列表的第一個元素while j >= 0:# 如果已排序的最后一個元素 < 當前未排序的元素值if num_list[j] < value:# 把當前未排序的元素值插入到已排序元素的最后面 退出循環num_list[j+1] = valuebreakelse:# 把已排序好元素倒敘向后移動 直到符合插入條件num_list[j+1] = num_list[j]# 如果當前被插入的元素一直未找到比它小的元素 則把當前元素放到首位if j == 0:num_list[j] = value# 倒敘向后移動j -= 1return aif __name__ == '__main__':a = [1, 3, 4, 2, 6, 9, 12, 3, 22]insertion_sort(a)print(a)

五、時間復雜度和空間復雜度

• 最好情況的時間復雜度為O(n) 示例: [1, 2, 3, 4, 5]
• 最壞情況的時間復雜度為O(n2) 示例: [5, 4, 3, 2, 1]
• 平均情況的時間復雜度為O(n2),具體分析過程可以參考上篇的冒泡排序

空間復雜度為O(1)

是否為原地排序: 是

是否穩定: 是

總結

以上是生活随笔為你收集整理的python 插入排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。