Lua中实现先粗排序后同组精细排序的方法

嘿，你遇到的这个问题其实是Lua排序的一个常见小坑——table.sort用的是不稳定排序算法，当两个元素的第一键相等时，它们的相对顺序就没保障了，完全看排序算法的内部处理，所以才会出现随机的情况。

要实现你要的「保持第一键分组的绝对位置，同时给同组子表精细排序」的需求，其实很简单，只需要修改你的比较函数，在第一键相等的时候加个第二级的判断逻辑就行。

按自定义规则给同组元素排序 #

比如，假设你想在第一键相同的时候，按子表的第二个元素（字符串）按字典序升序排，那可以这么改：

local items = { {7007, "quux", 9.7}, {1004, "foo", 12.3}, {1234, "bar", 9.6}, {1234, "baz", 8.8}, }

local function compare(a, b)
    -- 先比第一键，优先级最高
    if a[1] ~= b[1] then
        return a[1] < b[1]
    end
    -- 第一键相等时，按第二个字符串的字典序排
    return a[2] < b[2]
end

table.sort(items, compare)

跑完这段代码后，items就会变成：

{ {1004, "foo", 12.3}, {1234, "bar", 9.6}, {1234, "baz", 8.8}, {7007, "quux", 9.7} }

要是你想按第三个元素（数值）升序排，那就把第二级判断换成：

return a[3] < b[3]

这样同组的子表就会按数值从小到大排，结果就是：

{ {1004, "foo", 12.3}, {1234, "baz", 8.8}, {1234, "bar", 9.6}, {7007, "quux", 9.7} }

核心逻辑就是先判断主排序键，当主键相等时，再判断次级排序键，这样既保证了整个大表按第一键的排序结果不变，又能让同组元素的顺序完全可控。

保持原表同组元素的相对顺序（稳定排序） #

如果你需要的是「稳定排序」——也就是原表中同第一键的元素，排序后依然保持原来的相对位置，那上面的方法就不适用了（因为table.sort本身是不稳定排序）。这时候可以给每个元素加个原索引，然后在第一键相等时比较原索引：

-- 先给每个元素加上原数组的索引
for idx, item in ipairs(items) do
    -- 用第四个位置存原索引，也可以用元表或者单独的映射表，看你习惯
    item[4] = idx
end

local function compare(a, b)
    if a[1] ~= b[1] then
        return a[1] < b[1]
    end
    -- 第一键相等时，按原索引升序，保留原顺序
    return a[4] < b[4]
end

table.sort(items, compare)

-- 最后把原索引删掉，还原结构
for _, item in ipairs(items) do
    item[4] = nil
end

这样处理后，原表中先出现的{1234, "bar", 9.6}在排序后依然会排在{1234, "baz", 8.8}前面，同时整个表的第一键排序完全正确。

内容的提问来源于stack exchange，提问作者Chase