algorithm - 如何根据任意顺序对列表进行排序

Question

我搜索了一个相关问题，但找不到。所以我的问题是如何根据任意顺序对数组进行排序。例如，假设顺序是:

order_of_elements = ['cc', 'zz', '4b', '13']

还有我要排序的列表:

list_to_be_sorted = ['4b', '4b', 'zz', 'cc', '13', 'cc', 'zz']

所以结果需要是:

ordered_list = ['cc', 'cc', 'zz', 'zz', '4b', '4b', '13']

请注意，引用列表(order_of_elements)描述了排序，我不询问根据引用列表的字母顺序索引进行排序。

您可以假设 order_of_elements 数组包含所有可能的元素。

欢迎任何伪代码。

Answer 1

实现此目的的一种简单的 Pythonic 方法是计算 order_of_elements 数组的索引查找表，并将索引用作排序键:

order_index_table = { item: idx for idx, item in enumerate(order_of_elements) }
ordered_list = sorted(list_to_be_sorted, key=lambda x: order_index_table[x])

该表将顺序查找减少到 O(1)(摊销)，因此不会改变排序的时间复杂度。

(当然，它确实假定 list_to_be_sorted 中的所有元素都存在于 order_of_elements 中；如果情况不一定如此，那么您需要在关键 lambda。)