给定预定义顺序对字符串列表进行排序 [英] Sort a list of strings given a predefined order

问题描述

我有一组要按顺序排序的颜色.但是，我不想使用它们的自然"顺序对它们进行排序，而是按照以下顺序对它们进行排序:

I have an array of colors that I'd like to sort into order. However, I don't want to sort them using their "natural" ordering, but rather to keep them in this order:

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

例如，对这个数组进行排序

So, for example, sorting this array

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 个元素怎么办?

I'm not sure how well it scales - what if order has 100 or 1000 elements but 'items' has 10?

有什么好的、可扩展的方式来实现这一目标?

What is a good, scalable way to accomplish this?

推荐答案

正如@Shmiddty 在评论中指出的那样，一种简单的方法是使用带有自定义比较器的库 sort 函数，像这样:

As @Shmiddty pointed out in a comment, one simple way to do this is to use the library sort function with a custom comparator, like this:

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

我会从那个开始.如果它足够快，那就太好了！随它去吧.

I'd start with that. If it's fast enough, great! Go with it.

从时间复杂度的角度来看，假设您有一个包含 n 个元素的列表要排序，并且主排序中有 k 个元素.然后使用自定义比较器调用 sort 将进行 O(n log n) 次比较，由于扫描列表的成本，每次比较都需要 O(k) 时间.这给出了 O(kn log n) 的运行时间.假设 k 很小 - 也就是说，您的主列表不会太长 - 这完全没问题.

From a time complexity perspective, let's imagine that you have a list of n elements to sort and the master ordering has k elements in it. Then calling sort with a custom comparator will make O(n log n) comparisons, each of which takes time O(k) due to the cost of scanning over the list. That gives a runtime of O(kn log n). Assuming k is small - that is, your master list isn't too long - this is perfectly fine.

如果 k 很大——例如，如果你有世界上所有城市的固定排序，或者类似的东西——那么这种方法不太可能很好地扩展.在这种情况下，您可能希望通过创建一个直接将要排序的所有内容映射到其索引的字典来为问题添加另一层间接性.这是执行此操作的一种方法:

If k is large - for example, if you have a fixed ordering of all cities in the world, or something like that - then this approach is not likely to scale well. In that case, you may want to add another layer of indirection to the problem by creating a dictionary directly mapping everything to be sorted to its index. Here's one way to do this:

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，它可能会明显更快.

This has time complexity O(k + n log n), so for very large k it's likely to be appreciably faster.

这篇关于给定预定义顺序对字符串列表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！