首页 > 代码库 > 八大排序算法学习笔记：插入排序（二分插入排序）
八大排序算法学习笔记：插入排序（二分插入排序）
二分插入排序 也称折半插入排序，
1、基本思想:设数列[0....n]分为两部分一部分是[0...i]为有序序列，另一部分是[i+1.....n]为无序序列，从无序序列中取一个数 x ,利用二分查找算法找到 x 在有序序列中的插入位置并插入，有序序列还是有序的，接下来重复上述步骤，直到无序序列全部插入有序序列 ，这是整个序列只剩下有序序列即有序了。
2、代码：
<script src="https://code.csdn.net/snippets/398551.js" type="text/javascript"></script>
3、复杂度：
用二分插入排序所要进行的总比较次数为O(lgn)，当n较大时，比直接插入排序的最大比较次数小得多，但大于最小比较次数。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。