如何在Python中获取已排序数组的索引

Question

我有一个数字列表:

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

现在,如果我对此列表进行排序以获取[1, 2, 3, 5, 100].我想要的是排序顺序中原始列表中元素的索引,即[0, 1, 2, 4, 3] --- ala MATLAB的sort函数,它返回值和索引.

Answer 1

如果你正在使用numpy,你可以使用argsort()函数:

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

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

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

Answer 2

像下一个:

>>> 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) 为您提供包含(索引,值)元组的列表:

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

您可以通过将列表传递给sorted并指定一个函数来对列表进行排序,然后指定一个函数来提取排序键(每个元组的第二个元素;这就是lambda它的用途.最后,使用列表推导提取每个已排序元素的原始索引[i[0] for i in ...].

Answer 3

警告,专业人士:

myList = [1, 2, 3, 100, 5]    
sorted(range(len(myList)),key=myList.__getitem__)

[0, 1, 2, 4, 3]

Answer 4

答案enumerate很好,但我个人不喜欢用于按值排序的lambda.以下只是反转索引和值,并对其进行排序.所以它首先按值排序,然后按索引排序.

sorted((e,i) for i,e in enumerate(myList))

Answer 5

更新的答案:enumerate和itemgetter:

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

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

或者itemgetter从operator模块`使用:

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

Answer 6

基本上你需要做一个argsort，你需要什么实现取决于你是想使用外部库（例如 NumPy）还是想保持纯 Python 而不依赖。

你需要问自己的问题是：你想要

• 对数组/列表进行排序的索引
• 元素在排序数组/列表中的索引

不幸的是，问题中的示例并没有说明需要什么，因为两者都会给出相同的结果：

>>> arr = np.array([1, 2, 3, 100, 5])

>>> np.argsort(np.argsort(arr))
array([0, 1, 2, 4, 3], dtype=int64)

>>> np.argsort(arr)
array([0, 1, 2, 4, 3], dtype=int64)

选择argsort实施

如果您可以使用 NumPy，则可以简单地使用 functionnumpy.argsort或 method numpy.ndarray.argsort。

其他一些答案中已经提到了没有 NumPy 的实现，所以我将根据此处的基准答案回顾最快的解决方案

def argsort(l):
    return sorted(range(len(l)), key=l.__getitem__)

获取对数组/列表进行排序的索引

要获取对数组/列表进行排序的索引，您只需调用argsort数组或列表即可。我在这里使用 NumPy 版本，但 Python 实现应该给出相同的结果

>>> arr = np.array([3, 1, 2, 4])
>>> np.argsort(arr)
array([1, 2, 0, 3], dtype=int64)

结果包含获取排序数组所需的索引。

由于排序数组将是[1, 2, 3, 4]argsorted 数组，它包含原始元素中这些元素的索引。

• 最小值是1并且它位于1原始索引处，因此结果的第一个元素是1。
• 的2是在索引2中的原始所以结果的第二个元素是2。
• 的3是在索引0中的原始所以结果的第三个元素是0。
• 最大值4，它位于3原始索引处，因此结果的最后一个元素是3。

获取元素在排序数组/列表中的索引

在这种情况下，您需要申请argsort 两次：

>>> arr = np.array([3, 1, 2, 4])
>>> np.argsort(np.argsort(arr))
array([2, 0, 1, 3], dtype=int64)

在这种情况下 ：

• 原始元素的第一个元素是3，它是第三大值，因此它将2在排序数组/列表中具有索引，因此第一个元素是2。
• 原始元素的第二个元素是1，它是最小值，因此它将0在已排序的数组/列表中具有索引，因此第二个元素是0。
• 原始元素的第三个元素是2，它是第二小的值，因此它将1在已排序的数组/列表中具有索引，因此第三个元素是1。
• 原始元素的第四个元素4是最大值，因此它将3在排序数组/列表中具有索引，因此最后一个元素是3.

Answer 7

如果您不想使用numpy，

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

是最快的，这表现在这里。

Answer 8

其他答案是错误的。

运行argsort一次不是解决方案。例如，以下代码：

import numpy as np
x = [3,1,2]
np.argsort(x)

产量array([1, 2, 0], dtype=int64)不是我们想要的。

答案应该是运行argsort两次：

import numpy as np
x = [3,1,2]
np.argsort(np.argsort(x))

array([2, 0, 1], dtype=int64)按预期给出。

Answer 9

我用perfplot（我的一个项目）对这些进行了快速性能检查，发现很难推荐除numpy以外的其他任何东西（请注意对数刻度）：

复制剧情的代码：

import perfplot
import numpy


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__)


def numpy_argsort(x):
    return numpy.argsort(x)


perfplot.save(
    "argsort.png",
    setup=lambda n: numpy.random.rand(n),
    kernels=[sorted_enumerate, sorted_enumerate_key, sorted_range, numpy_argsort],
    n_range=[2 ** k for k in range(15)],
    xlabel="len(x)",
    logx=True,
    logy=True,
)