Как использовать TimSort для сортировки по нескольким полям?

Question

Я реализовал TimSort, но мне действительно нужно иметь возможность сортировать по разным полям.Например, сортировка по полю 2, затем 1, затем 3. Я знаю в общих чертах, как это сделать, сортировка по следующему полю, если ранее заданные поля для сортировки равны, но я ищу решение, которое имеет больше деталейи в частности для TimSort.

Answer 1

Тот факт, что вы сортируете по нескольким полям, влияет только на функцию сравнения, а не на реализацию алгоритма сортировки, который вы используете.
Для сортировки объектов вам нужно уметь сравнивать их.Простой способ сделать это - реализовать функцию isSmaller, которая принимает два объекта в качестве аргументов и возвращает истину, если первый меньше второго.

Функция 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.