Java排序算法--希爾排序（Shellsort）

希爾排序

希爾排序：它通過比較相距一定間隔的元素來工作，各趟比較所用的距離隨著算法的進行而減小，直到只比較相鄰元素的最後一趟排序為止。希爾排序也叫縮減增量排序（diminishing increment sort）。

希爾排序使用一個序列h₁，h₂，h₃，…，h_t，叫做增量序列（increment sequence）。在使用增量h_k的一趟排序之後，對於每一個i我們都有a[i] ≤ a[i+h_k]，所有相隔h_k的元素都被排序，此時稱文件是h_k排序的（h_k-sorted）。希爾排序的一個重要性質：一個h_k排序的文件（然後將是h_k-1排序的）保持它的h_k排序性。

 h_k排序的一般做法是，對於h_k，h_k+1，...，N-1中的每一個位置i，把其上的元素放到i，i-h_k，i-2h_k，...中的正確位置上。一趟h_k排序的作用就是對h_k個獨立的子數組執行一次插入排序。

Shell建議序列：h_t=N/2值的下界，h_k=h_k+1/2值的下界。使用希爾增量的希爾排序：

    /**
     * Shellsort,using Shell's(poor) increments
     * @param a an array of Comparable items
     */
    public static <AnyType extends Comparable<? super AnyType>> void shellsort(AnyType[] a){
    	int j;
    	for(int gap=a.length/2;gap>0;gap/=2){
    		for(int i=gap;i<a.length;i++){
    			AnyType tmp = a[i];
    			for(j=i;j>=gap&&tmp.compareTo(a[j-gap])<0;j-=gap){
    				a[j] = a[j-gap];
    			}
    			a[j] = tmp;
    		}
    	}
    }

希爾排序的最壞情形分析

使用希爾增量時希爾排序的最壞情形運行時間為O(N²)。

Hibbard提出一個稍微不同的增量序列，它的增量形如1，3，7，...，2^K-1。雖然這些增量幾乎是相同的，但關鍵的區別是相鄰的增量沒有公因子。

使用Hibbard增量的希爾排序的最壞情形運行時間為O(N^3/2)。

Sedgewick提出幾種增量序列，其最壞情形運行時間(也是可以達到的)為O(N^4/3)。其中最好的序列{1，5，19，41，109，...}，該序列中的項或者是9*4ⁱ-9*2ⁱ+1形式，或者是4ⁱ-3*2ⁱ+1形式。