算法—3.希爾排序（中等規模最佳算法），希爾排序

算法—3.希爾排序（中等規模最佳算法），希爾排序

對於大規模亂序數組插入排序很慢，因為它只會交換相鄰的元素，因此元素只能一點一點地從數組的一端移動到另一端。例如，如果主鍵最小的元素正好在數組的盡頭，要將它挪到正確的位置就需要N-1次移動。希爾排序為了加快速度簡單地改進了插入排序，交換不相鄰的元素以對數組的局部進行排序，並最終用插入排序將局部有序的數組排序。

1.基本思想

希爾排序的思想是使數組中任意間隔為h的元素都是有序的。這樣的數組被稱為h有序數組。換句話說，一個h有序數組就是h個互相獨立的有序數組編織在一起組成的一個數組（見下圖）。在進行排序時，如果h很大，我們就能將元素移動到很遠的地方，為實現更小的h有序創造方便。用這種方式，對於任意以1結尾的h序列，我們都能夠將數組排序。這就是希爾排序。

希爾排序更高效的原因是它權衡了子數組的規模和有序性。排序之初，各個子數組都很短，排序之後子數組都是部分有序的，這兩種情況都很適合插入排序。子數組部分有序的程度取決於遞增序列的選擇。透徹理解希爾排序的性能至今仍然是一項挑戰。實際上，它是我們唯一無法准確描述其對於亂序的數組的性能特征的排序方法。

2.具體算法

/**
 * 希爾排序
 * @author huazhou
 *
 */
public class Shell extends Model{

	public void sort(Comparable[] a){
//		System.out.println("Shell");
		//將a[]按升序排列
		int N = a.length;
		int h = 1;
		//1,4,13,40,121,364,1093,...
		while(h < N/3){
			h = 3*h + 1;
		}
		//將數組變為h有序
		while(h >= 1){
			//將a[i]插入到a[i-h],a[i-2*h],a[i-3*h]...之中
			for (int i = h; i < N; i++) {
				for (int j = i; j >= h && less(a[j],a[j-h]); j-=h) {
					exch(a, j, j-h);
				}
			}
			h = h/3;
		}
	}
}

如果我們在插入排序中加入一個外循環來將h按照遞增序列遞減，我們就能得到這個簡潔的希爾排序。增幅h的初始值是數組長度乘以一個常數因子，最小為1.

和選擇排序以及插入排序形成對比的是，希爾排序也可以用於大型數組。它對任意排序（不一定是隨機的）的數組表現也很好。實際上，對於一個給定的遞增序列，構造一個使希爾排序運行緩慢的數組並不容易。下圖是可視軌跡圖：

3.算法分析

至於希爾排序算法的性能，目前最重要的結論是它的運行時間達不到平方級別。在實際應用中，使用算法中的遞增序列基本就足夠了。在最壞的情況下的比較次數和N^3/2成正比。

命題：使用遞增序列1,4,13,40,121,364...的希爾排序所需的比較次數不會超出N的若干倍乘以遞增序列的長度。

證明：大量的實驗證明平均每個增幅所帶來的比較次數約為N^1/5，但只有在N很大的時候這個增長幅度才會變得明顯。

4.總結

通過SortCompare可以看到，希爾排序比插入排序和選擇排序要快得多，並且數組越大，優勢越大。希爾排序能夠解決一些初級排序算法無能為力的問題。

有經驗的程序員有時會選擇希爾排序，因為對於中等大小的數組它的運行時間是可以接受的。它的代碼量很小，且不需要使用額外的內存空間。在後面的學習中我們會看到更加高效的算法，但除了對於很大的N，它們可能只會比希爾排序快兩倍（可能還達不到），而且更復雜。如果你需要解決一個排序問題而又沒有系統排序函數可用（例如直接接觸硬件或是運行於嵌入式系統中的代碼），可以先用希爾排序，然後再考慮是否值得將它替換為更加復雜的排序算法。

再看希爾排序執行一次百萬規模的數組的運行時間約為1秒，這完全是可以接受的。（輸入命令的時候把第二個參數設為xxx表示只運行第一個參數對應的排序算法）：

【源碼下載】