插入排序法 - 使用Python(Insertion Sort)
插入排序法 - 使用Python
插入排序法的原理是，從未排序的數列裡，每次取一個值並逐一和已排序的數列進行比較，並插入到已排序的數列中，適合的位置。這樣說有點抽象，下面直接用每個步驟插入排序法做的事情來讓大家瞭解。
原始數列 = [6, 5, 4, 3, 2, 1] 刷紫色是未排序的值，刷紅色是本次要比較的值。
第 1 次要排序的數列 = [6, 5, 4, 3, 2, 1] ， 欲比較的值 = 6
第 2 次要排序的數列 = [6, 5, 4, 3, 2, 1] ， 欲比較的值 = 5
[6, 6, 4, 3, 2, 1] ← 最後一次比較，下一步則將 5 插入 6 之前
第 3 次要排序的數列 = [5, 6, 4, 3, 2, 1] ， 欲比較的值 = 4
[5, 6, 6, 3, 2, 1]
[5, 5, 6, 3, 2, 1] ← 最後一次比較，下一步則將 4 插入 5 之前
第 4 次要排序的數列 = [4, 5, 6, 3, 2, 1] ， 欲比較的值 = 3
[4, 5, 6, 6, 2, 1]
[4, 5, 5, 6, 2, 1]
[4, 4, 5, 6, 2, 1] ← 最後一次比較，下一步則將 3 插入 4 之前
第 5 次要排序的數列 = [3, 4, 5, 6, 2, 1] ， 欲比較的值 = 2
[3, 4, 5, 6, 6, 1]
[3, 4, 5, 5, 6, 1]
[3, 4, 4, 5, 6, 1]
[3, 3, 4, 5, 6, 1] ← 最後一次比較，下一步則將 2 插入 3 之前
第 6 次要排序的數列 = [2, 3, 4, 5, 6, 1] ， 欲比較的值 = 1
[2, 3, 4, 5, 6, 6]
[2, 3, 4, 5, 5, 6]
[2, 3, 4, 4, 5, 6]
[2, 3, 3, 4, 5, 6]
[2, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6] ← 插入排序法執行完畢，已完成排序
下面附上插入排序法的範例程式(使用Python撰寫)
import math
import random
# 首先亂數產出一組List
sampleList = []
s = 0
while s < 9:
tempRandNum = random.randint(0,100)
sampleList.append(tempRandNum)
s = s + 1
# 印出原始List
print(sampleList)
# 建立插入排序法的Function
def insertSortExample(sourceList):
listLength = len(sourceList)
i = 0
# 從第一個值開始取
while i < listLength:
# 先將要比較的值暫存起來(以下稱它暫存值)
tempNum = sourceList[i]
j = i - 1
# 將暫存值逐一和前面的值做比較，如果小於前面的值則將前面的直往後放
while j >= 0 and tempNum < sourceList[j]:
sourceList[j+1] = sourceList[j]
j = j - 1
# 比較完後，將暫存值插入到適合的位置
sourceList[j+1] = tempNum
i = i + 1
return sourceList
# 列印出執行結果
print(insertSortExample(sampleList))
如果覺得對你有幫助的話. 請幫小弟按個讚吧～
資料結構相關文章：
