Определение порядка списка номеров (возможно, без сортировки)

Question

У меня есть массив уникальных целых чисел (например, val[i]) в произвольном порядке, и я хотел бы заполнить другой массив (ord[i]) отсортированными индексами целых чисел. Другими словами, val[ord[i]] в порядке сортировки для увеличения i.

Прямо сейчас я просто заполняю ord 0, ..., N, затем сортирую его по массиву значений, но мне интересно, можем ли мы быть более эффективными в этом, поскольку ord не заполнено начать с. Это больше вопрос из любопытства; Меня не особо волнуют дополнительные затраты, связанные с необходимостью предварительно заполнить список, а затем отсортировать его (он небольшой, я использую сортировку вставкой). Это может быть глупый вопрос с очевидным ответом, но я не смог ничего найти в Интернете.

Answer 1

С точки зрения сложности времени, не может быть более быстрого метода, чем сортировка. Если это так, то вы можете использовать его для более быстрой сортировки: сгенерируйте индексы, а затем используйте их, чтобы изменить порядок исходного массива в порядке сортировки. Это переупорядочение займет линейное время, поэтому в целом у вас будет более быстрый алгоритм сортировки, создающий противоречие.

Answer 2

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

В конечном итоге, чтобы узнать, что быстрее вам придется профилировать, большой O говорит вам только о том, как возрастает сложность при n -> бесконечность