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

问题描述：

我有一个数字列表：

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

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

解决方案 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

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

解决方案 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 ...]

解决方案 3：

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

[0, 1, 2, 4, 3]

解决方案 4：

我使用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")

解决方案 5：

答案enumerate很好，但我个人不喜欢用于按值排序的 lambda。下面只是反转索引和值，然后对其进行排序。因此，它将首先按值排序，然后按索引排序。

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

解决方案 6：

更新答案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))

解决方案 7：

本质上你需要做一个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，那么您可以简单地使用该函数numpy.argsort或方法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`

解决方案 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)。

解决方案 9：

如果你不想使用numpy，

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

是最快的，正如这里所展示的。

解决方案 10：

为此目的，您可以使用 Numpy 包的最简单方法：

import numpy
s = numpy.array([2, 3, 1, 4, 5])
sort_index = numpy.argsort(s)
print(sort_index)

但是如果你想要你的代码应该使用基本的python代码：

s = [2, 3, 1, 4, 5]
li=[]
  
for i in range(len(s)):
      li.append([s[i],i])
li.sort()
sort_index = []
  
for x in li:
      sort_index.append(x[1])
  
print(sort_index)

解决方案 11：

我们将创建另一个从 0 到 n-1 的索引数组，然后将其压缩到原始数组，然后根据原始值对其进行排序

ar = [1,2,3,4,5]
new_ar = list(zip(ar,[i for i in range(len(ar))]))
new_ar.sort()

`

解决方案 12：

s = [2, 3, 1, 4, 5]
print([sorted(s, reverse=False).index(val) for val in s]) 

对于具有重复元素的列表，它将返回无关系的排名，例如

s = [2, 2, 1, 4, 5]
print([sorted(s, reverse=False).index(val) for val in s]) 

返回

[1, 1, 0, 3, 4]

解决方案 13：

将 numpy 导入为 np

索引

S=[11,2,44,55,66,0,10,3,33]

r=np.argsort(S)

[output]=array([5, 1, 7, 6, 0, 8, 2, 3, 4])

argsort 按排序顺序返回 S 的索引

追求价值

np.sort(S)

[output]=array([ 0,  2,  3, 10, 11, 33, 44, 55, 66])

解决方案 14：

首先将您的列表转换为以下内容：

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

为列表项添加索引

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

下一个 ：

sorted(myList, key=lambda k:k[1])

结果：

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

解决方案 15：

请注意，您经常会想要获取排序后的值以及索引。这里有一个快速而好的方法（不会浪费时间对所有内容进行两次排序）：

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

indices, values = zip(*sorted(enumerate(myList), key=lambda x: x[1]))

>>> indices
(0, 1, 2, 4, 3)
>>> values
(1, 2, 3, 5, 100)

解决方案 16：

代码：

s = [2, 3, 1, 4, 5]
li = []

for i in range(len(s)):
    li.append([s[i], i])
li.sort()
sort_index = []

for x in li:
    sort_index.append(x[1])

print(sort_index)

试试这个，它对我有用，欢呼！

解决方案 17：

RustyRob 答案的一个变体（它已经是性能最高的纯 Python 解决方案）在对集合进行排序时可能会更胜一筹：

1. 不是序列（例如，它是一个set，并且有正当理由希望索引对应于迭代器必须前进多远才能到达该项目），或者

2. 是没有索引的序列O(1)（在 Python 的内置电池中，collections.deque是一个显著的例子）

情况 1 不太可能有用，但情况 2 更可能有意义。无论哪种情况，您都有两种选择：

1. 转换为list/tuple并使用转换后的版本，或者

2. 使用技巧根据迭代顺序分配键

此答案提供了 #2 的解决方案。请注意，语言标准并不保证它可以正常工作；语言规定每个键都将计算一次，但不会规定计算顺序。到目前为止，在参考解释器 CPython 的每个版本中，它都是按从头到尾的顺序预先计算的，因此这有效，但请注意，这并不能保证。无论如何，代码是：

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

