插入排序(Insertion Sort)

資結演算法

Written by:

本篇將為大家介紹插入排序 (Insertion Sort) 的原理、虛擬碼、程式碼與時間複雜度分析。

插入排序

概念有點類似平常玩的撲克牌。當莊家發牌時,玩家拿到第一張牌、接著拿到第二張牌的時候,就會先把兩張作比較排序好。

接下來第三張牌接著插入這堆已經排序好的排組,接著同理。直到撲克牌發完的時候,手上的撲克牌也已經依照點數大小排序好了。

虛擬碼

 

程式碼

i = 2 開始,做 n-1 個回合──將第 i 筆資料插入前面 i-1 筆已排序好的資料,形成 n 筆排序好的資料。

原先想法:

  • insert(list[], data, n) 作為副程式
  • insort(list[], n) 作為主程式

其他的寫法:這個實現方式比較接近虛擬碼

從第二個資料開始,如果第二個資料比第一個資料大,順序就維持不變;否則將第一個資料往後移動,然後將第一個資料空下來的位置讓給第二個資料。

此時第一和第二個資料就由小到大排序完成。

同理,依序移動資料直到第 n 筆資料都排序完成。

時間複雜度

1. Best Case: O(n)

若 input data 剛好是由小到大的方式給予,每一回合只需比較一次,即可決定好要插入 data 的正確位置。

又共做了 n-1 回合,故總共比較 n-1 次即可完成 sort。

如果利用 Recursive Time Function 來解時間複雜度,同樣會得到 O(n) 的結果:

 

2. Worst Case: O(n2)

若 input data 剛好是反序由小到大給予。

 

如果利用 Recursive Time Function 來解時間複雜度,同樣會得到 O(n2) 的結果:

3. Average Case: O(n2)

2 Replies to “插入排序(Insertion Sort)”

  1. 謝承璋 說:

    虛擬碼 最後打錯了喔
    A[j+1] = data; //A[i+1] = data
    這樣才對

  2. Allen 說:

    It doesn’t mention that this sort stable or not.

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *