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

Question

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

Answer 1

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

根据您给出的条件，函数 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 实现中使用它来比较您的对象。

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

How do I use TimSort to sort by multiple fields?

sorting

algorithm

timsort