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

希尔排序的概述：

       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
0	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