希爾排序算法思想：希爾排序是按照下標增量進行分組，對每組使用插入排序算法進行排序，隨著增量減少，每組包含的關鍵字越來越多，增量減到1時，整個序列被分為壹組，算法終止。
我們以增序排序為例，希爾排序基本步驟：選擇初始增量gap=length/2，縮小增量繼續以gap=gap/2的方式進行，直到增量gap=1為止，增量的每次變化都會將原始序列劃分為若幹組，分別對每壹組進行插入排序。
每壹次通過增量劃分組進行插入排序宏觀上小的數移到了前面，大的數移到了後面，最後增量gap=1進行插入排序後就是最終的有序序列。
由於多次插入排序，我們知道壹次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，所以shell排序是不穩定的。
發展歷史
希爾排序按其設計者希爾（Donald Shell）的名字命名，該算法由希爾在1959年所發表的論文“A high-speed sorting procedure”中所描述。
1961年，IBM公司的女程序員Marlene Metzner Norton（瑪琳·梅茨納·諾頓）首次使用FORTRAN語言編程實現了希爾排序算法。在其程序中使用了壹種簡易有效的方法設置希爾排序所需的增量序列：第壹個增量取待排序記錄個數的壹半，然後逐次減半，最後壹個增量為1。
該算法後來被稱為Shell-Metzner算法，Metzner本人在2003年的壹封電子郵件中說道：“我沒有為這種算法做任何事，我的名字不應該出現在算法的名字中。”