第二种实现方法的改进

上面的代码中需要三个for循环，因为我们是循环对每个子序列进行插入排序的，实际上我们还可以这样做：对每个子序列交叉进行排序。比如，第1个子序列中的第2个元素A5（A5表示它在总序列A中的位置序号是5，下同）刚进行完插入排序操作，便接着对第2个子序列中的第2个元素A6进行插入排序操作。这样我们就可以少写一个for循环，但实际比较的次数还是相同的，只是代码更加简洁。如下：

/*
在第二种代码的形式上继续精简代码
交叉进行各个子序列的插入排序
*/
void Shell_Insert2_1(int *arr,int len,int ader)
{
	int i,j;
	//交叉对ader个子序列进行插入排序
		for(i=ader;i
        
         =0 && arr[j]>arr[j+ader];j-=ader)
			{
				//交换元素数值
				//由于arr[j]不等于arr[j+1]，
				//因此可以安全地用该交换方法
				arr[j]^=arr[j+ader];
				arr[j+ader]^=arr[j];
				arr[j]^=arr[j+ader];
			}
}
        

第三种实现方法

/*
第三种形式的代码
对长为len的数组进行一趟增量为ader的插入排序
本算法在插入排序算法的第二种实现形式上进行修改得到
*/
void Shell_Insert3(int *arr,int len,int ader)
{
	int i,j,k;
	//循环对ader个子序列各自进行插入排序
	for(k=0;k
        
         =k && arr[j]>key;j-=ader)
					arr[j+ader] = arr[j];
				arr[j+ader] = key;
			}
}
        

第三种实现方法的改进

我们可以对该方法做出同样的改进，对各个子序列进行交叉排序，代码如下：

/*
在第三种代码的形式上继续精简代码
交叉进行各个子序列的插入排序
*/
void Shell_Insert3_1(int *arr,int len,int ader)
{
	int i,j;
	//对ader子序列交叉进行插入排序
	for(i=ader;i
        
         =0 && arr[j]>key;j-=ader)
				arr[j+ader] = arr[j];
			arr[j+ader] = key;
		}
}
        

希尔排序的时间复杂度根据选择的增量序列不同会有所不同，但一般都会比n*n小（序列长度为n）。

在选择增量序列时，应使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须为1.

看如下两个增量序列：

n/2、n/4、n/8...1

1、3、7...2^k-1

第一个序列称为希尔增量序列，使用希尔增量时，希尔排序在最坏情况下的时间复杂度为O(n*n)。

第二个序列称为Hibbard增量序列，使用Hibbard增量时，希尔排序在最坏情况下的时间复杂度为O(n^3/2)。

经验研究表明，在实践中使用这些增量序列要比使用上面两个增量序列的效果好的多，其中最好的序列是

{1、5、9、41、109...}

该序列中的项或是9*4^i-9*2^i+1，或是4^i-3*2^i+1。

希尔排序的性能是完全可以接受的，即时是对数以万计的n来说也是如此。编程的简单特点使得它成为对适度的大量输入数据进行排序时经常选用的算法。

完整代码下载