（二）希爾排序法

一、簡介

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。

希爾排序是基于插入排序的以下兩點性質而提出改進方法的： 1、插入排序在對幾乎已經排好序的資料操作時，效率高， 即可以達到線性排序的效率 2、對于大規模亂序數組插入排序很慢，因為它隻會交換相鄰的元素，是以元素隻能一點一點地從數組的一端移動到另一端。

希爾排序簡單地改進了插入排序，交換不相鄰的元素以對數組的局部進行排序，并最終用插入排序将局部有序的數組排序。（先将整個大數組基本有序，再對大數組來一次插入排序）

思想：使數組中任意間隔為h的元素都是有序的。這樣的數組被稱為h有序數組。在進行排序時，如果h很大，我們就能将元素移動到很遠的地方，為實作更小的h有序創造友善。

二、步驟

先取一個小于n的整數d1作為第一個增量，把檔案的全部記錄分組。所有距離為d1的倍數的記錄放在同一個組中。先在各組内進行直接插入排序；然後，取第二個增量d2<d1重複上述的分組和排序，直至所取的增量dt=1（dt< d(t-1)< …<d2<d1），即所有記錄放在同一組中進行直接插入排序為止。

三、示例

假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進行排序，我們可以通過将這清單放在有5列的表中來更好地描述算法，這樣他們就應該看起來是這樣：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
複制代碼
           

然後我們對每列進行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
複制代碼
           

将上述四行數字，依序接在一起時我們得到： [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ] 這時10已經移至正确位置了，然後再以3為步長進行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
複制代碼
           

排序之後變為：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
複制代碼
           

最後以1步長進行排序（此時就是簡單的插入排序了）。

四、代碼實作

template<typename T> //可以使用整數或浮點數作為元素，如果使用類(class)作為元素則需要重載大于(>)運算符。
void sort(T arr[], int len) {
	int gap, i, j;
	T temp;
	for (gap = len >> ; gap > ; gap >>= )	// gap為當時增量
		/* 同時做gap個序列排序 */
		for (i = gap; i < len; i++) {			
			temp = arr[i];		// 儲存待插入記錄Ri
                        int j = ; //有序區中待比較元素的下标，初始時，從有序區中最後一個元素開始比較起
			/* 按間隔gap尋找插入點 */ 
			for (j = i - gap; j >=  && arr[j] > temp; j -= gap)	// 對步長為 gap 的元素組進行排序
				arr[j + gap] = arr[j];	// 大記錄後移
			arr[j + gap] = temp;	// 插入記錄Ri
		}
}

int main()
{
	int a[] = { ,,,,,,,,, };
	sort(a,);
	for (int i = ; i < ; i++) {
		cout << a[i] << " ";
	}
}
複制代碼
           

五、評價

穩定性：不穩定。我們知道一次插入排序是穩定的，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，即希爾排序中相等資料可能會交換位置。

時間性能：希爾排序的平均時間複雜度為O(nlog2n)

适用範圍：中等大小規模表現良好，對規模非常大的資料排序不是最優選擇。不适用于鍊式結構

六、參考資料

排序:直接插入+希爾排序 希爾排序 排序:插入排序之希爾排序(縮小增量排序)

白話經典算法系列之三 希爾排序的實作 中國MOOC大學-程式設計基礎-6.問題解決和算法基礎3