Сортировка списка строк по заданному порядку

Question

У меня есть множество цветов, которые я хотел бы отсортировать по порядку. Тем не менее, я не хочу сортировать их, используя их "естественный" порядок, а скорее, чтобы держать их в следующем порядке:

var order = ['white', 'yellow', 'violet', 'blue', 'orange', 'red', 'maroon', 'brown', 'black'];

Так, например, сортировка этого массива

var items = ['blue', 'violet', 'white', 'black', 'orange'];

должен вернуть

['white', 'violet', 'blue', 'orange', 'black'];

Вот что у меня так далеко:

var itemsInOrder = [];

for (var i=0; i<order.length; i++) {
    if (items.indexOf(order[i]) > -1) {
        itemsInOrder.push(order[i]);
    }
}

Я не уверен, насколько хорошо это масштабируется - что если order имеет 100 или 1000 элементов, но у 'items' есть 10?

Какой хороший, масштабируемый способ сделать это?

Answer 1

Как отметил @Shmiddty в комментарии, один простой способ сделать это - использовать библиотеку. sort функция с пользовательским компаратором, как это:

items.sort(function(a,b) {
   return order.indexOf(a) - order.indexOf(b);
});

Я бы начал с этого. Если это достаточно быстро, отлично! Смирись с этим.

С точки зрения сложности времени, давайте представим, что у вас есть список из n элементов для сортировки, и в главном порядке есть k элементов. Потом звоню sort с помощью специального компаратора будет выполнено O(n log n) сравнений, каждое из которых занимает время O(k) из-за стоимости сканирования по списку. Это дает время выполнения O(kn log n). Предполагая, что k мало - то есть ваш основной список не слишком длинный - это прекрасно.

Если k велико - например, если у вас фиксированный порядок всех городов в мире или что-то в этом роде - тогда этот подход вряд ли будет хорошо масштабироваться. В этом случае вы можете захотеть добавить еще один слой косвенности к проблеме, создав словарь, напрямую сопоставляющий все, что нужно отсортировать по его индексу. Вот один из способов сделать это:

var indexMap = {};
for (var i = 0; i < order.length; i++) {
    indexMap[order[i]] = i;
}

items.sort(function(a,b) {
   return indexMap[a] - indexMap[b];
});

Это имеет временную сложность O(k + n log n), поэтому для очень больших k это, вероятно, будет значительно быстрее.

Answer 2

В дополнение к ответу templatetypedef, одна вещь состоит в том, что если предопределенный вами элемент является "частичным", например, некоторые элементы в списке не могут быть отсортированы по предопределенному порядку, то вы можете выделить их из списка и затем объединить их в конце список потом

var items = [3, 2, 3, 2, 1, 4, 5, 1, 2, 3]
var order = [1, 2, 3]
var unordered = items.filter(t => order.indexOf(t) === -1);
var ordered = items.filter(t => order.indexOf(t) !== -1);
ordered.sort(function(a,b) {
   return order.indexOf(a) - order.indexOf(b);
});
var final = ordered.concat(unordered)
console.log(final)
// [ 1, 1, 2, 2, 2, 3, 3, 3, 4, 5 ]

Если вы не сделаете этот шаг, то сортировка фактически поместит неупорядоченные элементы в начало списка, и я не представлял, как его изменить, чтобы переместить их обратно в конец, не отфильтровав их в первую очередь.

Answer 3

Если кто-то ищет более простой код, чем Colin D, для сортировки массива и добавления неизвестных элементов в конце, вот еще один пример:

let list = ["A", "F", "Banana", "rules", "L", "Juice", "Z"]
let order = ["Banana", "Juice", "rules"]

list.sort((a, b) => {
  if (order.indexOf(a) === -1) return 1
  if (order.indexOf(b) === -1) return -1
  return order.indexOf(a) - order.indexOf(b)
})

console.log(list)

Это будет регистрировать: ["Banana", "Juice", "rules", "A", "F", "L", "Z"]