Нет ключа сравнения алгоритм сортировки

Question

На этой webpage я не могу читать:

Несколько специальных алгоритмов случай (один из примеров упоминается в Программирование Pearls) можно сортировать определенные данные наборы быстрее, чем O (N * журнал (п)). Эти алгоритмы не основаны на сравнении элементов , которые сортируются и опираются на трюки. Было показано, что алгоритм сравнения ключей может работать лучше, чем O (n * log (n)).

Это первый раз, когда я слышу о алгоритмов без сравнения. Может ли кто-нибудь дать мне пример одного из этих алгоритмов и объяснить, как быстрее решить проблему сортировки, чем O (nlog (n))? Какие трюки автор этой веб-страницы говорит?

Любая ссылка на документы или другой хороший источник приветствуются. Спасибо.

Answer 1

Во-первых, давайте терминологию прямо:

1. Ключевые сравнение алгоритмы могут» t лучше, чем O(n logn).
2. Есть другие - non-сравнения - алгоритмы, которые при определенных предположениях относительно данных могут работать лучше, чем O(n logn). Bucket sort - один из таких примеров.

Чтобы дать интуитивный пример второго класса, скажем, вы знаете, что ваш входной массив состоит из нулей и единиц. Вы можете перебирать массив, считая количество нулей и единиц. Назовем окончательные счета n0 и n1. Затем вы перебираете выходной массив, выписывая n0 нулями, а затем n1. Это алгоритм сортировки O(n).

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

Цена на то, чтобы быть в состоянии сортировать что-либо в любом случае, используя только один алгоритм, заключается в том, что такой алгоритм не может надеяться на лучшее, чем O(n logn) в среднем.

Answer 2

Да не сравнение сортировки обычно занимает O (N) пример этих алгоритмов сортировки являются Bucket Sort и Radix Sort