Получение индексов сортировки целочисленного массива

Question

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

, например: [10, 20, 30]

должен привести к: [2, 1, 0]

что такоеоптимизированный алгоритм для достижения этой цели?

Answer 1

Этого можно добиться с помощью любого алгоритма сортировки, если преобразовать каждый элемент в кортеж (value, position) и отсортировать его.

То есть [10, 20, 30] станет [(10, 0), (20, 1), (30, 2)]. Затем вы отсортируете этот массив, используя компаратор, который просматривает первый элемент кортежей, и вы получите [(30, 2), (20, 1), (10, 0)]. Отсюда вы можете просто взять второй элемент каждого кортежа, чтобы получить то, что вы хотите, [2, 1, 0]. (В предположении, что вы хотите обратную сортировку.)

Answer 2

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

Answer 3

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