iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 11
0

本系列文章同步分享於個人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吧:

Shell Sort

從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的時間複雜度為O(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的時間複雜度為O(n^(3/2))
  • Shell Sort是Unstable Sorting

預告

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


References

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

上一篇
Day10 -- Decrease and Conquer - Insertion Sort
下一篇
Day12 -- Decrease and Conquer - Binary Search
系列文
舌尖上的演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言