Table of Contents
前言
第十天我們第一次介紹了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。