如何返回已排序列表的索引？

Question

我需要对列表进行排序，然后返回排序后元素在原列表中的索引。例如，如果要排序的列表是[2,3,1,4,5]，需要返回[2,0,1,3,4]。

这个问题最初发布在Bytes上，但我觉得在这里重新发问一下。 http://bytes.com/topic/python/answers/44513-sorting-list-then-return-index-sorted-item

我的具体需求是，根据对象的属性对对象列表进行排序，然后重新排列一个相应的列表以匹配新排序列表的顺序。

有没有好的方法可以实现这个需求呢？

- alex

---

一个选项是将对象列表映射到元组列表 [obj1, obj2, ...] -> [(0,obj1), (1, obj2), ...]，并对此列表进行排序。然后您可以立即获得原始索引的新顺序。 - Felix Kling

你实际上不需要索引来对应列表进行排序。只需在排序之前将列表压缩在一起，然后解压即可。（使用示例更新了我的答案）。 - Shawn Chin

@sykora：当然，但我认为OP已经指定了一个键，因为对象是按某个属性排序的... - Felix Kling

作为从事数值工作的人，我对Python中列表/zip/key技巧的性能至关重要，至少在数组很大的情况下是如此。我认为@jterrace提供了最好的解决方案。 - sigvaldm

请注意order向量和rank向量之间的区别，例如[2,0,1,3,4]是order向量，而对应的rank向量则为[1,2,0,3,4]。详见https://dev59.com/WsKVzogBFxS5KdRj5vjM。 - djvg

Answer 1

你可以使用Python排序函数的key参数来对索引数组进行排序。

>>> s = [2, 3, 1, 4, 5, 3]
>>> sorted(range(len(s)), key=lambda k: s[k])
[2, 0, 1, 5, 3, 4]
>>> 

- sykora

---

也许是 key=s.__getitem__？ - djvg

如果你需要逆序排列，可以使用以下代码：sorted(range(len(s)), key=lambda k: s[k], reverse=True) - NDM

如果您也想要排序后的数组，则可以使用以下代码：sorted_s = [s[k] for k in ind_s_to_sort]，其中ind_s_to_sort是从该方法获取的索引。 - villybyun

Answer 2

你可以使用numpy的argsort方法来完成这个操作，如果你有numpy的话：

You can do this with numpy's argsort method if you have numpy available:

>>> import numpy
>>> vals = numpy.array([2,3,1,4,5])
>>> vals
array([2, 3, 1, 4, 5])
>>> sort_index = numpy.argsort(vals)
>>> sort_index
array([2, 0, 1, 3, 4])

如果没有可用的方法，可以参考这个问题中提到的方法，这是最快的方法：

>>> vals = [2,3,1,4,5]
>>> sorted(range(len(vals)), key=vals.__getitem__)
[2, 0, 1, 3, 4]

- jterrace

---

非常好。因此，NumPy版本比sorted(...)版本更快吗？ - Iulius Curt

对于大型数组，是的。 - jterrace

Answer 3

如果你需要排序后的列表和索引列表，你可以这样做：

L = [2,3,1,4,5]
from operator import itemgetter
indices, L_sorted = zip(*sorted(enumerate(L), key=itemgetter(1)))
list(L_sorted)
>>> [1, 2, 3, 4, 5]
list(indices)
>>> [2, 0, 1, 3, 4]

或者对于 Python <2.4（没有 itemgetter 或 sorted）：

temp = [(v,i) for i,v in enumerate(L)]
temp.sort
indices, L_sorted = zip(*temp)

p.s. zip(*iterable)的惯用语反转了zip过程（即解压缩）。

---

更新：

针对您的特定要求：

"我有一个特殊需求，需要基于对象的属性对对象列表进行排序。然后，我需要重新排序相应的列表以匹配新排序列表的顺序。"

那是一种冗长的方式。您可以通过将两个列表一起压缩，然后使用对象属性作为排序关键字进行排序（并在排序后解压缩），以单个排序实现该目的。

combined = zip(obj_list, secondary_list)
zipped_sorted = sorted(combined, key=lambda x: x[0].some_obj_attribute)
obj_list, secondary_list = map(list, zip(*zipped_sorted))

这是一个简单的示例，使用字符串来表示您的对象。 在这里，我们使用字符串的长度作为排序的关键字：

str_list = ["banana", "apple", "nom", "Eeeeeeeeeeek"]
sec_list = [0.123423, 9.231, 23, 10.11001]
temp = sorted(zip(str_list, sec_list), key=lambda x: len(x[0]))
str_list, sec_list = map(list, zip(*temp))
str_list
>>> ['nom', 'apple', 'banana', 'Eeeeeeeeeeek']
sec_list
>>> [23, 9.231, 0.123423, 10.11001]

- Shawn Chin

Answer 4

如何呢？

l1 = [2,3,1,4,5]
l2 = [l1.index(x) for x in sorted(l1)]

- sizzzzlerz

---

这是 O(n^2)... - Felix Kling

这对于重复项不起作用吗？ - Leo

请见 https://www.bigocheatsheet.com/。 - djvg

在我看来，这种方法可能效率不高，但比其他答案更易读。 - djvg

Answer 5

你可以使用numpy.argsort，或者你可以这样做：

test =  [2,3,1,4,5]
idxs = list(zip(*sorted([(val, i) for i, val in enumerate(test)])))[1]

zip 会重新排列列表，使第一个元素为 test，第二个为 idxs。

- Simon Bergot

Answer 6

针对您的具体需求，我会这样做：

假设您有一个包含一些值的列表a，而您的键位于存储在列表b中的对象的属性x中。

keys = {i:j.x for i,j in zip(a, b)}
a.sort(key=keys.__get_item__)

使用这种方法，您可以按顺序获取列表，而无需构建您所要求的中间排列列表。

- fortran

Answer 7

直接从 collections.OrderedDict 的文档中摘录：

>>> # dictionary sorted by value
>>> OrderedDict(sorted(d.items(), key=lambda t: t[1]))
OrderedDict([('pear', 1), ('orange', 2), ('banana', 3), ('apple', 4)])

适应原帖中的示例：

>>> l=[2,3,1,4,5]
>>> OrderedDict(sorted(enumerate(l), key=lambda x: x[1])).keys()
[2, 0, 1, 3, 4]

详情请见http://docs.python.org/library/collections.html#collections.OrderedDict

- Austin Marshall