它所做的只是提供一个key忽略给定值（索引）的函数，而是从原始容器预先构造的迭代器中提供下一个项目（缓存为默认参数，以允许它作为一行代码运行）。因此，对于像大型这样的对象collections.deque，使用它.__getitem__需要O(n)工作（因此计算所有键都需要O(n²)工作），顺序迭代仍然是O(1)，因此生成键仍然只是O(n)。

如果您需要某些符合语言标准并能保证正常工作的东西，使用内置类型，Roman 的解决方案将具有与该解决方案相同的算法效率（因为它们都不依赖于索引原始容器的算法效率）。

需要明确的是，对于建议的用例collections.deque，deque必须非常大才能产生影响；deque有一个相当大的常数除数用于索引，因此只有真正巨大的才会出现问题。当然，同样，如果输入很小/比较便宜，则排序的成本非常小，因此如果您的输入足够大以至于高效排序很重要，那么它们也足够大以至于高效索引很重要。

解决方案 18：

我有点困惑。

问题是关于“如何在 Python 中获取排序数组的索引”，我的理解是如何获取数组中每个元素的排序索引。

因此，请为可能需要的人提供我的解决方案：

a = [1, 2, 3, 100, 5]
b = [m[0] for m in sorted([j for j in enumerate([i[0] for i in sorted(enumerate(a), key=lambda x:x[1])])],key=lambda x:x[1])]
print(b)

解决方案 19：

一些语法糖变化和少量修饰，否则这篇文章中至少有两个类似的答案。我发布这篇文章是因为与其他帖子不同，这篇文章也可以以降序方式获取“argsort”。

from collections import namedtuple
from array import array
def argsort(seq, reverse=False):
    index = sorted(range(len(seq)), key=lambda x: seq[x] if not reverse else -seq[x])
    sorted_number = sorted(seq, reverse=reverse)
    argsorted = namedtuple('argsorted_info', ['sorting_index','sorted_number', 'original_number'])
    return argsorted(index, sorted_number, seq)

# Works for integers
a = argsort([3,1,7,5,9,4])
print(a)

b = argsort([3,1,7,5,9,4], reverse=True)
print(b)

# Works for float (beware of truncation)
a = argsort([1.3,1.1,1.7,1.5,1.9,1.4])
print(a)

b = argsort([1.3,1.1,1.7,1.5,1.9,1.4], reverse=True)
print(b)

# Works for array
c = argsort(array('l',[3,1,7,5,9,4]))
print(c)

d = argsort(array('l',[3,1,7,5,9,4]), reverse=True)
print(d)

输出为

argsorted_info(sorting_index=[1, 0, 5, 3, 2, 4], sorted_number=[1, 3, 4, 5, 7, 9], original_number=[3, 1, 7, 5, 9, 4])
argsorted_info(sorting_index=[4, 2, 3, 5, 0, 1], sorted_number=[9, 7, 5, 4, 3, 1], original_number=[3, 1, 7, 5, 9, 4])
argsorted_info(sorting_index=[1, 0, 5, 3, 2, 4], sorted_number=[1, 3, 4, 5, 7, 9], original_number=array('l', [3, 1, 7, 5, 9, 4]))
argsorted_info(sorting_index=[4, 2, 3, 5, 0, 1], sorted_number=[9, 7, 5, 4, 3, 1], original_number=array('l', [3, 1, 7, 5, 9, 4]))
argsorted_info(sorting_index=[1, 0, 5, 3, 2, 4], sorted_number=[1.1, 1.3, 1.4, 1.5, 1.7, 1.9], original_number=[1.3, 1.1, 1.7, 1.5, 1.9, 1.4])
argsorted_info(sorting_index=[4, 2, 3, 5, 0, 1], sorted_number=[1.9, 1.7, 1.5, 1.4, 1.3, 1.1], original_number=[1.3, 1.1, 1.7, 1.5, 1.9, 1.4])