сортировка вставки получить индексы?

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].

Есть указатели? Я немного застрял.

EDITED : извинения, сортировка по убыванию ..

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)) ]

просто замените вызов sort на ваш алгоритм сортировки.

Answer 3

Я пытался решить ту же проблему, но я сортировал массивы, а не списки.Проблема с использованием сортировки заключалась в том, что она возвращает список, который для моих целей занимал слишком много памяти.К счастью, вы можете сделать это с помощью numpy, используя массивы и argsort:

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

, что в результате даст массив ([0,3,1,2]).Это отсортировано по убыванию.

Answer 4

Я немного изменил вашу версию.Теперь он сортирует список 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 5

Похоже, ваша идея изменить массив индексов при изменении оригинала, чтобы отслеживать их, должна работать.Я нахожу, что, когда мне иногда трудно отслеживать два индекса одновременно, и я часто прибегаю к пошаговой прохождению цикла (ов) на бумаге, чтобы выяснить, где я иду не так.

Answer 6

Когда вы установите A[i+1]=key, ясно indices[j]=i+1. Однако, когда вы устанавливаете A[i+1]=A[i] Вы должны увеличить значение элемента indices, который имеет значение i (потому что элемент A, который был в i, теперь находится в i+1). К сожалению, я думаю, что наивной реализацией этого алгоритма будет O (n ^ 3) в худшем случае.