Представьте себе случай, когда сравнение двух элементов чрезвычайно дорого.
Какой алгоритм сортировки вы бы использовали?
Какой алгоритм сортировки использует наименьшее количество сравнений в среднем случае?
Что делать, если вы можете ожидать, что многие сравниваемые элементы будут идентичными, скажем, в 80% сравнений. Это имеет значение?
Сортировка - один из тех тем, где, как говорится, дьявол находится в деталях. Как правило, во входных параметрах производительности доминируют вторичные соображения.
Однако, если сравнение очень дорогое, и если большинство ключей идентичны, возможно, что вход можно считать уже отсортированным или уже почти отсортированным.
В этом случае вам нужен разумный алгоритм, который имеет самый быстрый вариант, и почти наверняка будет сортировка вставки.
Победитель Sleep Sort, который не использует сравнения.
Посмотрите на ссылку wikipedia Ваш выбор структуры данных также влияет на сортировку.
Это зависит от того, какие данные у вас есть. Вам нужен стабильный алгоритм или нет?
Если ваши данные равномерно, вы можете использовать сортировку ковша (Θ (n), O (n ^ 2))
подсчет сортировки (я думаю, это то, что вы ищете), это также стабильный алгоритм, но нужно больше памяти (меньше у вас есть много идентичных записей).
Конечно, вы можете использовать Sleep sort, но если у вас много данных, он не будет работать.
Если ваши элементы на 80% идентичны, может быть, есть простой способ сказать, что они идентичны (то же самое)?
Сортировка дистрибутива (с использованием хэш-массива) почти не сравнивает.
m = max number may appear in the input + 1
hash = array of size m
initialize hash by zeroes
for i = 0 to n - 1
hash[input[i]] = hash[input[i]] + 1
j = 0
for i = 0 to m - 1
while hash[i] > 0
sorted[j] = i
j = j + 1
hash[i] = hash[i] - 1
Shellsort использует меньше сравнений.
И у вас много одинаковых элементов, Сортировка сортировки должна выполнять задание