实现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;
    }
}

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