希尔排序

 基本思想：先将整个待排序记录序列分割成为若干个序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序！

因为关键字是跳跃式的往前移动，因为它是不稳定的。

  

   

    

     

    
    

     

      # include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      # define MAXSIZE 20
     
    
   

    

     

    
    

     

      typedef int KeyType;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct 
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	KeyType r[MAXSIZE+1];
     
    
   

    

     

    
    

     
	int length;
     
    
   

    

     

    
    

     

      }SqList;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void CreateSqList(SqList &L)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int i,n;
     
    
   

    

     

    
    

     
	printf("请输入待排序数据的长度:");
     
    
   

    

     

    
    

     
	scanf("%d",&n);
     
    
   

    

     

    
    

     
	printf("请输入待排序的数据:");
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	for (i=1;i<=n;i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		scanf("%d",&L.r[i]);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	L.length = n;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void Display(SqList &L)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int i;
     
    
   

    

     

    
    

     
	for (i=1; i<=L.length; i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		printf("%d ",L.r[i]);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("\n");
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void InserSort(SqList &L)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int i,j,k=0;
     
    
   

    

     

    
    

     
	int inc = L.length ;
     
    
   

    

     

    
    

     
	do
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		inc = inc/3 + 1;//inc为增量
     
    
   

    

     

    
    

     
		for (i=inc+1; i<=L.length; ++i)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			if (L.r[i]<L.r[i-inc])//小于前面的数，L.r[i]插入有序增量子表
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

       L.r[0] = L.r[i];//暂存在L.r[0]
     
    
   

    

     

    
    

     
 for (j=i-inc; j>0 && L.r[0] <L.r[j];j-=inc)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       L.r[j+inc] = L.r[j];//记录后移，查找插入位置
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       L.r[j+inc] = L.r[0];//插入到正确的位置
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 printf("第%d趟排序结果为: ", ++k);
     
    
   

    

     

    
    

     

       Display(L);
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}while (inc>1);//inc的值最终为1
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(void)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	SqList L;
     
    
   

    

     

    
    

     

      	CreateSqList(L);
     
    
   

    

     

    
    

     

      	InserSort(L);
     
    
   

    

     

    
    

     
	printf("最后的排序结果是:");
     
    
   

    

     

    
    

     

      	Display(L);
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

希尔排序的分析是一个复杂的问题，因为它的时间是取“增量”序列的函数，这涉及到一些数学上尚未解决的难题。

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/6835039