用C语言实现希尔排序
程序员文章站
2022-03-15 23:45:30
...
希尔排序是直接插入排序的改良版,比直接插入排序更加高效,它是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
形象地说就是像军训或者体育课初次进行排队的步骤:
- 教官/老师让所有人排成一队,按1 2 3 1 2 3循环报数(此时下标的一定增量就是3)
- 报到相同数字的就重新组成一队(分组,但事实上不会分成三组,只是逻辑上进行分组,相当于打上标记)
- 在每个重新组成的组里按身高进行排序(直接插入排序)
- 改变增下标增量d(一般是递减的,d/2),重复以上步骤
- 直到下标增量变为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;
}
}
}
上一篇: 希尔排序(C语言实现)