插入排序获取索引？

Question

我使用以下算法进行插入排序：

def insertionSort(A):
    indices = [z for z in xrange(len(A))]
    for j in range(1, len(A)):
        key = A[j]
        i = j-1
        while (i>=0) and (A[i]<key):
            A[i+1] = A[i]  
            indices[j-i-1] = i+1         
            i = i-1

        A[i+1] = key

但是，我需要维护一个列表以将 A 的原始值的索引映射到 A 的排序值，这意味着如果我有一个 [1,3,4,2 ] 对列表进行排序后 = [4,3,2,1] 我将得到一个索引列表 [3,1,0,2]。

有什么指点吗？我有点卡住了。

已编辑：抱歉，按降序排序..

Answer 1

你为什么要写一个排序？使用Python 的内置排序。

def sort_with_indexes(data):
    sorted_data = sorted(enumerate(data), key=lambda key: key[1])
    indexes = range(len(data))
    indexes.sort(key=lambda key: sorted_data[key][0])
    return [i[1] for i in sorted_data], indexes

data, indexes = sort_with_indexes([1,3,4,2])
print data, indexes

Answer 2

对 NullUserException 答案的修复很简单：

sorted_list, mapping = zip(*sorted([ (v, i) for i, v in enumerate(l) ]))
index_list = [ mapping.index(i) for i in range(len(sorted_list)) ]

只需用排序算法替换对排序的调用即可。

Answer 3

当你设置A[i+1]=key时，明确indices[j]=i+1。但是，当您设置 A[i+1]=A[i] 时，您必须递增 indices 中具有值 i （因为 A 中位于 i 的元素现在位于 i+1）。不幸的是，我认为在最坏的情况下，该算法的简单实现将是 O(n^3)。

Answer 4

看来您在更改原始数组的同时更改索引数组以跟踪它们的想法应该可行。我发现，当我有时无法同时跟踪两个索引时，我经常会通过单步执行纸上的循环来找出哪里出错了。

Answer 5

我稍微修改了你的版本。现在，它对列表 A 进行就地排序（非降序）并返回带有“排序索引”的列表。

def insertionSort(A):
    sorted_indices = [0]
    for j in range(1, len(A)):
        sorted_indices.append(j)
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] > key:
            A[i+1] = A[i]
            sorted_indices[i+1] = sorted_indices[i]
            i -= 1
        A[i+1] = key
        sorted_indices[i+1] = j
    return sorted_indices

Answer 6

我试图解决同样的问题，但我正在对数组而不是列表进行排序。使用排序的问题是它返回一个列表，对于我的目的而言，它占用了太多内存。幸运的是，您可以使用数组和 argsort 使用 numpy 来完成此操作：

import numpy
a=numpy.array([1,3,4,2])
p=a.argsort()

这将给出 array([0,3,1,2]) 作为结果。这是从低到高排序的。