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

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

如果您没有几个键，您可以在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}]