排序数组并返回排序数组的原始索引

Question

给定一个numpy数组，如何找到其中的索引序列以便对结果进行排序？在

例如，给定x=[4,2,6]，结果将是[1,0,2]，因为[x[1],x[0],x[2]]是排序的。在

我知道有很多可用的Python函数，比如argsort()可以完成这项工作，但是我需要自己实现这个排序函数。有什么建议吗？在

Answer 1

如果我理解您的问题，您可以使用list-comprehension，并使用sorted函数。在

>>> import numpy as np
>>> np_array = np.array([4, 2, 6])
>>> sorted_index_pos = [index for index, num in sorted(enumerate(np_array), key=lambda x: x[-1])]
[1, 0, 2]

Answer 2

作为一个示例，让我们使用冒泡排序（from https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Bubble_sort#Python）并添加索引跟踪：

def bubblesort(lst):
    "Sorts lst in place and returns it."
    args = list(range(len(lst))) # <- initial order of indices
    for passesLeft in range(len(lst)-1, 0, -1):
        for index in range(passesLeft):
            if lst[index] > lst[index + 1]:
                lst[index], lst[index + 1] = lst[index + 1], lst[index]
                args[index], args[index + 1] = args[index + 1], args[index] # swap indices too
    return lst, args

Answer 3

首先，可以使用^{}将任何值的iterable转换为（index，value）对的iterable。在

但是如果你只是对它们进行排序，它将按索引排序，这并不是很有用。您需要按每个（index，value）对中的值进行排序。通常，在Python中，通过将key function传递给^{}来实现这一点。如该文档中的示例所示，^{}是一个完美的键函数。你可以很容易地修改你的自定义排序函数来使用键函数，就像sorted所做的那样，尽管在没有看到自定义排序函数的情况下演示如何使用键函数有点困难。¹

但在本例中，您可以使用Decorate-Sort-Undecorate习惯用法。您只需要按每个（index，value）对中的值进行排序，所以“装饰”所需做的就是将这些对颠倒。而且，如果您只希望索引而不是值来“取消装饰”，只需删除这些值。在

所以：

indexed = enumerate(arr)
decorated = ((value, index) for index, value in indexed)
sortedpairs = my_sort_function(decorated)
indices = np.fromiter(index for (value, index) in sortedpairs)

……或者，把它们放在一起：

^{pr2}$

（当然，您可以使用一行代码，但我认为两行代码是最好的可读性平衡点。）

---

如果你不允许用你的函数来替换你的函数。事实上，文档甚至向您展示了如何做到这一点：

def my_enumerate(sequence, start=0):
    n = start
    for elem in sequence:
        yield n, elem
        n += 1

或者，因为您不需要自定义开始值：

def my_enumerate(sequence):
    n = 0
    for elem in sequence:
        yield n, elem
        n += 1

---

但是现在，你能做同样的事情，同时仍然利用numpy（至少是一些）的优势，将所有东西都作为数组而不是使用iterables吗？在

当然可以。我们可以做与enumerate相同的操作，甚至将值放在底部，这样就不需要整个翻转步骤：

decorated = np.stack((arr, np.arange(len(arr))))

…然后分类。我假设您的自定义排序函数对列进行排序。也许你需要传入一个axis参数，或者排序decorated.T，或者其他什么；你应该知道你自己函数的API。在

sorted_pairs = my_sorted_array_function(decorated)

现在，我们只取索引行：

indices = sorted_pairs[1]

---

_{1。对于初始实现，只需将every x < y更改为key(x) < key(y)，并使其正常工作。然后，您可以通过缓存键值来找出如何优化它，这样每个元素只调用key次，而不是每个元素调用log(N)次。}