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

Question

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

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

Answer 1

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

Answer 2

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

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