為什么80%的碼農都做不了架構師？>>> ??

希爾排序（Shell's sort）是一種非?！吧衿妗钡呐判蛩惴āＵf它“神奇”，是因為沒有任何人能清楚地說明它的性能到底能到什么情況。希爾排序因DL．Shell于1959年提出而得名。自從C. A. R. Hoare在1962年提出快速排序后，由于其更為簡單，一般采用快速排序。但是，不少數學家們還是孜孜不倦地尋找希爾排序的最佳復雜度。作為普通程序員，我們可以學習下希爾的思路。

順便說一句，在希爾排序出現之前，計算機界普遍存在“排序算法不可能突破O(n2)”的觀點。希爾排序的出現打破了這個魔咒，很快，快速排序等算法相繼問世。從這個意義上說，希爾排序帶領我們走向了一個新的時代。

?

算法概述/思路

希爾排序的提出，主要基于以下兩點：

1.插入排序算法在數組基本有序的情況下，可以近似達到O(n)復雜度，效率極高。

2.但插入排序每次只能將數據移動一位，在數組較大且基本無序的情況下性能會迅速惡化。

?

基于此，我們可以使用一種分組的插入排序方法，具體做法是：（以一個16元素大小的數組為例）

1.選擇一個增量delta，該增量大于1，從數組中按此增量選擇出子數組進行一次直接插入排序。例如，若選擇增量為5，則對下標為0，5，10，15的元素進行排序。

2.保留該增量delta并依次移動首個元素進行直接插入排序，直到一輪完成。對于上面的例子，則依次對數組[1，6，11]，[2，7，12]，[3，8，13]，[4，9，14]進行排序。

3.減小增量，不斷重復上述過程，直到增量減小為1.顯然，最后一次為直接插入排序。

4.排序完成。

從上面可以看出，增量是不斷減小的，因此，希爾排序又被成為“縮小增量排序”。

下面是希爾排序的示意圖（圖片來自維基百科）:

?http://upload.wikimedia.org/wikipedia/commons/d/d8/Sorting_shellsort_anim.gif

代碼實現

實現代碼1：

public?static?void?shellSort(int[]?arr){?int?temp;?for?(int?delta?=?arr.length/2;?delta>=1;?delta/=2){??????????????????????????????//對每個增量進行一次排序?for?(int?i=delta;?i<arr.length;?i++){???????????????for?(int?j=i;?j>=delta?&&?arr[j]<arr[j-delta];?j-=delta){?//注意每個地方增量和差值都是delta?temp?=?arr[j-delta];?arr[j-delta]?=?arr[j];?arr[j]?=?temp;?}?}//loop?i?}//loop?delta? }

實現代碼2：

public?static?void?shellSort2(int[]?arr){?int?delta?=?1;?while?(delta?<?arr.length/3){//generate?delta?delta=delta*3+1;????//?<O(n^(3/2))?by?Knuth,1973>:?1,?4,?13,?40,?121,?...?}??????????int?temp;?for?(;?delta>=1;?delta/=3){?for?(int?i=delta;?i<arr.length;?i++){???????????????for?(int?j=i;?j>=delta?&&?arr[j]<arr[j-delta];?j-=delta){?temp?=?arr[j-delta];?arr[j-delta]?=?arr[j];?arr[j]?=?temp;?}?}//loop?i?}//loop?delta? }

算法性能/復雜度

希爾排序的增量數列可以任取，需要的唯一條件是最后一個一定為1（因為要保證按1有序）。但是，不同的數列選取會對算法的性能造成極大的影響。上面的代碼演示了兩種增量。

切記：增量序列中每兩個元素最好不要出現1以外的公因子！（很顯然，按4有序的數列再去按2排序意義并不大）。

下面是一些常見的增量序列。

第一種增量是最初Donald Shell提出的增量，即折半降低直到1。據研究，使用希爾增量，其時間復雜度還是O(n2)。

第二種增量Hibbard：{1, 3, ..., 2^k-1}。該增量序列的時間復雜度大約是O(n^1.5)。

第三種增量Sedgewick增量：(1, 5, 19, 41, 109,...)，其生成序列或者是9*4^i - 9*2^i + 1或者是4^i - 3*2^i + 1。

下面的表中有更多的增量（來自http://en.wikipedia.org/wiki/Shellsort）：

算法穩定性

我們都知道插入排序是穩定算法。但是，Shell排序是一個多次插入的過程。在一次插入中我們能確保不移動相同元素的順序，但在多次的插入中，相同元素完全有可能在不同的插入輪次被移動，最后穩定性被破壞，因此，Shell排序不是一個穩定的算法。

?

算法適用場景

Shell排序雖然快，但是畢竟是插入排序，其數量級并沒有后起之秀--快速排序O(n㏒n)快。在大量數據面前，Shell排序不是一個好的算法。但是，中小型規模的數據完全可以使用它。

轉載于:https://my.oschina.net/lifj/blog/389714

總結

以上是生活随笔為你收集整理的常见排序算法：希尔排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。