| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 1232 人关注过本帖, 2 人收藏
标题:有没有兴趣玩下排序算法
只看楼主 加入收藏
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:33
帖 子:1083
专家分:3403
注 册:2011-12-3
收藏
得分:0 
回复 18楼 xianfajushi
理论上分析 你写的排序算法是慢于原始插入排序的
因为你的算法多了一个没必要的 二分查找
你用二分查找定位待插入数据应该插入的位置
然后把插入位置后面的每一个元素都后移一位 完成插入

原始插入算法 直接在每一个元素后移的操作中截图一个判断语句确定是不是合适的插入位置
二分查找的全部工作 只等于原始插入算法中一个if判断
所以你的算法慢于原始插入算法

===============================================
上面的思路是错误的
你的二分查找有点价值
原始插入算法 后移循环每次都要判断
后移n次 总执行 n次判断 + n次赋值
二分查找能执行较少次数定位到插入点
后移n次 总执行 二分查找次数*单次查找指令 + n次赋值
因为二分查找是一个对数级别的复杂度的算法 虽然单次查找指令较多
但在数据规模较大的情况下 这种定位方式有更好的效果
的确能算是对原始插入算法的一个优化

===============================================
另一个需要注意的地方是
原始插入排序是一个稳定排序
你目前这个排序算法是不稳定的
应用场景略有区别





[此贴子已经被作者于2020-10-10 14:32编辑过]


https://zh.
2020-10-10 11:29
快速回复:有没有兴趣玩下排序算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.127205 second(s), 9 queries.
Copyright©2004-2020, BCCN.NET, All Rights Reserved