Сортировка списка по правилам

Question

У меня есть список, который мне нужно отсортировать.

['Product ED', 'Product CX', 'Product XY', 'Product ED']

Этот список должен быть отсортирован после определенного правила:

['CX', 'XY', 'ED']

Итак, в конце список имеетбыть заказанным после этого правила, например:

['Product CX', 'Product XY', 'Product ED', 'Product ED']

Как бы вы реализовали алгоритм, подобный этому?

РЕДАКТИРОВАТЬ: Ну, я пришел к простой идее сразу после того, как я написал этовопрос ...

Вот оно:

var l = ['Product ED', 'Product CX', 'Product XY', 'Product ED'];
var rules = ['CX', 'XY', 'ED'];

l.sort(function(a, b) {
    return rules.indexOf(a.replace(/^Product /, '')) > rules.indexOf(b.replace(/^Product /, ''));
})

['Product CX', 'Product XY', 'Product ED', 'Product ED']

Answer 1

Более формально, вы можете определить функцию сравнения, которая берет два элемента из списка для сортировки, список правил, и затем возвращает 1, если первый элемент больше второго (согласно правилам) и -1 если он меньше, и 0, если они одинаковы. Тогда будет работать любая сортировка на основе сравнения.

Сложность: T (n) = 2T (n / 2) + O (нм) =? O (m n log n) возможно, например, с помощью mergesort ... верно? (примечание: n - это количество элементов в списке, которые нужно отсортировать, m размер набора правил).

Answer 2

jsFiddle

    var list = ['Product ED', 'Product CX', 'Product XY', 'Product ED'];
    var rule = ['CX', 'XY', 'ED'];

    list.sort(function(a, b) {
        var aIndex, bIndex;
        for (var i = 0; i < rule.length; i++) {
            var aMatch = a.match(rule[i]);
            var bMatch = b.match(rule[i]);
            if (aMatch && aMatch.length > 0) {
                aIndex = rule.indexOf(aMatch[0])
            }
            if (bMatch && bMatch.length > 0) {
                bIndex = rule.indexOf(bMatch[0]);
            }

            if (bIndex && aIndex) {
                continue;
            }
        }

        if (aIndex < bIndex) return -1;
        else if (aIndex > bIndex) return 1;
        else return 0;
    })

    console.log(list)

Answer 3

Ну, быстрый и грязный способ - добавить каждое значение с помощью ключа сортировки.«1Product CX», «2Product XY» и т. Д., Отсортируйте их, а затем удалите их.

Просто убедитесь, что добавляемый ключ сортировки имеет ту же длину, если у вас больше 10,Вам понадобятся '01', '02' и т. д.

Если вы хотите сделать это правильно, вам нужно определить функцию сравнения и передать ее в функцию «сортировки» в качестве параметра: http://www.w3schools.com/jsref/jsref_sort.asp