Aloha！又是我少女人妻 Uerica ～ 我每天看到時間快接近午夜 12 點，都能感受到灰姑娘的慌張，仙杜瑞拉跟王子跳舞到一半急急忙忙地跑回家，是因為她還沒發鐵人賽文章！
又稱 遞減增量排序法 diminishing increment sort。希爾排序法是插入排序法 insertion Sort 的改良版，前面提過，插入排序法用在排序完全是亂數的元素效率是很低的，所以用此方法來解決。
希爾排序法的作法是由大到小選擇數個間距 Gap，資料依據選擇的間距將元素分組，分別進行插入排序，反覆操作直到最後一個間距為 1 為止，間距的選擇對執行效率會有很大的影響。
常見的 Gap
希爾排序法 Shell Sort 操作圖解
首先取一個未排序數列，數列元素有 8 個 (N = 8) ，第一次排序的 Gap 取 N/2 = 8/2 = 4。
因 Gap 是 4，表示每四個為一組相互比較，所以第 0 個與第 4 個元素比較並排序。
比較後發現因 56 大於 12，所以 12 與 56 交換位置。
結束後，繼續下一組元素的比較，比較第 1 個與第 5 個元素，因 1 小於 49 所以位置不變。
再繼續下一組元素的比較，因 33 大於 20 ，所以 20 與 33 交換位置。
結束後，再繼續下一組元素的比較，因 7 小於 51 所以位置不變。已經比較到最後一個元素，所以第一回合結束。
結束第一回合後，將 Gap 縮小，此時 Gap 取 N/4 = 8/4 = 2，表示每兩個為一組比較。如下圖，第 0 個與第 2 個比較，因 12 小於 20 所以維持不變。
再下一組， 1 小於 7 ，所以維持不變。
再下一組， 20 小於 56 ，所以維持不變。
再下一組， 7 小於 49 ，所以維持不變。
再下一組， 56 大於 33 ，所以將 33 與 56 交換位置，如同插入排序法，往前插入後，要再比較前一個位置的元素，如下圖因 20 小於 33 ，所以維持不變。
再回來比較下一組元素，因 49 小於 51 所以維持不變。比較到最後一個元素，所以第二回合結束。
再將 Gap 縮小至 1 ，表示鄰近的兩個元素為一組互相做比較並排序。如下圖第 0 個與第 1 個位置做比較。因 12 大於 1 ，所以 1 與 12 交換位置。
再比較下一組元素，12 小於 20，所以位置維持不變
再比較下一組元素，20 大於 7 所以位置交換。交換後如同插入排序法，7要再往前一個元素比較，因 12 大於 7，所以 7 再與 12 交換。7 再往前一個元素比較，因 1 小於 7 所以維持不變。
再比較下一組元素...
因 56 大於 51 ，所以需交換位置。交換後需再往前比較，因 49 小於 51 所以維持不變。
將啷～這樣整個希爾排序法就完成啦！484 很簡單啊！
又稱 搖晃排序法 Shaker Sort、雞尾酒排序法Cocktail Sort，在這邊我使用雙氣泡排序這個名稱較為好懂，顧名思義就是氣泡排序法的改良版，原本的氣泡排序法只從一個方向做比對，而雙向氣泡排序法則是兩邊來回反覆操作，直到排序完成為止。
雙向氣泡排序法 Bidirectional Bubble Sort 操作圖解
首先取一個未排序元素數列如下
跟氣泡排序法一樣，先由右往左開始兩兩比對。若左邊元素小於右邊元素位置不變。
若左邊元素大於右邊元素則兩兩交換。下圖 3 大於 1 ，所以兩元素交換。
繼續向前比對，因 5 大於 1 ，所以兩元素交換。
最小值已排序到最左邊，第一回合結束。
與氣泡排序法不同之處，第二回合由左往右開始。若左邊元素大於右邊元素則做交換。因 5 大於 3 ，所以兩兩交換。
因 5 大於 2 ，所以兩兩交換。
因 5 大於 4 ，所以兩兩交換。
此時最大值已排到最右邊，第二回合結束
此時再從右往左開始比對，左邊元素小於右邊元素位置不變。
若左邊元素大於右邊元素則兩兩交換，因 3 大於 2 ，所以兩元素交換。
第三回合結束！排序就完成了，比原本的氣泡排序法省了很多時間呢！
基數排序法與前面的排序法不同，基數排序法不用通過元素相互比較來做排序，且可用在多鍵值的元素排序，如兩個鍵值 (1,2)、(2,4)、(3,2)，或撲克牌 (梅花,3)、(方塊,7)等，屬於較為特殊的排序法。
基數排序法是用桶子 Bucket 來將元素分類，並依照每個位數來做排序，元素的基底為多少就需準備多少個桶，若元素為數值，基底則為進制。例如 10 進位的數值則準備 10 個桶子，16 進位則是 16 個桶子，以此類推。
依照位數排序的先後順序，可分為兩種：
參考資料:
好的～～感謝閱讀！大家掰掰明天見啦！再不發文我的馬車也要變南瓜跟老鼠了！
iThome鐵人賽
看影片追技術