linq - 实现 OrderBy/ThenBy 的聪明方法是什么？

Question

我正在 Lua 中实现 LINQ 克隆，但这在这里不太相关，而且我已经完成了大部分功能(可枚举/可查询，还不是预编译器)，但想不出一个聪明的实现方式OrderBy 的 ThenBy。

目前我排序一次，然后放在新列表中，然后对这些子列表进行排序，最后再次合并结果，但这看起来非常浪费和不雅，我敢肯定有人已经想出一个聪明的方法来做到这一点(更好算法)，但我不知道它是什么。关于如何以有效方式实现 OrderBy/Thenby 的任何线索？

注意:希望语言和语言构造在这里不相关，我正在寻找通用算法，就像二进制排序可以用任何语言完成一样。

编辑:目前我正在研究 LINQ to Object，所以任何有关具体如何完成的想法都会很棒。我猜 OrberBy/ThenBy 是 2 个函数调用，不是一个，但我可能错了。

Answer 1

通常，您会使用合适的比较方法来实现多键排序。例如，要按姓氏然后按名字对名称列表进行排序，您可以使用如下比较函数:

int compareNames(Name n1, Name n2)
{
    if (n1.LastName < n2.LastName) {
        return -1;
    } else if (n1.LastName > n2.LastName) {
        return 1;
    } else if (n1.FirstName < n2.FirstName) {
        return -1;
    } else if (n1.FirstName > n2.FirstName) {
        return 1;
    } else {
        return 0;
    }
}

这里的关键点是，除非我们已经知道两个 LastName 成员相等，否则我们不会查看 FirstName 成员。