排序：返回一个数组，每个元素的新位置

我需要排序数组，同时返回一个包含原始元素排序位置的数组。（NB不是argsort，所述索引来对数组进行排序）排序：返回一个数组，每个元素的新位置

目前这需要两个步骤：

一种argsort
一个新的阵列上的散布操作即POS [argsort [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

寻找对这个问题的引用让我感到沮丧，也许我错过了这种类型的操作正确的术语。

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

来源

2012-10-16 amckinley

我之前几次做，甚至不知道那是微不足道的改造人决定把它收集*散射*。尽管如此，我看不出为什么你这么注视这个 – Alexander

原始元素的排序位置是由argsort给出的。您的代码打印排序元素的原始位置。 –

另外注意，你可以通过应用两次'argsort'函数来达到同样的效果，但显然这是不理想的 – Alexander

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

更新响应@夫的评论和澄清意图：

#!/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-28 16:21:36 philwalk

它看起来这种方法需要两次排序操作。原始方法看起来更高效，因为它需要一次排序操作并列出遍历一次。 – norio

@norio，不确定3年前我在想什么，但回过头来看原来的问题，我怀疑我的版本实际上完成了他想要的，这可能就是你的观点。尽管只有一种排序方式，但还是有一个收集操作来将结果应用于数字列表。 – philwalk

作为算法的一部分，我以前在以前的版本中将'np.argsort'错误地写入了'print（..）'中。这就是为什么我写了“分类操作两次”。对不起。我在上面撤回了我的评论。（你对前一个函数的输出与OP想要的区别是对的，但是我太粗心了，注意到它。） – norio

排序：返回一个数组，每个元素的新位置

回答

相关问题