如果還沒有看過 Jason 寫的【演算法】排序演算法 Sorting Algorithm 可以先去看看那篇,再回來看這篇。 Ok, 那讓我們書接上文,今天再來介紹另外兩種排序演算法:插入排序、希爾排序。 一、插入排序 Insertion Sort
插入排序是一種非常簡單、直觀的排序演算法。它的想法是,將還未排序的元素從已排序的序列由後向前一一比較,找到它們在以排序數列中的位子將它們插入進去,直至所有未排序的元素都以插入已排序的數列中。
你也可以想像成,平常在玩樸克牌的時候,莊家一張一張發牌,然後你一張一張的把牌依照順序加入你的手牌的過程。e.g.
看完上圖應該就可以蠻清楚的知道插入排序的演算流程。
但我們也可以發現,由於在演算過程中需要做大量插入 ( Insert ) 的動作,所以在實作上我們可以考慮採用連結串列 ( Linked-list ) 來取代陣列 ( Array ) 存放資料。在 Array 中做插入的動作會導致有大量的資料需要做搬移,每插一次就有大量的資料要搬再乘上大量的插入,這會是相當驚人的,也很沒效率,所以不建議使用陣列。 二、希爾排序 Shell Sort
希爾排序又稱作「 遞減增量排序 ( Diminishing Increment Sort )」,是希爾於1959年發表的排序演算法,而它基本上就是基於我們剛剛提到的插入演算法去進行改良的。核心想法是:
接著我們會由大到小取數個不同的間距 ( Gap ) 來做,然後最後一個必須是1。 至於這個 Gap 有點類似於上篇 quick sort 裡的 pivot 取的好不好是會關鍵性影響演算法效能的! 一般比較常見的取法是,若數列中有 N 個 Element,我們會取 N/2、N/4、N/8、N/16、...、1。
0 評論
發表回覆。 |
Jason Chen人不光是生來就擁有一切,而是靠他從學習中得到的一切來造就自己。- 歌德 文章分類
全部
封存檔
九月 2023
|