折半插入排序算法的详细解析
发布时间
阅读量：
阅读量
折半插入排序算法的时间复杂度：O(nlogn)
折半插入排序基于二分查找的思想，在一个已经有序的序列中确定新元素的合适位置后进行插入操作。如图1所示，在包含n个数据项的情况下，默认前i-1项为有序序列，在第i步需要将当前数据项放置到正确的位置上。该算法分为两个主要阶段：一是确定待插入数据项应处的位置；二是完成实际的数据项插入操作。
图1 插入排序示意图
为了便于确定元素a[i]的合适位置, 我们将定义两个变量low和high作为下标索引, 其中low初始化为数组的第一个元素, high初始化为数组的倒数第二个元素, 计算中点mid=(low + high)/2.
还没有任何评论哟~