## 插入排序 插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。 ## 插入排序分析   ~~~ def insert_sort(alist): # 從第二個位置，即下標為1的元素開始向前插入 for i in range(1, len(alist)): # 從第i個元素開始向前比較，如果小于前一個元素，交換位置 for j in range(i, 0, -1): if alist[j] < alist[j-1]: alist[j], alist[j-1] = alist[j-1], alist[j] alist = [54,26,93,17,77,31,44,55,20] insert_sort(alist) print(alist) ~~~ ## 時間復雜度 * 最優時間復雜度：O(n) （升序排列，序列已經處于升序狀態） * 最壞時間復雜度：O(n2) * 穩定性：穩定 ## 插入排序演示