希尔排序又称“缩小增量排序”，它的基本思想是：先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对记录进行一次直接插入排序。

      希尔排序的一个特点是：子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。这就使得希尔排序中关键字较小的记录不是一步一步地往前挪动，而是一次按照“增量”的大小跳跃式地往前移，从而使得在进行最后一趟增量为1的插入排序时，序列已基本有序，只要作记录的少量比较和移动即可完成排序，因此希尔排序的时间复杂度较直接插入排序低。

下面以N=10个记录为例分析希尔排序的过程，记录如下：

49   38   65   97   76   13   27   49   55   04

第一趟排序选择增量为Increment=N/2=5，所以：

49   38   65   97   76   13   27   49   55   04

1A                               1B

      2A                               2B

              3A                               3B

                     4A                                4B

                             5A                               5B

第二趟排序选择增量为Increment=Increment/2=2,第一趟排序结果如下：

13   27   49   55   04   49   38   65   97   76

1A          1B         1C          1D          1E

       2A          2B         2C          2D          2E

第三趟排序选择增量为Increment=Increment/2=1,第二趟排序结果如下：

04   27   13   49   38   55   49   65   97   76

第四趟排序选择增量为Increment=Increment/2=0,即第三趟排序即完成整个排序，结果如下：

04   13   27   38   49   49   55   65   76   97

希尔排序算法的实现中，一个很重要的问题是增量序列的选择问题，因为它关系到希尔排序的性能，不同增量序列，性能会相差很远。通常情况下，第一个增量选为Increment=N/2，后面的增量选为Increment=Increment/2；

示例代码1（C语言实现）：

/*********************************************************************
  Author：李冰 date：2014-9-6
  Email：libing1209@126.com
  @array: the pointer to the records
  @num：the length of the records
*********************************************************************/

void shellsort(int array[], int num)
{
	if(array == NULL || num < 0)
		return;	

	int i, j, increment;

	for(increment = num / 2; increment > 0; increment /= 2)  //增量序列
	{
       //直接插入排序
		for(i = 0; i < increment; i++)	
		{
			for(j = i + increment; j < num; j += increment)	
			{
				if(array[j] < array[j - increment])	
				{
					int tmp = array[j];	
					int k = j - increment;
					while(k >= 0 && array[k] > tmp)
					{
						array[k + increment] = array[k]	;
						k -= increment;
					}
					array[k + increment] = tmp;
				}
			}
		}
	}
}

上面给出的希尔排序是完全按照定义给出的，比较繁琐，下面给出简化版本的希尔排序。

示例代码2（C语言实现）：

/*********************************************************************
 Author：李冰 date：2014-9-6
 Email：libing1209@126.com
 @array: the pointer to the records
 @num：the length of the records
*********************************************************************/

void shellsort(int array[], int num)
{
	if(array == NULL || num < 0)
		return;

	int i, j, increment;
	int tmp;

	for(increment = num / 2; increment > 0; increment /= 2){
		for(i = increment; i < num; i++){
			tmp = array[i];	
			for(j = i; j >= increment; j -= increment){
				if(tmp > array[j - increment])	
					array[j] = array[j - increment];
				else
					break;
			}
			array[j] = tmp;
		}	
	}
}

1、希尔排序的增量一般选择为N/2和Increment/2。

2、希尔排序的最坏情形运行时间为O(n^2)。

算法学习之排序算法：希尔排序