文章目录[隐藏]
折半插入排序又称二分法插入排序。和直接插入排序算法不同的是：在插入元素时，利用折半搜索法寻找插入位置。
算法思想：
过程同直接插入排序，仅仅是在找插入位置时，不是顺序遍历，而是二分法查找位置。因为：如果要找地 i 个元素的插入位置，那么第 i-1 个元素是已经有序的，可以用二分查找来寻找位置。
算法分析：
时间复杂度：折半插入排序仅仅是减少了比较元素的次数，约为O(nlogn)，而且该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数n；而元素的移动次数没有改变，它依赖于待排序表的初始状态。因此，折半插入排序的时间复杂度仍然为O(n²)，但它的效果还是比直接插入排序要好。
空间复杂度：排序只需要一个位置来暂存元素，因此空间复杂度为O（1）
二分法插入排序模块源码
.版本 2
.子程序 二分法插入排序
.参数 参数组, 整数型, 数组
.局部变量 排序变量, 整数型, , "0"
.局部变量 当前查找次数, 整数型
.局部变量 数据成员数量, 整数型
.局部变量 插入位置, 整数型
.局部变量 当前数据, 整数型
.局部变量 当前分区成员数, 整数型
.局部变量 当前位置, 整数型
.局部变量 中间位置, 整数型
.局部变量 中间数据, 整数型
数据成员数量 ＝ 取数组成员数 (参数组)
.如果真 (数据成员数量 ≤ 0)
返回 ()
.如果真结束
.计次循环首 (数据成员数量, 当前查找次数)
当前位置 ＝ 1
当前分区成员数 ＝ 取数组成员数 (排序变量)
当前数据 ＝ 参数组 [当前查找次数]
' 本源码来自易语言资源网(www.5A5X.com)
.判断开始 (当前查找次数 ＝ 1)
插入成员 (排序变量, 1, 当前数据)
' 加入第一个成员
到循环尾 ()
.判断 (当前数据 ≥ 排序变量 [当前分区成员数])
插入成员 (排序变量, 当前分区成员数 ＋ 1, 当前数据)
' 用无序数据比较数组的最大位
到循环尾 ()
.判断 (当前数据 ≤ 排序变量 [1])
' 用无序数据比较数组的最小位
插入成员 (排序变量, 1, 当前数据)
到循环尾 ()
.默认
.判断结束
' 条件成立，继续拆，直至找到“当前数据”等于“中间数据”或者直至当前的查找区间为空（即失败）为止。
.判断循环首 (当前位置 ＜ 当前分区成员数 － 1)
' 二分排序的结构
' 取有序区中间位置，将分区减半进行查找
中间位置 ＝ (当前位置 ＋ 当前分区成员数) ＼ 2
' 取有序区中间位置的数据
中间数据 ＝ 排序变量 [中间位置]
.如果真 (当前数据 ＝ 中间数据)
当前位置 ＝ 中间位置
跳出循环 ()
.如果真结束
.如果 (当前数据 ＜ 中间数据)
当前分区成员数 ＝ 中间位置
' 其插入位置在左分区
.否则
当前位置 ＝ 中间位置
' 其插入位置在右分区
.如果结束
.判断循环尾 ()
插入位置 ＝ 当前位置 ＋ 1
插入成员 (排序变量, 插入位置, 当前数据)
' 插入位置 ＝ 1
.计次循环尾 ()
复制数组 (参数组, 排序变量)