Как получить индексы отсортированного массива в Python

Если вы используете numpy, вам доступна функция argsort ():

>>> import numpy
>>> numpy.argsort(myList)
array([0, 1, 2, 4, 3])

http://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html

Это возвращает аргументы, которые будут сортировать массив или список.

Что-то вроде следующего:

>>> myList = [1, 2, 3, 100, 5]
>>> [i[0] for i in sorted(enumerate(myList), key=lambda x:x[1])]
[0, 1, 2, 4, 3]

enumerate(myList) дает вам список, содержащий кортежи (индекс, значение):

[(0, 1), (1, 2), (2, 3), (3, 100), (4, 5)]

Вы сортируете список, передавая его sorted и указывая функцию для извлечения ключа сортировки (второй элемент каждого кортежа; для этого используется lambda. Наконец, исходный индекс каждого отсортированного элемента равен извлечен с использованием понимания списка [i[0] for i in ...].

Ответы с enumerate хороши, но мне лично не нравится лямбда, используемая для сортировки по значению. Следующее просто меняет местами индекс и значение и сортирует их. Поэтому сначала выполняется сортировка по значению, а затем по индексу.

sorted((e,i) for i,e in enumerate(myList))

Я быстро проверил их производительность с помощью perfplot (мой проект) и обнаружил, что рекомендовать их сложно. что-нибудь еще, кроме numpy (обратите внимание на шкалу журнала):

Код для воспроизведения сюжета:

import perfplot
import numpy


def sorted_enumerate(seq):
    return [i for (v, i) in sorted((v, i) for (i, v) in enumerate(seq))]


def sorted_enumerate_key(seq):
    return [x for x, y in sorted(enumerate(seq), key=lambda x: x[1])]


def sorted_range(seq):
    return sorted(range(len(seq)), key=seq.__getitem__)


def numpy_argsort(x):
    return numpy.argsort(x)


perfplot.save(
    "argsort.png",
    setup=lambda n: numpy.random.rand(n),
    kernels=[sorted_enumerate, sorted_enumerate_key, sorted_range, numpy_argsort],
    n_range=[2 ** k for k in range(15)],
    xlabel="len(x)",
)

Обновленный ответ с enumerate и itemgetter:

sorted(enumerate(a), key=lambda x: x[1])
# [(0, 1), (1, 2), (2, 3), (4, 5), (3, 100)]

Объедините списки вместе: первый элемент в кортеже будет индексом, второй - значением (затем отсортируйте его, используя второе значение кортежа x[1], x - это кортеж)

Или используя itemgetter из operatormodule`:

from operator import itemgetter
sorted(enumerate(a), key=itemgetter(1))

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

Вам нужно задать себе следующий вопрос: хотите ли вы

• индексы, которые будут сортировать массив / список
• индексы, которые элементы будут иметь в отсортированном массиве / списке

К сожалению, пример в вопросе не проясняет, что желательно, потому что оба дадут одинаковый результат:

>>> arr = np.array([1, 2, 3, 100, 5])

>>> np.argsort(np.argsort(arr))
array([0, 1, 2, 4, 3], dtype=int64)

>>> np.argsort(arr)
array([0, 1, 2, 4, 3], dtype=int64)

Выбор реализации argsort

Если у вас есть NumPy, вы можете просто использовать функцию numpy.argsort или метод _5 _.

Реализация без NumPy уже упоминалась в некоторых других ответах, поэтому я просто резюмирую самое быстрое решение в соответствии с эталонным ответом здесь

def argsort(l):
    return sorted(range(len(l)), key=l.__getitem__)

Получение индексов для сортировки массива / списка

Чтобы получить индексы, которые будут сортировать массив / список, вы можете просто вызвать argsort в массиве или списке. Здесь я использую версии NumPy, но реализация Python должна давать те же результаты.

>>> arr = np.array([3, 1, 2, 4])
>>> np.argsort(arr)
array([1, 2, 0, 3], dtype=int64)

Результат содержит индексы, необходимые для получения отсортированного массива.

Поскольку отсортированный массив будет [1, 2, 3, 4], отсортированный массив содержит индексы этих элементов в оригинале.

• Наименьшее значение - 1, а в оригинале он находится под индексом 1, поэтому первым элементом результата является 1.
• 2 находится в индексе 2 в оригинале, поэтому второй элемент результата - 2.
• 3 находится в индексе 0 в оригинале, поэтому третий элемент результата - 0.
• Наибольшее значение 4 и индекс 3 в оригинале, поэтому последний элемент результата - 3.

Получение индексов, которые элементы будут иметь в отсортированном массиве / списке

В этом случае вам нужно будет применить argsort дважды:

>>> arr = np.array([3, 1, 2, 4])
>>> np.argsort(np.argsort(arr))
array([2, 0, 1, 3], dtype=int64)

В таком случае :

• первым элементом оригинала является 3, что является третьим по величине значением, поэтому он будет иметь индекс 2 в отсортированном массиве / списке, поэтому первым элементом является 2.
• вторым элементом оригинала является 1, что является наименьшим значением, поэтому он будет иметь индекс 0 в отсортированном массиве / списке, поэтому вторым элементом является 0.
• третий элемент оригинала - это 2, что является вторым наименьшим значением, поэтому он будет иметь индекс 1 в отсортированном массиве / списке, поэтому третий элемент - это 1.
• четвертым элементом оригинала является 4, что является наибольшим значением, поэтому он будет иметь индекс 3 в отсортированном массиве / списке, поэтому последний элемент - 3.

Если вы не хотите использовать numpy,

sorted(range(len(seq)), key=seq.__getitem__)

самый быстрый, как показано здесь.

Другие ответы неверны.

Один раз запустить argsort - не решение. Например, такой код:

import numpy as np
x = [3,1,2]
np.argsort(x)

дает array([1, 2, 0], dtype=int64), чего мы не хотим.

Ответ должен заключаться в том, чтобы запустить argsort дважды:

import numpy as np
x = [3,1,2]
np.argsort(np.argsort(x))

дает array([2, 0, 1], dtype=int64), как и ожидалось.

Мы создадим еще один массив индексов от 0 до n-1, затем заархивируем его в исходный массив и затем отсортируем его на основе исходных значений.

ar = [1,2,3,4,5]
new_ar = list(zip(ar,[i for i in range(len(ar))]))
new_ar.sort()

`

Самый простой способ использовать для этой цели пакеты Numpy:

import numpy
s = numpy.array([2, 3, 1, 4, 5])
sort_index = numpy.argsort(s)
print(sort_index)

Но если вы хотите, чтобы в коде использовался код baisc на Python:

s = [2, 3, 1, 4, 5]
li=[]
  
for i in range(len(s)):
      li.append([s[i],i])
li.sort()
sort_index = []
  
for x in li:
      sort_index.append(x[1])
  
print(sort_index)

Импортировать numpy как np

ДЛЯ ИНДЕКСА

S=[11,2,44,55,66,0,10,3,33]

r=np.argsort(S)

[output]=array([5, 1, 7, 6, 0, 8, 2, 3, 4])

argsort Возвращает индексы S в отсортированном порядке

ДЛЯ СТОИМОСТИ

np.sort(S)

[output]=array([ 0,  2,  3, 10, 11, 33, 44, 55, 66])

Код:

s = [2, 3, 1, 4, 5]
li = []

for i in range(len(s)):
    li.append([s[i], i])
li.sort()
sort_index = []

for x in li:
    sort_index.append(x[1])

print(sort_index)

Попробуйте, это сработало для меня, ура!

сначала преобразуйте свой список в этот:

myList = [1, 2, 3, 100, 5]

добавить индекс к элементу вашего списка

myList = [[0, 1], [1, 2], [2, 3], [3, 100], [4, 5]]

следующий :

sorted(myList, key=lambda k:k[1])

результат:

[[0, 1], [1, 2], [2, 3], [4, 5], [3, 100]]