欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

用C语言实现希尔排序

程序员文章站 2022-03-15 23:45:30
...

希尔排序是直接插入排序的改良版,比直接插入排序更加高效,它是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
用C语言实现希尔排序

形象地说就是像军训或者体育课初次进行排队的步骤:

  1. 教官/老师让所有人排成一队,按1 2 3 1 2 3循环报数(此时下标的一定增量就是3)
  2. 报到相同数字的就重新组成一队(分组,但事实上不会分成三组,只是逻辑上进行分组,相当于打上标记)
  3. 在每个重新组成的组里按身高进行排序(直接插入排序)
  4. 改变增下标增量d(一般是递减的,d/2),重复以上步骤
  5. 直到下标增量变为1,全队排序完成

以上是希尔排序的基本思想,问题是如何用代码实现这个理解起来不算难的算法;
首先,已数组排序为例,希尔算法是按照下标一定增量d开始每一次循环的,而且每次下标一定是递减的,直到d<=1,在希尔算法中下标增量d递减的方式是减半,即d=d/2,那么初始的d如果设置为最大,即数组的长度n,那样第一次下标分组就越界了,要保证第一次分组能包含数组里所有的数,很容易就想到d应该等于数组长度的一半于是框架就是

for(d=n/2; d>=1; d=d/2){
	对每一组都进行插入排序
}

此时考虑如何对每一组进行插入排序,只需将每个下标为i的数与下标为i+d的数比较,大的排后边,小的排左边,同时注意下标。
这里提供一种实现方式

hellsort ( int a[],  int n){	
        for(d=n/2; d>=1; d=d/2){
              for( i=0+d; i<n; i++){        
              		t=a[i];
                    for(j=i-d; j>=0 && a[j]>t; j=j-d)  {a[j+d]=a[j] ;}
                    a[j+d]=t;             
              }
         }
}