Shell排序——软考(五)
2024-09-20 20:45:53
希尔排序是一种插入排序,是对直接插入排序的一种改进,该算法出自于D.L.Shell,因此得名为希尔。Shell排序又名缩小增量排序。
思想
假设初始序列为n个元素,先取一个小于n的整数d1作为第一个增量,然后将全部元素分为d1组。所有距离为d1的倍数的记录放在同一个组中,先在各个组内进行直接插入排序,然后取第二个增量d2 < d1(d2=d1/2)重复上述的分组和排序动作,直到所取的增量di=1,即所有记录放在同一组中进行直接插入排序为止。
注意:一般去d1=n/2,di+1=di/2。如果结果为偶数,则加1,保证di为奇数。
例子
初始序列为[ 6 3 4 1 5 8]
第一步:
d1=6/2=3,将第一个和第四个比较,进行交换,如图所示。
第二步:
d2=d1/2=1.5,由于取奇数,所以d2=1;
此时待排序列仍是无序的。
第三步:
当执行到d=1时,仍然是无序的,此时进行直接插入排序,直接插入排序不再详细叙述,请看上一篇博客:
这样希尔排序才是真正的完成。
代码
void shellsort(int number[]) {
int i, j, k, d, t; d = Len / 2; while(d > 0) {
for(k = 0; k < d; k++) {
for(i = k+d; i < Len; i+=gap) {
for(j = i - d; j >= k; j-=d) {
if(number[j] > number[j+d]) {
t = number[j];
number[j]=number[j+d];
number[j+d]=t;
}
else
break;
}
}
}
}
分析
由上面的例子可以看出,希尔排序的执行时间依赖于增量序列d的选择,由于增量不确定,所以希尔排序是不稳定的排序。其平均时间复杂度是 O(n1.3),最坏情况时间复杂度为 O(n2);空间复杂度为O(1)。
总结:
经过上述分析之后发现shell排序算法的中心在与找到增量,根据增量来找到两两需要比较和交换的值,最后再进行一次直接插入运算,这样就算是大功告成了。
最新文章
- [转载]C/C++框架和库
- LeetCode之412. Fizz Buzz
- SQL疑难问题
- MicroERP数据初始化SQL脚本
- CSS样式-文字超出宽部分用省略号代替
- Spring Setter Injection and Constructor Injection
- JSP中显示用户信息
- MSBuild和Jenkins搭建持续集成环境
- lintcode:最大子数组II
- UIWebView 获取html标题
- Cocos2d-x课程大纲/学习路线
- mac下mysql5.6字符集设置
- winform DataGridView 导出到Excel表格 分类: WinForm 2014-07-04 10:48 177人阅读 评论(0) 收藏
- Linux Namespaces机制——实现
- pycharm(Python编辑器)的激活
- Dubbo服务启动脚本
- 54. Spiral Matrix以螺旋顺序输出数组
- Google TensorFlow 机器学习框架介绍和使用
- 通过python将xml文件转换成html文件
- 3.Spring Cloud初相识--------Ribbon客户端负载均衡
热门文章
- appium 弹窗处理
- 四、Spring中使用@Conditional按照条件注册Bean
- springboot继承JpaRepository报org.springframework.beans.factory.NoSuchBeanDefinitionException: No qualif
- [转帖]熬夜变傻有科学依据,人类睡觉时会被“洗脑”,科学家首次拍下全程 | Science
- ModelSerializer组件
- Codeforces VP/补题小记 (持续填坑)
- .NET Core 中三种模式依赖注入的生命周期。
- 和我一起,重零开始学习Ant Design Pro开发解决方案(二)部署示例项目
- 【转载】C#中List集合使用Remove方法移除指定的对象
- css文字的渐变色设置