希爾排序(Shell's sort)是一種非常“神奇”的排序算法。說它“神奇”,是因為沒有任何人能清楚地說明它的性能到底能到什麼情況。希爾排序因DL. Shell於1959年提出而得名。自從CAR 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.排序完成。
從上面可以看出,增量是不斷減小的,因此,希爾排序又被成為“縮小增量排序”。
代碼實現
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) { // 計算出最大的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); } } // 計算出下一個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(); } }運行結果:
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
算法性能/複雜度
希爾排序的增量數列可以任取,需要的唯一條件是最後一個一定為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。
算法穩定性
我們都知道插入排序是穩定算法。但是,Shell排序是一個多次插入的過程。在一次插入中我們能確保不移動相同元素的順序,但在多次的插入中,相同元素完全有可能在不同的插入輪次被移動,最後穩定性被破壞,因此,Shell排序不是一個穩定的算法。
算法適用場景
Shell排序雖然快,但是畢竟是插入排序,其數量級並沒有後起之秀--快速排序O(nn)快。在大量數據面前,Shell排序不是一個好的算法。但是,中小型規模的數據完全可以使用它。