Есть ли алгоритм, который помещает элементы с одинаковыми ключами в группы быстрее, чем сортировка элементов?

Question

Некоторые элементы с целочисленными ключами находятся в массиве. Я хочу, чтобы элементы с одинаковыми ключами находились в группах внутри массива. Это может быть выполнено путем сортировки элементов, однако для меня не имеет значения, отсортированы ли элементы, только то, что они находятся в группах с одинаковыми ключами. Есть ли способ выполнить sh это быстрее, чем сортировка?

Answer 1

Карта ha sh в среднем должна работать хорошо. Используйте «счетчик» для значения, которое увеличивается каждый раз, когда вы видите соответствующий ключ в массиве, а затем используйте эти счетчики для перезаписи вашего массива.

Тем не менее, вызов «сортировки» по-прежнему довольно быстр и легче читать. Хорошая быстрая сортировка действительно может избежать некоторой работы, когда существуют дубликаты, поэтому вам действительно следует выполнить несколько тестов, чтобы убедиться, что более уродливый подход достаточно быстр и оправдан.