Какой самый быстрый алгоритм сортировки для наихудшего случая? Меня не волнует лучший случай, и я предполагаю гигантский набор данных, если это даже имеет значение.
О важности указания вашей проблемы: сортировка по основанию может быть самой быстрой, но ее можно использовать только тогда, когда ваши данные имеют ключи фиксированной длины, которые можно разбить на независимые мелкие фрагменты. Это ограничивает его полезность в общем случае и объясняет, почему больше людей не слышали об этом.
http://en.wikipedia.org/wiki/Radix_sort
P.S. Это алгоритм O (k * n), где k - размер ключа.
Нижняя верхняя граница на машинах Тьюринга достигается с помощью сортировки слиянием , то есть O (n log n). Хотя быстрая сортировка может быть лучше для некоторых наборов данных.
Вы не можете опускаться ниже O (n log n), если не используете специальное оборудование (например, поддерживаемое оборудование сортировка по бусам , другие несопоставимые виды).
Я всегда предпочитал сортировку слиянием, поскольку она стабильна (это означает, что если два элемента равны с точки зрения сортировки, то их относительный порядок явно сохраняется), но быстрая сортировка также хороша.
Все зависит от данных, которые вы пытаетесь отсортировать. Разные алгоритмы имеют разные скорости для разных данных. алгоритм O (n) может быть медленнее, чем алгоритм O (n ^ 2), в зависимости от типа данных, с которыми вы работаете.
См. Быстрая сортировка и сортировка слиянием для сравнения быстрой сортировки и сортировки слиянием, которые в большинстве случаев являются двумя из лучших алгоритмов.
Предполагая случайную сортировку данных, быстрая сортировка.
O (nlog n) среднее значение, O (n ^ 2) в худшем случае, но для этого требуются весьма неслучайные данные.
Возможно, вы захотите описать характеристики вашего набора данных.