常用12大排序算法之二:二分插入排序(折半插入排序)

2017-04-20 23:39 阅读 1,010 次 评论 0 条

1.二分(折半)插入排序法基本思想

设在顺序表中有一个对象序列V[0],V[1],…,V[n−1]。其中, V[0],V[1],…,V[i−1]是已经排好序的对象。在插入V[i]时,利用二分搜索法寻找V[i]的插入位置。关于二分搜索法在我的博文《查找searching》中有精彩论述,这里只是简要的说明一下二分搜索在二分插入排序中的应用。

第一行是原始数据,第二行是假设已经排好了前i个数据,在排a[i]时,采用二分搜索(查找)的方法在前i个数据中找到合适的位置插入。下面几行是二分查找的步骤,每次将查找的范围缩小一半儿,直到找到合适位置为止,然后在该位置上插入a[i],其余数据往后移动一个位置。

 

2.二分插入排序算法分析

二分搜索比顺序搜索查找快,所以二分插入排序就平均性能来说比直接插入排序要快。
它所需的排序码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。在插入第i个对象时,需要经过log2i+1次排序码比较,才能确定它应插入的位置。 将n个对象用折半插入排序所进行的排序码比较次数比较次数(KCN):∑n−1(log2i+1)≈nlog2n
二分插入排序是一个稳定的排序方法。
当n较大时,总排序码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差。
在对象的初始排列已经按排序码排好序或接近有序时,直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的对象移动次数与直接插入排序相同,依赖于对象的初始排列。

 

3.二分(折半)插入排序法C语言源代码

 

4.二分(折半)插入排序法C++源代码

 

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:常用12大排序算法之二:二分插入排序(折半插入排序) | 算法君

发表评论


表情