首页 > 代码库 > 希尔排序算法——缩小增量法排序
希尔排序算法——缩小增量法排序
希尔排序——1959年shell提出而得名,也称为缩小增量排序算法,它是直接插入排序的改进,效率比较高,适合于中小规模的排序。
具体的算法实现步骤为:首先得知道直接插入排序的算法,然后就是选择增量给原数列进行分组,对每个分得的小组进行直接插入排序便可,然后逐渐减小这个增量,依然进行新的分组的直接插入排序,直到增量为1,此时数列便是有序数列了。具体的代码如下:
首先是对特定的增量的分组的直接插入排序:
void _insert(int *A,int d,int length) //d为增量 { int temp=0; int j=0; for(int i=d;i<length;i++) { temp=A[i]; for(j=i-d;j>=0 && A[j]>temp;j-=d) { A[j+d]=A[j]; } A[j+d]=temp; } }然后就是选择增量来循环调用上面的函数便可:
void _shell(int *A,int length) { for(int i=length/2;i>0;i=i/2) { _insert(A,i,length); } }下面编写测试代码:
void main() { int ia[]={0,4,2,1,9,2}; int length=sizeof(ia)/sizeof(int); _shell(ia,length); for(int i=0;i<length;i++) { cout<<ia[i]<<" "; } }测试结果如下:
希尔排序算法——缩小增量法排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。