插入排序获取索引？

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

我稍微修改了一下你的版本。现在它可以直接对列表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 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)) ]

只需要把调用sorted的地方换成你自己的排序算法就可以了。

Answer 3

你为什么要自己写排序的代码呢？直接用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