快捷導(dǎo)航

細(xì)致解讀希爾排序算法與相關(guān)的Java代碼實(shí)現(xiàn)

更新時(shí)間：2016年05月04日 17:11:00 作者：飛翔的貓咪

這篇文章主要介紹了希爾排序算法與相關(guān)的Java代碼實(shí)現(xiàn),希爾排序的時(shí)間復(fù)雜度根據(jù)步長(zhǎng)序列的不同而不同,需要的朋友可以參考下

希爾排序（Shell's sort）是一種非?！吧衿妗钡呐判蛩惴?。說(shuō)它“神奇”，是因?yàn)闆](méi)有任何人能清楚地說(shuō)明它的性能到底能到什么情況。希爾排序因DL．Shell于1959年提出而得名。自從C. A. R. Hoare在1962年提出快速排序后，由于其更為簡(jiǎn)單，一般采用快速排序。但是，不少數(shù)學(xué)家們還是孜孜不倦地尋找希爾排序的最佳復(fù)雜度。作為普通程序員，我們可以學(xué)習(xí)下希爾的思路。
順便說(shuō)一句，在希爾排序出現(xiàn)之前，計(jì)算機(jī)界普遍存在“排序算法不可能突破O(n2)”的觀點(diǎn)。希爾排序的出現(xiàn)打破了這個(gè)魔咒，很快，快速排序等算法相繼問(wèn)世。從這個(gè)意義上說(shuō)，希爾排序帶領(lǐng)我們走向了一個(gè)新的時(shí)代。

算法概述/思路
希爾排序的提出，主要基于以下兩點(diǎn)：
1.插入排序算法在數(shù)組基本有序的情況下，可以近似達(dá)到O(n)復(fù)雜度，效率極高。
2.但插入排序每次只能將數(shù)據(jù)移動(dòng)一位，在數(shù)組較大且基本無(wú)序的情況下性能會(huì)迅速惡化。

基于此，我們可以使用一種分組的插入排序方法，具體做法是：（以一個(gè)16元素大小的數(shù)組為例）
1.選擇一個(gè)增量delta，該增量大于1，從數(shù)組中按此增量選擇出子數(shù)組進(jìn)行一次直接插入排序。例如，若選擇增量為5，則對(duì)下標(biāo)為0，5，10，15的元素進(jìn)行排序。
2.保留該增量delta并依次移動(dòng)首個(gè)元素進(jìn)行直接插入排序，直到一輪完成。對(duì)于上面的例子，則依次對(duì)數(shù)組[1，6，11]，[2，7，12]，[3，8，13]，[4，9，14]進(jìn)行排序。
3.減小增量，不斷重復(fù)上述過(guò)程，直到增量減小為1.顯然，最后一次為直接插入排序。
4.排序完成。
從上面可以看出，增量是不斷減小的，因此，希爾排序又被成為“縮小增量排序”。

代碼實(shí)現(xiàn)

package sort; 
 
public class ShellSortTest { 
  public static int count = 0; 
 
  public static void main(String[] args) { 
 
    int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; 
    print(data); 
    shellSort(data); 
    print(data); 
 
  } 
 
  public static void shellSort(int[] data) { 
    // 計(jì)算出最大的h值 
    int h = 1; 
    while (h <= data.length / 3) { 
      h = h * 3 + 1; 
    } 
    while (h > 0) { 
      for (int i = h; i < data.length; i += h) { 
        if (data[i] < data[i - h]) { 
          int tmp = data[i]; 
          int j = i - h; 
          while (j >= 0 && data[j] > tmp) { 
            data[j + h] = data[j]; 
            j -= h; 
          } 
          data[j + h] = tmp; 
          print(data); 
        } 
      } 
      // 計(jì)算出下一個(gè)h值 
      h = (h - 1) / 3; 
    } 
  } 
 
  public static void print(int[] data) { 
    for (int i = 0; i < data.length; i++) { 
      System.out.print(data[i] + "\t"); 
    } 
    System.out.println(); 
  } 
 
}

運(yùn)行結(jié)果：

5  3  6  2  1  9  4  8  7   
1  3  6  2  5  9  4  8  7   
1  2  3  6  5  9  4  8  7   
1  2  3  5  6  9  4  8  7   
1  2  3  4  5  6  9  8  7   
1  2  3  4  5  6  8  9  7   
1  2  3  4  5  6  7  8  9   
1  2  3  4  5  6  7  8  9

算法性能/復(fù)雜度
希爾排序的增量數(shù)列可以任取，需要的唯一條件是最后一個(gè)一定為1（因?yàn)橐ＷC按1有序）。但是，不同的數(shù)列選取會(huì)對(duì)算法的性能造成極大的影響。上面的代碼演示了兩種增量。
切記：增量序列中每?jī)蓚€(gè)元素最好不要出現(xiàn)1以外的公因子?。ê茱@然，按4有序的數(shù)列再去按2排序意義并不大）。
下面是一些常見的增量序列。
第一種增量是最初Donald Shell提出的增量，即折半降低直到1。據(jù)研究，使用希爾增量，其時(shí)間復(fù)雜度還是O(n2)。
第二種增量Hibbard：{1, 3, ..., 2^k-1}。該增量序列的時(shí)間復(fù)雜度大約是O(n^1.5)。
第三種增量Sedgewick增量：(1, 5, 19, 41, 109,...)，其生成序列或者是9*4^i - 9*2^i + 1或者是4^i - 3*2^i + 1。

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

算法適用場(chǎng)景
Shell排序雖然快，但是畢竟是插入排序，其數(shù)量級(jí)并沒(méi)有后起之秀--快速排序O(n㏒n)快。在大量數(shù)據(jù)面前，Shell排序不是一個(gè)好的算法。但是，中小型規(guī)模的數(shù)據(jù)完全可以使用它。

您可能感興趣的文章: