Shell Sort

終於弄懂這個了阿 哈哈
人家的說明我真的都看不懂 Orz
Shell Sort是利用insertion sort的一個特性
白話的說insertion sort是將未排序集合中拿一個出來，並且"插入"至以排序集合中自己應至的位置
將步驟標上順序
排序陣列E 且 n = |E|
1. FOR pos = n TO 1 STEP -1
2. 取出pos位置的元素
3. 將pos位置元素插入至pos+1到n這個以排序的部分
步驟3 假如不要用單純的陣列，改使用Linked List的話
插入的動作可以很省時間，而且不需要不斷地交換位置，只需要二元搜尋然後插入
說起來如果陣列本來就排的差不多的話 insertion sort是很快的
http://www.sorting-algorithms.com/insertion-sort

Shell Sort則是利用這個特性並衍生出下面的概念
利用Insertion Sort大致排好一些 > 再排一些 > 再排一些 > ... > 完成。
至於證明！！ 在查一下吧！！
演算法如下

// 找出最大的間隔

h = 1
while h < n, h = 3*h + 1

// 當間隔大於0的時候，用insertion sort排序
while h > 0,
   h = h / 3
   for k = 1:h, insertion sort a[k:h:n]
   → invariant: each h-sub-array is sorted
end