希爾排序是希爾（DonaldShell）于1959年提出的一種排序算法。希爾排序也是一種刺進排序，它是簡略刺進排序經(jīng)過改進之后的一個更高效的版本，也稱為縮小增量排序，一起該算法是沖破O(n2）的第一批算法之一。本文會以圖解的方式具體介紹希爾排序的根本思想及其代碼完成。
根本思想
希爾排序是把記錄按下標(biāo)的一定增量分組，對每組運用直接刺進排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時，整個文件恰被分成一組，算法便終止。
簡略刺進排序很安分守己，不論數(shù)組分布是怎么樣的，仍然一步一步的對元素進行比較，移動，刺進，比方[5,4,3,2,1,0]這種倒序序列，數(shù)組末端的0要回到首位置很是費勁，比較和移動元素均需n-1次。
而希爾排序在數(shù)組中選用跳躍式分組的戰(zhàn)略，經(jīng)過某個增量將數(shù)組元素劃分為若干組，然后分組進行刺進排序，隨后逐漸縮小增量，繼續(xù)按組進行刺進排序操作，直至增量為1。
希爾排序經(jīng)過這種戰(zhàn)略使得整個數(shù)組在初始階段達到從微觀上看根本有序，小的根本在前，大的根本在后。然后縮小增量，到增量為1時，其實多數(shù)情況下只需微調(diào)即可，不會涉及過多的數(shù)據(jù)移動。
咱們來看下希爾排序的根本步驟，在此咱們挑選增量gap=length/2，縮小增量繼續(xù)以gap=gap/2的方式，這種增量挑選咱們能夠用一個序列來表示，{n/2,(n/2)/2…1}，稱為增量序列。希爾排序的增量序列的挑選與證明是個數(shù)學(xué)難題，咱們挑選的這個增量序列是比較常用的，也是希爾建議的增量，稱為希爾增量，但其實這個增量序列不是最優(yōu)的。此處咱們做示例運用希爾增量。
代碼完成
在希爾排序的了解時，咱們傾向于關(guān)于每一個分組，逐組進行處理，但在代碼完成中，咱們能夠不用這么按部就班地處理完一組再調(diào)轉(zhuǎn)回來處理下一組（這樣還得加個for循環(huán)去處理分組）比方[5,4,3,2,1,0]，首次增量設(shè)gap=length/2=3,則為3組[5,2][4,1][3,0]，完成時不用循環(huán)按組處理，咱們能夠從第gap個元素開始，逐一跨組處理。一起，在刺進數(shù)據(jù)時，能夠選用元素交換法尋找最終位置，也能夠選用數(shù)組元素移動法尋找。希爾排序的代碼比較簡略，如下：
packagesortdemo;importjava.util.Arrays;/***Createdbychengxiaoon2016/11/24.*/publicclassShellSort{publicstaticvoidmain(String[]args){int[]arr={1,4,2,7,9,8,3,6};
sort(arr);
System.out.println(Arrays.toString(arr));int[]arr1={1,4,2,7,9,8,3,6};
sort1(arr1);
System.out.println(Arrays.toString(arr1));
}/***希爾排序針對有序序列在刺進時選用交換法
*@paramarr*/publicstaticvoidsort(int[]arr){//增量gap，并逐漸縮小增量for(intgap=arr.length/2;gap>0;gap/=2){//從第gap個元素，逐一對其所在組進行直接刺進排序操作for(inti=gap;i){intj=i;while(j-gap>=0&&arr[j]gap]){//刺進排序選用交換法swap(arr,j,j-gap);
j-=gap;
}
}
}
}/***希爾排序針對有序序列在刺進時選用移動法。
*@paramarr*/publicstaticvoidsort1(int[]arr){//增量gap，并逐漸縮小增量for(intgap=arr.length/2;gap>0;gap/=2){//從第gap個元素，逐一對其所在組進行直接刺進排序操作for(inti=gap;i){intj=i;inttemp=arr[j];if(arr[j]gap]){while(j-gap>=0&&tempgap]){//移動法arr[j]=arr[j-gap];
j-=gap;
}
arr[j]=temp;
}
}
}
}/***交換數(shù)組元素
*@paramarr
*@parama
*@paramb*/publicstaticvoidswap(int[]arr,inta,intb){
arr[a]=arr[a]+arr[b];
arr[b]=arr[a]-arr[b];
arr[a]=arr[a]-arr[b];
}
}