希尔排序的历史
希尔排序按其设计者希尔(Donald Shell)的名字命名,该算法由希尔 1959 年公布。
1、希尔排序是基于插入排序的以下两点性质而提出改进方法的:
插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。
但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。
提示:以下是本篇文章正文内容,下面案例可供参考
一、关于希尔排序
1、由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。
2、虽然希尔排序的稳定性比较差,但是希尔排序是冲破二次时间屏障的第一批算法之一。
3、简单说一下希尔排序的思路,就我的理解而言:希尔排序首先先分组【我自己称之为“希尔分组”】,之后把分好的组别分别按照直接插入排序的算法来进行排序。【当我自己学习该算法的时候,我首先先列一个数组,之后分组,然后往纸上写代码,找不同分组的共性,然后统一成一片代码】
4、另外强调一点的是,学习该算法之前必须完全先掌握直接插入排序算法。因为希尔算法实在该基础上进行排序的。
链接: 【直接插入排序算法】.
二、希尔排序的思路
一、希尔排序:“希尔分组”是根据步长【gap】来分的。
二、
假设有一个数组 {1 ,2,3,4,5,6,7,8,9,0}
第一大组:步长gap=length/2=5;
。。。。。分成五小组,每组有2个数
第二大组:gap=gap/2=5/2=2;
。。。。。分成两小组,每组有5个数
第三大组:gap=gap/2=2/2=1;【直到步长gap=1,才算结束】
。。。。。分成一个组,每组有10个数
三、之后就分别对以上各个小组用直接插入排序就可以了。
三、代码实例讲解
代码如下(示例):
void ShellSort(int a[],int length){
int gap; //步长
int i,j,temp,x;
for(gap=length/2;gap>0;gap=gap/2){ //第一个for循环是看需要几次“希尔分组”【注意:每次“希尔分组”直接开始对其进行直接插入排序】
for(i=0;i<gap;i++){ //第二个for循环是对分组后,就这个大组中有几个小组,就循环几次
for(j=i+gap;j<length;j=j+gap){ //剩下两个for循环是对那个小组进行的直接插入排序
for(x=j;x>0;x=x-gap){
if(a[x]<a[x-gap]){
temp=a[x-gap];
a[x-gap]=a[x];
a[x]=temp;
}
else break; //一定记住:再次强调,一旦一不小心忘了带,
//你就需要像我一样进行,长达两三个小时的查错。
}
}
}
}
}
总结
。。目前对于希尔排序我就写这么多,我希望看懂的哥们儿自己再总结一边,然后自己写下这个代码。【你不一定写的和我一毛一样,我就和一大部分人写算法程序不一样,但是思路是一样的。虽然有时候自己根据理解写的代码,有可能编译时间很长,但是这也是一种进步。这说明我可以写出自己的代码了,相当于我自己生了个孩子,我骄傲,即使他不是很完美。【博主是男生】,,,,但是在编程的路上我可以把它变得完美】
【还是那句话,一定要自己根据理解自己干一边代码。我相信我们以后会变得越来越好】
【兄弟姐妹们,加油!!!】