排序(Sort)

排序(Sort)是将无序的记录序列（或称文件）调整成有序的序列。

排序的目的是方便我们队数据查询记录、修改记录等操作。

排序的分类

按稳定性可分为稳定排序和非稳定排序，按待排序数据的存储位置又可分为内排序和外排序。

截止目前，各种内排序方法可归纳为以下五类：
（1）插入排序
（2）交换排序
（3）选择排序
（4）归并排序
（5）基数排序。

本次介绍的是简单常用的shell排序算法，shell排序属于插入排序算法！

shell排序算法

Shell（希尔）排序又称“缩小增量”排序，1959年由D.L.Shell提出。希尔发现：直接插入排序中，key比较次数及记录移动次数会比较大，若将待排序文件按某种次序分隔成若干个子文件，对各子文件“跳跃”式的排序，然后调整子文件个数，逐步对原文件排序，这样总的key比较次数尤其是记录移动次数也许会大大降低

这是一种跳跃式的排序方法，它使得文件逐步有序，从而克服了一次排序时记录成片移动现象。

算法思路：数据序列中相隔增量d（如令d=n/2）的记录组成一个个子序列，对各子文件插入排序；然后缩小增量d（如令d=d/2），再将相隔新增量的记录组成一个个子序列，对诸子序列排序，……，直到增量d=1为止，排序完毕。

  

   

    

     

    
    

     

      void shellsearch(int a[])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
      int i,j,tmp;
     
    
   

    

     

    
    

     
      int d;
     
    
   

    

     

    
    

     
      for(d = N/2; d > 0; d /= 2){
     
    
   

    

     

    
    

     
	    for(i = d; i < N; i++){
     
    
   

    

     

    
    

     

      		  tmp = a[i];
     
    
   

    

     

    
    

     
		  for(j = i-d;j >= 0; j -= d)
     
    
   

    

     

    
    

     
			if(tmp < a[j])
     
    
   

    

     

    
    

     

      			      a[j+d] = a[j];
     
    
   

    

     

    
    

     
			else
     
    
   

    

     

    
    

     
			      break;
     
    
   

    

     

    
    

     

      		  a[j+d] = tmp;
     
    
   

    

     

    
    

     

      	    }
     
    
   

    

     

    
    

     

      	    show(a);
     
    
   

    

     

    
    

     

            }
     
    
   

    

     

    
    

     

      }
     
    
  
 

过程分析

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/81197169