【语法】
一、抛坑提问:海量等级值排序,比较排序下限 n log n——基数排序按个位、十位、百位逐轮分桶收集,不比较任何两个元素,桶数固定时整体线性。
二、底层原理:从最低位开始:每轮按当前位数字分入 0 到 9 十个桶,再按桶序依次收回;位数轮结束后整体有序,稳定性由先入先出保证。
三、正确代码:
错误写法。示例代码如下:
table.sort(levels) -- 比较排序下限nlogn
正确写法。示例代码如下:
local function radix(levels)
local buckets = {}
for _ = 1, 10 do buckets[#buckets + 1] = {} end
local cur, div = levels, 1
for _ = 1, 3 do -- 3位数排3轮
for _, v in ipairs(cur) do
local d = math.floor(v / div) % 10
table.insert(buckets[d + 1], v)
end
cur = {}
for _, b in ipairs(buckets) do
for _, v in ipairs(b) do
cur[#cur + 1] = v -- 按桶序收回
end
end
for i = 1, 10 do buckets[i] = {} end
div = div * 10
end
return cur
end
local sorted = radix({32, 5, 217, 90})
sendmsg(actor, 1, "排序尾值 " .. sorted[#sorted])
四、引擎验证:1 万条三位等级值:比较排序 13 万次比较;基数排序 3 轮分桶 3 万次分配,快 4 倍,结果一致。
五、FAQ:问:位数不一样长怎么办?答:按最长位数定轮数,短数高位按 0 处理自然排在前面。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【游戏】 一、规则机制 隐蔽的坑:折叠列表收起分组时只把子项 setVisible(false),占位还留在原地,列表下半截…
【语法】 一、机制原理 一行代码拆解:a, b = b, a % b。最大公约数的辗转相除法:两数相除取余数,余数再与除数继…
【游戏】 一、规则机制 线上事故:聊天里 @ 了某人,消息混在普通流水里,对方根本没注意,集合迟到的锅全甩给没提醒。点名提醒…
【游戏】 一、规则机制 一行定骨架:text = LANG[cur][key] or LANG.zh[key]。多语言文案的…
【语法】 一、机制原理 抛个坑:模板"$(name),您的$(item)已到账"这种带命名槽位的文案怎么填值?string.…
【游戏】 一、规则机制 抛个坑:横屏竖屏一切界面,控件坐标全按竖屏摆,一旋转错位满屏——适配该怎么做?两条策略配合:界面元素…