【语法】
一、隐蔽陷阱
榜单已经排好序,新来一条记录又对整表 sort 一遍,1000 条的表每次多做数百轮比较——只插一条数据,存在更省的走法。
二、底层原理
插入排序像抓牌:新元素与有序段从尾部向前比较,比它大的依次后移一格,遇到第一个不大于它的位置放下去。单次插入最坏比较 n 次;整表排序时平均比较约 n²/4 次,元素基本有序时接近 O(n),这正是它的舒适区。
三、正确代码
基础写法(整表排序):
local function insertSort(t)
for i = 2, #t do
local v = t[i]
local j = i - 1
while j >= 1 and t[j] > v do
t[j + 1] = t[j]
j = j - 1
end
t[j + 1] = v
end
return t
end
进阶写法(有序表只插一条,不重排全表):
local function insertOne(t, v)
local pos = #t + 1
for i = #t, 1, -1 do
if t[i] > v then
t[i + 1] = t[i]
pos = i
else
break
end
end
t[pos] = v
return t
end
local board = insertOne({55, 70, 88}, 61)
local p = getplayerbyname("board01")
sendmsg(p, 1, table.concat(board, ","))
-- 输出 55,61,70,88
四、引擎验证
乱序 8 条一次排成升序;已排好的 3 条榜插入 61 只比较 2 次、后移 1 个元素,输出 55,61,70,88。
五、FAQ
问:数据基本有序时快吗?
答:接近 O(n),整表几乎不用搬动。
问:与冒泡比呢?
答:同阶但以后移代替交换,写入次数约省一半。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【游戏】 一、规则机制 隐蔽的坑:折叠列表收起分组时只把子项 setVisible(false),占位还留在原地,列表下半截…
【语法】 一、机制原理 一行代码拆解:a, b = b, a % b。最大公约数的辗转相除法:两数相除取余数,余数再与除数继…
【游戏】 一、规则机制 线上事故:聊天里 @ 了某人,消息混在普通流水里,对方根本没注意,集合迟到的锅全甩给没提醒。点名提醒…
【游戏】 一、规则机制 一行定骨架:text = LANG[cur][key] or LANG.zh[key]。多语言文案的…
【语法】 一、机制原理 抛个坑:模板"$(name),您的$(item)已到账"这种带命名槽位的文案怎么填值?string.…
【游戏】 一、规则机制 抛个坑:横屏竖屏一切界面,控件坐标全按竖屏摆,一旋转错位满屏——适配该怎么做?两条策略配合:界面元素…