2

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

目前这需要两个步骤：

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

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

第 2 步也可以通过搜索来实现，但我认为分散更有效。

我已经包含了一些示例 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

搜索对这个问题的引用让我很沮丧，也许我错过了这种操作的正确术语。

任何帮助或指导将不胜感激。

4

1 回答 1

0

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

更新以回应@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)
于 2014-07-28T16:21:36.100 回答