希尔排序(图解+代码)

标签: 排序

希尔排序


如图: 我们来看下希尔排序的基本步骤,在此我们选择增量gap=length/2,缩小增量继续以gap = gap/2的方式,这种增量选择我们可以用一个序列来表示,{n/2,(n/2)/2...1},称为增量序列

图中有10个数,所以第一趟增量就设为10/2=5;看图中第一趟排序,颜色相同为一组,每组进行比较,可以看到,这十个数被分成了五组        [9,4] [1,8] [2,6] [5,3] [7,5],     然后对这五组分别进行直接插入排序

第二趟继续进行,缩小增量为5/2=2;这时候可以看到这些数被分成了两组[4,2,5,8,5] [1,3,9,6,7],继续分别对这两组进行直接插入排序。

第三趟 缩小增量为 2/2=1;这时候,只需要对这些数字进行微调就可以满足要求。

 

希尔排序的代码部分:(C语言版)

#include <stdio.h>
int main(){
	int i=0,gap=0,k=0,j=0,t=0;
	int n=0;
	scanf("%d",&n);     
	int a[n];
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}                                        //输入想要排序的数 
	for(gap=10/2;gap>0;gap=gap/2){           //设置增量,每次都是gap/2;
		for(k=gap;k<10;k++){
			t=a[k];                  //将要插入的数放入t中     
			j=k-gap;
			while(j>=0&&t<a[j]){     //t若比前面位置上的数字小,前面数就要后移
				a[j+gap]=a[j];   //后移
				j=j-gap;         //找到前面一个位置上的数,反正这步我推了好久
			} 
	    a[j+gap]=t;                          //t插入这个位置
	    }
    }
printf("%d",a[0]);                               //就是为了最后不留空格才这样输出
 for(j=1;j<10;j++){
	  printf(" %d ",a[j]);
    }
 return 0;
}

总结:

我们上面选择的增量序列{n/2,(n/2)/2...1}(希尔增量),其最坏时间复杂度依然为O(n2),一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n3/2)。

原文链接:加载失败,请重新获取