algorithm - 如何使用 TimSort 按多个字段排序？

Question

我已经实现了 TimSort，但我真的需要能够按不同的字段进行排序。例如，按字段 2 排序，然后是 1，然后是 3。我一般知道如何执行此操作，如果先前给定的字段排序相同，则按下一个字段排序，但我正在寻找一个具有更多详细信息的解决方案特别是对于 TimSort。

Answer 1

您使用多个字段进行排序这一事实仅对比较功能产生影响，而不是对您使用的排序算法的实现产生影响。
要对对象进行排序，您需要能够比较它们。一个简单的方法是实现一个函数isSmaller，它接受两个对象作为参数，如果第一个小于第二个，则返回 true。

根据您给出的标准，该函数isSmaller可能如下所示：

function isSmaller(object1, object2) -> boolean {
    if object1.field2 < object2.field2 {
        return true
    } else if object1.field2 > object2.field2 {
        return false
    } else {                           // equality on first criterion -> check the second
        if object1.field1 < object2.field1 {
            return true
        } else if object1.field1 > object2.field1 {
            return false
        } else {                      // equality again -> check 3rd criterion
            if object1.field2 < object2.field3 {
                return true
            } else if object1.field2 > object2.field3 {
                return false
            } else {                 // equality on all criteria -> can return true or false
                return true
            }
        }
    }
}

然后，您所要做的就是使用它来比较您在 Timsort 实现中的对象。