易语言折半插入排序(二分法插入排序)

算法思想:

过程同直接插入排序,仅仅是在找插入位置时,不是顺序遍历,而是二分法查找位置。因为:如果要找地 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
.计次循环尾 ()
复制数组 (参数组, 排序变量)

发布日期:

所属分类: 易语言 标签: