如何使用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实现中的对象。