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

 

   如果覺得對你有幫助的話. 請幫小弟按個讚吧~

資料結構相關文章:

      氣泡排序法 - 使用Python (Bubble Sort)

      資料結構 - Tree 的介紹

      合併排序法 - 使用Python(Merge sort)

文章標籤
創作者介紹
創作者 newaurora 的頭像
newaurora

史丹利愛碎念

newaurora 發表在 痞客邦 留言(0) 人氣()