图文讲解：5、希尔排序之c语言实现

排序算法之希尔排序

希尔排序算是直接插入排序的优化版本（所以在此之前有学过直接插入排序的话会更有助于理解希尔排序），那它的优化过程及其原理是怎样的呢，来！上图（排序方式以从小到大为例）

大家看过上图之后，整个过程应该不难理解，但可能会有这样几个疑惑： 1、为什么会拆分成两组，每次拆分成的新数组个数num由什么决定？ 2、数组不断地拆分，排序，合并，再拆分，排序，合并…，那么这个小过程（拆分，排序，合并）会执行几次呢？

而这也就是希尔排序的特点——一般来说，对于一个长度为length的数组，用length不断地除以2并取整(注意！这里是把结果取整（如：7/3=2）)，直到商为1，例如，4连续两次除以2可得到1，7连续两次除以2可得到1，8则连续三次除以2可得到1，也就是length连续除以n次2可得到1，则上述小过程执行n次，且每次拆分得到的新数组个数num=length/(2^n)。

还有一个很重要的一点，每次由目标数组拆分而形成的新数组有一个特点，那就是数组里面的元素之间的下标差（估且称之为距离distance）是变动的，且这个距离distance会大于或等于1。那如何确定这个距离distance呢，继续以上图为例：

通过上图可以知道，且每个小数组里面的元素的间距distance也等于 length/(2^n)，综上，每次拆分形成的小数组的个数num等于每个小数组里面的元素的间距distance（即num=distance）。

c代码实现如下

#include<stdio.h>
void shellsort(int *a,int length)
{
          
   
	int LENGTH=length;
 	while(LENGTH>1)    //决定拆分几次(及循环几次)
 	{
          
   
     	for(int b=0;b<LENGTH/2;b++)   //决定拆分成几个子数组(及循环几次)
   	 {
          
   
       		 for(int i=LENGTH/2+b;i<length;i+=LENGTH/2)   //从这个for循环开始，里面的实现原理和直接插入排序算法相似
        	 {
          
   
            		int value=a[i];
            		for(int j=i-LENGTH/2;j>=b&&value<=a[j];j-=LENGTH/2)
            		{
          
   
             			 a[j+LENGTH/2]=a[j];
            		}
            		a[j+LENGTH/2]=value;
        		}
    		 }
   		 LENGTH/=2;
	 }
}
int main()
{
          
   
	int a[]={
          
   2,4,1,3};
 	int length=sizeof(a)/sizeof(int);
 	shellsort(a,length);
 	for(int i=0;i<length;i++)
  	printf("%d ",a[i]);
	printf("
");
 	return 0;
}