algorithm - 排序:返回一个数组，其中包含每个元素的新位置

Question

我需要对数组进行排序，同时还返回一个包含原始元素排序位置的数组。 (注意不是 argsort，索引对数组进行排序)

目前这需要两个步骤:

1. 一个参数排序
2. 对新数组的分散操作即 pos[argsort[i]] = i

我觉得我在这里错过了一个技巧。这是我忽略的一种众所周知的算法，可以一步实现吗？

第二步也可以用搜索来实现，但我觉得分散更高效。

我已经包含了一些示例 python 代码来说明问题。

import numpy as np

l = [0,-8,1,10,13,2]

a = np.argsort(l)
# returns [1 0 2 5 3 4], the order required to sort l

# init new list to zero
pos = [0 for x in range(0,len(l))]

# scatter http://en.wikipedia.org/wiki/Gather-scatter_(vector_addressing)
for i in range(0,len(l)):
        pos[a[i]] = i

print pos
# prints [1, 0, 2, 4, 5, 3], i.e. each original indexes new position in the sorted array

搜索有关此问题的引用资料让我很沮丧，也许我错过了此类操作的正确术语。

如有任何帮助或指导，我们将不胜感激。

Answer 1

这是一个简单的实现，尽管它在任何意义上都不是“就地”的。我不确定您所说的“就地”是什么意思，因为输出是 int 类型的 np.array，输入可能包含 double 。

更新以回应@norio 的评论并澄清意图:

#!/usr/bin/env python

import numpy as np

unsorted = np.array([0,-8,1,10,13,2])

def myargsort(numbers):
  tuples = enumerate(numbers) # returns iterable of index,value
  sortedTuples = sorted(tuples,key = lambda pair: pair[1])
  sortedNumbers = [num for idx,num in sortedTuples]
  sortIndexes   = [idx for idx,num in sortedTuples]
  return (sortedNumbers,sortIndexes)

sortedNums, sortIndices = myargsort(unsorted)

print(unsorted)
print(sortedNums)
print(sortIndices)