希爾排序(Shell's Sort) 是插入排序的一種又稱 “縮小增量排序”（Diminishing Increment Sort）瓜喇，是直接插入排序算法的一種更高效的改進版本削彬。希爾排序是非穩(wěn)定排序算法髓霞。該方法因 D.L.Shell 于 1959 年提出而得名甜橱。
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序高每；隨著增量逐漸減少首繁，每組包含的關鍵詞越來越多，當增量減至 1 時哨查，整個文件恰被分成一組逗抑，算法便終止。
希爾排序是基于插入排序的以下兩點性質而提出改進方法的：
插入排序在對幾乎已經排好序的數(shù)據(jù)操作時解恰，效率高锋八，即可以達到線性排序的效率。
但插入排序一般來說是低效的护盈，因為插入排序每次只能將數(shù)據(jù)移動一位挟纱。
該方法實質上是一種分組插入方法
比較相隔較遠距離（稱為增量）的數(shù)，使得數(shù)移動時能跨過多個元素腐宋，則進行一次比較就可能消除多個元素交換紊服。D.L.shell 于 1959 年在以他名字命名的排序算法中實現(xiàn)了這一思想檀轨。算法先將要排序的一組數(shù)按某個增量d 分成若干組，每組中記錄的下標相差 d. 對每組中全部元素進行排序欺嗤，然后再用一個較小的增量對它進行参萄，在每組中再進行排序。當增量減到 1 時煎饼，整個要排序的數(shù)被分成一組讹挎，排序完成。
一般的初次取序列的一半為增量吆玖，以后每次減半筒溃，直到增量為 1。
穩(wěn)定性
由于多次插入排序沾乘，我們知道一次插入排序是穩(wěn)定的怜奖，不會改變相同元素的相對順序，但在不同的插入排序過程中翅阵，相同的元素可能在各自的插入排序中移動歪玲，最后其穩(wěn)定性就會被打亂，所以 shell 排序是不穩(wěn)定的掷匠。
排序過程
縮小增量
希爾排序屬于插入類排序, 是將整個有序序列分割成若干小的子序列分別進行插入排序滥崩。
排序過程：先取一個正整數(shù) d1數(shù)組元素放一組，組內進行直接插入排序讹语；然后取 d2
三趟結果
04 13 27 38 49 49 55 65 76 97
希爾排序是按照不同步長對元素進行插入排序夭委，當剛開始元素很無序的時候，步長最大募强，所以插入排序的元素個數(shù)很少，速度很快崇摄；當元素基本有序了擎值，步長很小，插入排序對于有序的序列效率很高逐抑。所以鸠儿，希爾排序的時間復雜度會比 o(n^2) 好一些。
java代碼如下：
package 數(shù)據(jù)結構;
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;
}
}
}
測試：
package 數(shù)據(jù)結構;
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]);
? }
}}
輸出結果如下：
好啦,這次就到這里啦命斧，有問題可以和我留言哦田晚！
其他博客的鏈接：
歡迎各位訪問哦，這次就到這里啦国葬！
