插入排序法 - 使用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