我有一个数字列表:

myList = [1, 2, 3, 100, 5]

现在如果我对这个列表进行排序得到[1,2,3,5,100]。 我想要的是元素的下标 原始列表的排序顺序,即[0,1,2,4,3] ——ala MATLAB的排序函数,返回两者 值和索引。


当前回答

如果你使用numpy,你有argsort()函数可用:

>>> import numpy
>>> numpy.argsort(myList)
array([0, 1, 2, 4, 3])

http://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html

这将返回对数组或列表进行排序的参数。

其他回答

像下面这样:

>>> myList = [1, 2, 3, 100, 5]
>>> [i[0] for i in sorted(enumerate(myList), key=lambda x:x[1])]
[0, 1, 2, 4, 3]

enumerate(myList)给你一个包含(index, value)元组的列表:

[(0, 1), (1, 2), (2, 3), (3, 100), (4, 5)]

通过将列表传递给sorted并指定一个函数来提取排序键(每个元组的第二个元素;这就是的意义。最后,使用[i[0] for i in…列表理解。

如果您不想使用numpy,

sorted(range(len(seq)), key=seq.__getitem__)

是最快的,如这里所示。

RustyRob答案的一个变体(它已经是最高性能的纯Python解决方案),当你排序集合时可能会更好:

不是一个序列(例如,它是一个集合,并且有一个合理的理由希望索引对应于迭代器必须前进多远才能到达项目),或者 是一个没有O(1)索引的序列(在Python包含的电池中,collections.deque是一个显著的例子)

情况#1不太可能有用,但情况#2更可能有意义。无论哪种情况,你都有两个选择:

转换为列表/元组并使用转换后的版本,或 使用基于迭代顺序分配键的技巧

这个答案为第2点提供了解决方案。请注意,它不能保证按照语言标准工作;该语言表示每个键将被计算一次,但不表示它们的计算顺序。到目前为止,在CPython(引用解释器)的每个版本中,它都是按照从头到尾的顺序预先计算的,所以这是可行的,但请注意,这并不能保证。在任何情况下,代码是:

sizediterable = ...
sorted_indices = sorted(range(len(sizediterable)), key=lambda _, it=iter(sizediterable): next(it))

All that does is provide a key function that ignores the value it's given (an index) and instead provides the next item from an iterator preconstructed from the original container (cached as a defaulted argument to allow it to function as a one-liner). As a result, for something like a large collections.deque, where using its .__getitem__ involves O(n) work (and therefore computing all the keys would involve O(n²) work), sequential iteration remains O(1), so generating the keys remains just O(n).

如果您需要使用内置类型来保证语言标准的工作,Roman的解决方案将具有与此解决方案相同的算法效率(因为它们都不依赖于索引原始容器的算法效率)。

需要明确的是,对于collections.deque的建议用例,deque必须非常大;Deques有一个相当大的常量除数用于索引,所以只有真正巨大的才会有问题。当然,出于同样的原因,如果输入比较小/便宜,排序的成本是非常小的,所以如果输入足够大,有效的排序很重要,那么它们也足够大,有效的索引也很重要。

我用perfplot(我的一个项目)快速检查了这些功能的性能,发现很难推荐其他功能

np.argsort(x)

(注意对数刻度):


代码重现情节:

import perfplot
import numpy as np


def sorted_enumerate(seq):
    return [i for (v, i) in sorted((v, i) for (i, v) in enumerate(seq))]


def sorted_enumerate_key(seq):
    return [x for x, y in sorted(enumerate(seq), key=lambda x: x[1])]


def sorted_range(seq):
    return sorted(range(len(seq)), key=seq.__getitem__)


b = perfplot.bench(
    setup=np.random.rand,
    kernels=[sorted_enumerate, sorted_enumerate_key, sorted_range, np.argsort],
    n_range=[2 ** k for k in range(15)],
    xlabel="len(x)",
)
b.save("out.png")

更新的答案与枚举和项目getter:

sorted(enumerate(a), key=lambda x: x[1])
# [(0, 1), (1, 2), (2, 3), (4, 5), (3, 100)]

将列表压缩在一起:元组中的第一个元素是索引,第二个元素是值(然后使用元组x[1]的第二个值对其排序,x是元组)

或者使用来自operatormodule '的itemgetter:

from operator import itemgetter
sorted(enumerate(a), key=itemgetter(1))