【语法算法】Lua+table.sort回调：比较器的约定本质

【语法算法】

table.sort(t, cmp) 的第二个参数只给了你一个约定：cmp(a, b) 返回 true 表示 a 应排在 b 前面。就这一句话，却是排序类 bug 的头号来源——把"小于"写成"小于等于"，排序直接抛异常或者结果错乱。今天把比较器的约定拆到最底：严格弱序是什么、sort 内部怎么用它、平局怎么补决胜键、以及写出可靠比较器的四条军规。

一、约定本体：严格弱序

比较器的正确形态是 cmp(a,b) = a.score < b.score 这类严格小于关系。数学上它要求满足严格弱序（strict weak order）两条：非自反——cmp(a,a) 必须为 false；非对称——若 cmp(a,b) 为 true，则 cmp(b,a) 必须为 false。一旦写成 <=，cmp(a,a) 变 true，内部排序的分区指针会越过彼此，轻则结果错乱，重则直接报 invalid order function for sorting。这个报错不是"偶发 bug"，是约定被破坏的直接证据——看到它先检查比较器里有没有 <=、>=，或者依赖浮点相等判断的多级比较（浮点 NaN 参与任何比较都是 false，会把全序搅成非序，排序前要过滤 NaN）。还有一个隐蔽来源：比较器里读了排序中途被修改的字段——回调函数里触发别的逻辑改了 score，等于边开车边换轮子。

local players = {
    { name = "A", score = 90 }, { name = "B", score = 90 }, { name = "C", score = 70 },
}
-- 正确: 严格小于 + 决胜键打破平局
table.sort(players, function(a, b)
    if a.score ~= b.score then return a.score > b.score end
    return a.name < b.name           -- 平局用第二键, 结果唯一
end)
-- 错误示范: return a.score >= b.score  → invalid order function

二、平局、稳定性与"确定性排序"

Lua 官方文档明确：table.sort 不保证稳定——两个 cmp 视为相等的元素，顺序在实现间、甚至同一实现的不同输入规模下都可能不同（底层是快排变体，输入量小走插入排序、量大走快排，小样本"看起来稳定"纯属巧合）。业务要"同分按报名时间先后"，就必须像上面那样在比较器里自己补决胜键，把"相等"收窄成"不相等"，排序结果才唯一可复现——排行榜、战报回放这类要求"两次排序结果完全一致"的场景，决胜键不是优化而是必需。另一个冷知识：5.3 及更早版本对带数组洞的表排序是未定义行为，#t 不连续就直接可能报错或死循环；排序前要么保证数组连续，要么 table.pack 收拢一遍把洞挤掉。5.4 对带洞数组已改为显式报错，但"先补洞再排"仍是跨版本的安全习惯。

flowchart TD
    A["cmp(a, b) 被调用"] --> B{a.score == b.score?}
    B -->|是| C{a.name < b.name?}
    C -->|是| D[a 排前]
    C -->|否| E[b 排前]
    B -->|否| F{a.score > b.score?}
    F -->|是| D
    F -->|否| E
    D & E --> G[结果全序且确定]
    H["错误写法: <="] --> I["invalid order function / 结果错乱"]

三、性能与工程四军规

比较器的调用次数是 O(n log n) 级别，n=10 万时约百万次调用——它是热点，四条军规给出。军规一，比较器里不许有副作用：不许改表、不许触发事件，排序中途修改待排元素等于在分区过程中挪动地基。军规二，键要预计算：若比较键是拼接串或算式（比如按 name .. level 排），先为每个元素算好 sortKey 字段再排序，别在 cmp 里每次重算——百万次重复拼接和十万次预计算差一个数量级。军规三，排序对象是数组：哈希表（键值对字典）没有顺序概念，想"按 value 排字典"得先 for k, v in pairs 收集成 {k=k, v=v} 数组再排，排完再遍历。军规四，降序就是反过来比：不要排序后再 table.reverse（多一趟 O(n)，且 reverse 与 sort 的平局序叠加后语义混乱），直接在比较器里反转比较方向，语义最干净。综合起来，比较器的本质是一次把业务序翻译成布尔值的契约翻译：严格小于保正确、决胜键保确定、无副作用保稳定、预计算保性能——四条全占，table.sort 就是零心智负担的黑盒；占不齐，它就把契约破坏原样还给你。

四、多级比较器的工程化封装

排行榜需求往往不止两个键：先按赛季分、再按胜场、再按报名先后。手写五层 if 嵌套的比较器既难读又难改，标准做法是把"键序列"数据化，用一个工厂函数生成比较器：

local function byKeys(...)          -- 传入键名列表, 后面的做决胜键
    local keys = table.pack(...)
    return function(a, b)
        for i = 1, keys.n do
            local k = keys[i]
            if a[k] ~= b[k] then return a[k] < b[k] end
        end
        return false                 -- 全平: 相等
    end
end
table.sort(players, byKeys("season", "wins", "joinTime"))

这个封装把比较器从"逻辑"降格为"配置"：策划要加一个决胜键，改参数列表而不是改函数体；要在某一级反向排序，把键名换成 {k="wins", desc=true} 形式再在循环里取方向即可。它同时天然满足严格弱序——键不相等才返回 true，相等返回 false，<= 这类写法根本无处藏身。两个使用前提要守住：键必须是可直接比较的同类型（混入 string 与 number 比较会直接抛错，混合类型键要先统一转串或转数）；键访问要 O(1)（普通表字段没问题，带 __index 转发的深链字段回到军规二——预计算成扁平字段再传键名）。顺带一提降序方向在工厂里的标准写法：不要在循环里对个别键写 > 硬编码，用一个方向数组 dirs[i] 决定每级用 < 还是 >，封装才配得上"通用"二字。把比较器做成配置的那一刻，排序这块就再也没有需要 review 的逻辑了。最后回到约定的源头收束：排序的可靠性从来不取决于算法本身——table.sort 的内部实现无可挑剔——而完全取决于你递给它的那个布尔函数是否守约；契约在，一切确定；契约破，一切报错都是它的诚实回声。