本系列文章同步分享於個人Blog → InformisTry-HankLee
第六天到第九天,我們都是在介紹屬於Brute Force的演算法,若要複習的人可以點下面連結:
今天開始的三天,我們就要來介紹另一個演算法類別Decrease and Conquer以及三種屬於這個類別的演算法。
Decrease and Conquer
的中文翻譯成『減治法』,這個名稱我一看到就是滿頭問號,但是當我瞭解他的流程之後,我才恍然大悟,我們在生活中很多事情都是透過這樣的方式在處理問題,只是從來沒想到居然真的被歸納出一個名稱來表示,那到底Decrease and Conquer是怎樣的一個過程呢?簡單來說,它分成下列三個步驟:
我相信如果大家仔細想想,應該多多少少可以想到一到兩個例子是用這個方式來解決問題的,那到底又有哪些演算法是屬於這種將大問題拆解成小問題來解決的呢?
我們在這三天將會介紹三種:Insertion Sort, Shell Sort和Binary Search,今天我們就來介紹第一種Insertion Sort。
Insertion Sort其實有一個生活化的例子,大家應該都有玩過撲克牌吧,我們在玩撲克牌很多人都會有個習慣,會把撲克牌一張一張的抽出來,看看這張牌的大小應該在手排中的哪個位置,找到他所屬的位置之後,再插進手牌中,最後手上的牌就是經過排序的樣子,比較方便之後出牌或自己比較容易理解牌型。
其實這個動作就是Insertion Sort,Insertion Sort的步驟就是:
我們在玩撲克牌的時候也是這樣去排手牌的吧。
Insertion Sort也算是很容易實現的演算法,其Pseudo-code如下:
// Input: An array Array[0...n-1] of orderable elements
// Output: An array Array[0...n-1] sorted in ascending order
function InsertionSort(Array[0, ..., n-1]){
for i = 1 to n-1 {
v = Array[i]
j = i - 1
while j >= 0 and Array[j] > v {
Array[j+1] = Array[j]
j = j - 1
}
A[j+1] = v
}
}
按照慣例,讓我們來看個GIF圖檔吧:
我的GIF圖中省略了一個一個值『換位置』的過程,但仍可從中發現,在一個一個『取值』時,是從左至右
取值,但是在進行『比較』的時候,卻是從右至左
比較,比較的過程中,當遇到比自己小的值的時候,就會將值放入當前位置;此外,由於Insertion Sort在執行時,也是一個巢狀迴圈的結構,因此其時間複雜度亦為O(n^2)
,而其Best Case、Average Case和Worst Case會發生在下列狀況:
O(n)
(因為內層迴圈不會跑,僅跑了外層迴圈而已)。O(n^2)
。O(n^2)
。O(n^2)
,但其Best Case的時間複雜度為O(n)
。明天我們將會介紹的是Insertion Sort的改良版 - Shell Sort。