希爾排序(Shell's Sort) 是插入排序的一種又稱 “縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因 D.L.Shell 于 1959 年提出而得名。
希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至 1 時(shí)，整個(gè)文件恰被分成一組，算法便終止。
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率。
但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位。
該方法實(shí)質(zhì)上是一種分組插入方法
比較相隔較遠(yuǎn)距離（稱為增量）的數(shù)，使得數(shù)移動(dòng)時(shí)能跨過多個(gè)元素，則進(jìn)行一次比較就可能消除多個(gè)元素交換。D.L.shell 于 1959 年在以他名字命名的排序算法中實(shí)現(xiàn)了這一思想。算法先將要排序的一組數(shù)按某個(gè)增量d 分成若干組，每組中記錄的下標(biāo)相差 d. 對(duì)每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對(duì)它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到 1 時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。
一般的初次取序列的一半為增量，以后每次減半，直到增量為 1。
穩(wěn)定性
由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，所以 shell 排序是不穩(wěn)定的。
排序過程
縮小增量
希爾排序?qū)儆诓迦腩惻判? 是將整個(gè)有序序列分割成若干小的子序列分別進(jìn)行插入排序。
排序過程：先取一個(gè)正整數(shù) d1數(shù)組元素放一組，組內(nèi)進(jìn)行直接插入排序；然后取 d2
三趟結(jié)果
04 13 27 38 49 49 55 65 76 97
希爾排序是按照不同步長對(duì)元素進(jìn)行插入排序，當(dāng)剛開始元素很無序的時(shí)候，步長最大，所以插入排序的元素個(gè)數(shù)很少，速度很快；當(dāng)元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨?。所以，希爾排序?a target="_blank" rel="nofollow">時(shí)間復(fù)雜度會(huì)比 o(n^2) 好一些。
java代碼如下：
package 數(shù)據(jù)結(jié)構(gòu);
public class Xierpaixu {
public static void sort(int arr []){
int h=1;
while(h<arr.length-1){
h=h*3+1;//h不斷變化，間隔不斷變大，找到最大的間隔，開始排序
}
while(h>0){
int temp=0;
for(int i=h;i<arr.length;i++){
temp=arr[i];
int j=i;
while(j>h-1&&arr[j-h]>=temp){
arr[j]=arr[j-h];
j-=h;
}
arr[j]=temp;
}
h=(h-1)/3;
}
}
}
測(cè)試：
package 數(shù)據(jù)結(jié)構(gòu);
public class TextXierpaixu {
public static void main(String args[]){
? int arr[]={2,5,4,15,54,34,21,43,22,67,76,78,33,61};
? Xierpaixu.sort(arr);
? for(int i=0;i<arr.length-1;i++){
? System.out.println(arr[i]);
? }
}}
輸出結(jié)果如下：
好啦,這次就到這里啦，有問題可以和我留言哦！
其他博客的鏈接：
Github個(gè)人網(wǎng)站?知乎?簡(jiǎn)書
歡迎各位訪問哦，這次就到這里啦！
