本系列文章同步分享於個人Blog → InformisTry-HankLee

前言

第十天我們第一次介紹了Decrease and Conquer類別的運作方式，同時也介紹了Insertion Sort，小複習一下，Insertion Sort就是大部分人在玩撲克牌時針對手牌進行排序的方式，而今天我們來介紹Insertion Sort的進化版 -- Shell Sort。

Shell Sort如何改善Insertion Sort？

Shell Sort是針對目標陣列再次進行Decrease的動作，將陣列以預先定義好的區間的數值進行比較，針對這幾個指定位置的數值排序，當此利用此區間進行排序完成後，再將區間縮小，反覆之前的動作，直到區間已經無法縮小（最小區間為3）後，再進行原先的Insertion Sort。

文字實在有點難形容這個過程，我們直接來看GIF吧：

從GIF中可以看到，我們一開始從1+5的倍數的位置(1, 6, 11, 16, 21, ...)開始進行排序，並僅在這幾個位置進行數值的交換，當利用5的倍數作為依據將陣列排序後，改成使用3的倍數的位置再排序一次，結束之後，因為3的倍數基本上已經是最小單位了，因此我們就直接針對這個已經排序兩次的陣列進行InSertion Sort，就可以得到結果啦。

而如何決定這個幾的倍數是一個一直被大家廣泛討論的問題，但是有一個已知數列可以讓Shell Sort執行效率還不錯：1, 4, 13, 40, 121, 364,...(3x+1)

x為『前一個數』

Shell Sort的時間複雜度

當我們使用上方數列（1, 4, 13, 40, 121, 364,...(3x+1))作為Shell Sort的依據時，Worst case的時間複雜度為Ｏ(n^(3/2))；而且Shell Sort本身是一個Unstable Sorting，原因是因為他的排序某程度而言，並沒有照著數值原先順序進行一個一個排序，Shell Sort的排序方式有點像跳棋，所以有可能當兩個數值一樣，但後面的數值會被往前移動而跳過原先排在前面且值相同的數值，有興趣的人可以試著畫圖試試看。

小結

• Shell Sort是進化版的Insertion Sort。
• 讓Shell Sort執行效率還不錯的數列：1, 4, 13, 40, 121, 364,...(3x+1)。
• Shell Sort若使用上方數列，其Worst case的時間複雜度為Ｏ(n^(3/2))。
• Shell Sort是Unstable Sorting。

預告

明天我們將會介紹的是Binary Search。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin