概述

　　希爾排序法(縮小增量法) 屬于插入類排序，是將整個無序列分割成若干小的子序列分別進行插入排序的方法。

　　把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。

希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：

• 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率。

• 但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位。

實現(xiàn)過程

　　先取一個正整數(shù)d1小于n，把所有序號相隔d1的數(shù)組元素放一組，組內(nèi)進行直接插入排序；然后取d2小于d1，重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止。

　　例如，假設(shè)有這樣一組數(shù)[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應(yīng)該看起來是這樣：

13 14 94 33 82?
25 59 94 65 23?
45 27 73 25 39?
10

然后我們對每列進行排序：

10 14 73 25 23?
13 27 94 33 39?
25 59 94 65 82?
45

　　將上述四行數(shù)字，依序接在一起時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經(jīng)移至正確位置了，然后再以3為步長進行排序：

10 14 73?
25 23 13?
27 94 33?
39 25 59?
94 65 82?
45

排序之后變?yōu)?#xff1a;

10 14 13?
25 23 33?
27 25 59?
39 65 73?
45 94 82?
94

最后以1步長進行排序（此時就是簡單的插入排序了）。

實現(xiàn)效率

　　希爾排序是一個不穩(wěn)定的排序，其時間復(fù)雜度受步長（增量）的影響。

　　空間復(fù)雜度：　Ｏ(1)

　　時間復(fù)雜度：　平均 O(n^1.3)?
最好　O(n)?
最壞　O(n^2)

Java實現(xiàn)

public static void shellSort(int[] a) {int gap = 1, i, j, len = a.length;int temp;//插入排序交換值的暫存//確定初始步長while (gap < len / 3){gap = gap * 3 + 1;}for (; gap > 0; gap /= 3){//循環(huán)遍歷步長，最后必為1for (i = gap; i < len; i++) {//每一列依次向前做插入排序temp = a[i];//每一列中在a[i]上面且比a[i]大的元素依次向下移動for (j = i - gap; j >= 0 && a[j] > temp; j -= gap){a[j + gap] = a[j];}//a[i]填補空白，完成一列中的依次插入排序a[j + gap] = temp;}} }

版權(quán)聲明：請尊重個人勞動成果，轉(zhuǎn)載注明出處，謝謝！

http://blog.csdn.net/amazing7/article/details/51386145

總結(jié)

以上是生活随笔為你收集整理的[数据结构] 希尔排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。