shell 排序是一種插入排序
亦被稱為 縮小增量排序
shell排序的實質(zhì)就是分組插入排序
基本思想
- 將需要排序的元素序列array分割成若干個子序列(array1,array2,array3......)
是根據(jù)“增量”分成的子序列场刑，增量要比array.length小絮姆，盡量可以被array的長度整除(默認(rèn)增量gap=array.length/2) - 對子序列分別進行直接插入排序
- 然后依次縮小增量(gap=gap/2)進行重新劃分子序列棠耕，對劃分好的子序列重新進行排序
- 最終循環(huán)2-3步驟潮模，直到gap=1，進行完最后一次排序比伏，排序終止
描述起來不難弥锄，希爾排序背后的邏輯卻是不簡單，希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法祖能，屬于最早的一批突破復(fù)雜度的一批次排序歉秫，其復(fù)雜度受著數(shù)組本身的排列和初始gap的取值有關(guān)，對于其復(fù)雜度的計算/證明养铸，對我個人而言有些難雁芙，數(shù)學(xué)戰(zhàn)五渣，只能哭唧唧钞螟，有能力的大佬們可以看一下本鏈接：https://blog.csdn.net/u013007900/article/details/51232472
下面筆者本著實踐的原則兔甘，進行一下希爾排序的圖解及實現(xiàn)：
首先，筆者認(rèn)為前面文字還是過于抽象鳞滨，并不能直觀的表達增量(也稱希爾增量)的含義洞焙，在此結(jié)合圖形解釋一下gap究竟是怎么將數(shù)組分組的，如下圖：
如上圖所示拯啦，數(shù)組的長度為9澡匪，初始gap指定為4，即按照增量=4來進行數(shù)組分組提岔；
數(shù)組下方標(biāo)記了其元素對應(yīng)的index索引序號仙蛉，按照gap進行遞增，構(gòu)造對應(yīng)分組：
第一組：index=0,4,8 → {array[0], array[4], array[8]}
第二組：index=1,5 → {array[1], array[5]}
第三組：index=2,6 → {array[2], array[6]}
第四組：index=3,7 → {array[3], array[7]}
上圖已經(jīng)足夠表明了如何進行分組碱蒙，下面就開始進行圖解整個排序的流程荠瘪，如下圖：
上圖中夯巷，按照之前所描述的算法邏輯：
- gap依次取值 4, 2, 1，即總共進行了三輪的分組排序哀墓；
- 每輪的分組數(shù)量分別為 4組, 2組, 1組（可根據(jù)圖中顏色進行區(qū)分組數(shù)）
- 每輪僅對各自組內(nèi)的序列進行排序即可趁餐。
按照算法給定的是對分組進行直接插入排序，個人認(rèn)為只要能對組內(nèi)元素進行排序篮绰，什么算法均可
原理講的差不多了后雷，下面直接上代碼，將理論具現(xiàn)到實踐中：
public void shellSort(int[] arrays) {
// 縮小增量法
int gap = arrays.length / 2;
while (gap >= 1) {
// 共有g(shù)ap組通過增量的分組吠各，進行排序
for (int i = 0; i < gap; i++) {
// 對增量對應(yīng)一組的數(shù)組進行排序(對子數(shù)組隨便選擇一個排序算法)
for (int j = i + gap; j < arrays.length; j += gap) {
//i,i+gap,i+2*gap,i+3*gap...
int index = j;
while (index >= i + gap && arrays[index] < arrays[index - gap]) {
swap(arrays, index, index - gap);
index -= gap;
}
}
}
gap /= 2;
}
}
希爾排序臀突，總的來說不難理解，最終其實也是對gap=1贾漏，即整個數(shù)組進行最終的直接插入排序候学，但之前的幾輪排序確定了各自分組內(nèi)的相對位置，對最終的增量gap=1的排序其實是起到了輔助作用纵散。
至于具體的證明其比直接插入復(fù)雜度低梳码，性能更高，從書面語我可能給不出什么解釋伍掀，想了解的還是戳上面給出的鏈接吧掰茶，在這里也再貼一下：https://blog.csdn.net/u013007900/article/details/51232472
