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

 

Python相關文章:

python import 路徑說明

python tuple資料讀取、合併、查詢

python使用matplotlib畫折線圖(Line chart)

Python - list的讀取、增加、刪除、修改方法

python dict資料讀取、新增、修改

python使用matplotlib畫圓餅圖(Pie chart)

pandas Dataframe常用的資料處理方法-上(合併資料、選擇欄位、刪除欄位、刪除列)

arrow
arrow

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