【排序算法系列】希爾排序

希爾排序的概述：

       a[0]...a[n-1] 将n個元素的數組，進行分組。同組内元素的索引相差gap(我們稱之為步長)。

第一次步長計算方式為 gap = n/2，第二次步長計算方式為 gap = gap/2...依次類推，直到gap = 0。每一次，對每個分組内的元素進行直接插入排序。最後對整一個數組進行直接插入排序，由于整個數組已經基本有序了，是以最後執行直接插入排序效率非常高。

       對于以下這個數組我們來模拟希爾排序的整個過程，以更形象地了解希爾排序的原理

     49   38   65   97   26   13   27   49   55   4

        第一次：gap = 10 / 2 = 5

49	38	65	97	26	13	27	49	55	4
A1	A2
B1	B2
C1	C2
D1	D2
E1	E2

         分組A執行直接插入排序後：13  49

         分組B執行直接插入排序後：27  38

         分組C執行直接插入排序後：49  65

         分組D執行直接插入排序後：55  97

         分組E執行直接插入排序後：4    26

13	27	49	55	4	49	38	65	97	26
A1	A2
B1	B2
C1	C2
D1	D2
E1	E2

執行完第一次的每個分組排序後：得到數組 13，27，49，55，4，49，38，65，97，26

        第二次：gap = 5 / 2 = 2 

13	27	49	55	4	49	38	65	97	26
A1	A2	A3	A4	A5
B1	B2	B3	B4	B5

        分組A執行直接插入排序後：4   13   38  49  97

       分組B執行直接插入排序後：26  27  49  55  65

4	26	13	27	38	49	49	55	97	65
A1	A2	A3	A4	A5
B1	B2	B3	B4	B5

執行完第二次的每個分組排序後，得到數組4  26  13   27  38   49   49   55   97  65

        第三次：gap = 2 / 2 = 1

4

26

13

27

38

49

49

55

97

65

         第三次，就隻有一個分組了，我們可以看到整個數組已基本有序了。對整個數組進行直接插入排序，就得到了一個拍好序的數組了。

4

13

26

27

38

49

49

55

65

97

        第四次：gap = 1 / 2 = 0

        結束

根據上述模拟的希爾排序過程給出希爾排序代碼：

   從上述分析我們可知gap為多少，就表示每次有多少個分組。

int n = array.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
	// 步長是多少，就有多少個分組
	for (int m = 0; m < gap; m++) {
		// 對每個分組進行直接插入排序
		for (int i = m + gap; i < length; i += gap) {
			int temp = array[i], j;
                        // 一邊判斷temp(為array[i]的值)是否小于array[j]，若小于array[j],則
                        //将array[j]後移一位
			for (j = i - gap; j >= 0 && temp < array[j]; j -= gap) {
				array[j + gap] = array[j];
			}
			array[j + gap] = temp;
		}
	}
}
           

對于嚴格定義的希爾排序稍作改進

上述給出的代碼看似有些繁瑣，我們可以稍作改進，觀察發現，每次對于分組的排序，都是要将該分組全部排序完後，再進行下一個分組的排序的。我們也可以這樣做，以上述例子中，第二次為例，

13,27,49,55,4,49,38,65,97,26

13	27	49	55	4	49	38	65	97	26
A1	A2	A3	A4	A5
B1	B2	B3	B4	B5
gap-1	gap	gap+1	gap+2	gap+3	gap+4	gap+5	gap+6	gap+7

       首先我們從gap開始，即從A2開始，此時對A1,A2做直接插入排序，接下來，gap+1即取B2，那麼對B1，B2做直接插入排序，接下來gap+2即取A3，對A1,A2,A3做直接插入排序，接下來取gap+3即B3，做直接插入排序。。。依次類推，直到gap+9即B5對B1，B2，B3，B4，B5做直接插入排序。

        不好了解的話，換種說法，還是以第二次排序為例，原來是每次從A1到A5，從B1到B5，可以改成從A2開始，先和A1比較，然後取B2與B1比較，再取A3與前面自己組内的資料比較…….。這種每次從數組第gap個元素開始，每個元素與自己組内的資料進行直接插入排序顯然也是正确的。

int n = array.length;
// 共需進行分組排序次數
for (int gap = n / 2; gap > 0; gap /= 2) {
	// 從gap個元素開始，與組内前面的元素進行直接插入排序
	for (int i = gap; i < n; i++) {
		int j = i - gap, temp = array[i], m;
		for (; j >= 0 && temp < array[j]; j -= gap);
		if (j + gap < i) {// 如果j + gap >= i表示無需移位
			for (m = i - gap; m >= j + gap; m -= gap) {
				array[m + gap] = array[m];
			}
			array[j + gap] = temp;// j+gap是需要插入的位置
		}
	}
}
           

 再将直接插入排序部分，改用邊判斷，邊移位，下面的代碼就簡潔多了

int n = array.length;
// 共需進行分組排序次數
for (int gap = n / 2; gap > 0; gap /= 2) {
	// 每次從第gap個元素開始
	for (int i = gap; i < n; i++) {
		int j, temp = array[i];
		for (j = i - gap; j >= 0 && temp < array[j]; j -= gap) {
			array[j + gap] = array[j];
		}
		array[j + gap] = temp;
	}
}
           

對于直接插入排序，可以參考我上一篇的文章http://jaychang.iteye.com/blog/2261560