在某些位置对某些列表元素进行排序，保持其他位置不变

Question

我有一个元素列表，以及相关的排序键

data = [
 {'data': 0},
 {'key': 'foo', 'data': 1},
 {'key': 'bar', 'data': 2},
 {'data': 3},
 {'key': 'foo', 'data': 4},
 {'key': 'bar', 'data': 5},
 {'key': 'bar', 'data': 6},
 {'data': 7}
]

有些元素有排序key，有些没有。我有一个外部表，其中包含一些键的排序：

ORDER = ['bar', 'foo', 'baz']

预期结果：

[
 {'data': 0},
 {'key': 'bar', 'data': 2},
 {'key': 'bar', 'data': 5},
 {'data': 3},
 {'key': 'bar', 'data': 6},
 {'key': 'foo', 'data': 1},
 {'key': 'foo', 'data': 4},
 {'data': 7}
]

我需要以这样的方式对数组进行排序，即只移动具有键的元素，而不移动具有相同键的元素。（基本上，我对需要不交换元素（如果键比较不需要交换元素）的元素有一个偏序）。就我所见，现有的list.sort/sorted（在Python中）不支持这种排序

我强烈怀疑这个问题已经解决了很多次，但我找不到合适的名称来搜索

这种类型的排序是如何调用的

Answer 1

创建已排序记录的迭代器：

it1 = iter(sorted((d for d in data if 'key' in d), 
                  key=lambda d_: ORDER.index(d_['key'])))

接下来，编写一个列表，有选择地用“key”覆盖记录，而其他记录保持不变

res = [d if 'key' not in d else next(it1) for d in data]
print (res)
# [{'data': 0},
#  {'key': 'bar', 'data': 2},
#  {'key': 'bar', 'data': 5},
#  {'data': 3},
#  {'key': 'bar', 'data': 6},
#  {'key': 'foo', 'data': 1},
#  {'key': 'foo', 'data': 4},
#  {'data': 7}]

有几点：

• 可能值得将ORDER转换为一个字典，将键映射到位置，因此查找时间是恒定的。这将降低排序步骤的复杂性

• sorted返回一个列表，然后将其转换为迭代器，因此无法避免中间列表

Answer 2

如果您没有几个键，您可以在O（n）时间内执行此操作，例如使用bucket sort之类的东西：

import pprint
from collections import defaultdict
from itertools import chain

# create buckets
buckets, no_key = defaultdict(list), {}
for i, d in enumerate(data):
    if 'key' in d:
        buckets[d['key']].append(d)
    else:
        no_key[i] = d

# create one sorted list for elements with keys, basically iterate over the buckets in ORDER
chained = list(chain.from_iterable([buckets[key] for key in ORDER]))[::-1]

# combine the two iterables, chained and no_key into the final result
final = [no_key.pop(i) if i in no_key else chained.pop() for i in range(len(data))]
pprint.pprint(final)

输出

[{'data': 0},
 {'data': 2, 'key': 'bar'},
 {'data': 5, 'key': 'bar'},
 {'data': 3},
 {'data': 6, 'key': 'bar'},
 {'data': 1, 'key': 'foo'},
 {'data': 4, 'key': 'foo'},
 {'data': 7}]