插入排序的基本思想:
每步將一個待排序的紀錄,按其關鍵碼值的大小插入前面已經排序的文件中適當位置上,直到全部插入完為止。
例:
arr = [49,38,04,97,76,13,27,49,55,65],從第2個數為關鍵值,向前比較,如前一個數大,進行交換,
arr = [38,49,04,97,76,13,27,49,55,65],然後從第3個數字為關鍵值,向前比較,前大則交換,
arr = [38,04,49,97,76,13,27,49,55,65],再繼續,arr = [04,38,49,97,76,13,27,49,55,65]
備註:依序向前比較時,因為前面的陣列是有序的,所以當前一個數小於或等於key值時,可以跳出這個向前比較的循環,演算法的速度有明顯提升。
程式碼:
Python程式碼
def insert_sort(lists): #插入排序 count = len(lists) for i in range(1,count):#从第2个数起遍历 key = lists[i] j = i - 1 while j >= 0: if lists[j] > key: lists[j+1], lists[j] = lists[j], key else: break #当前一个数小于或等于key时,跳出循环 j -= 1 return lists