Ограничения методов сортировки на основе сравнения

Question

Сравнительная сортировка выбирается в большинстве сценариев, где необходимо упорядочить данные. Такие методы, как сортировка слиянием, быстрая сортировка, сортировка вставкой и другие виды сравнения, могут обрабатывать различные типы данных и эффективность с нижним пределом O (nLog (n)).

Мои вопросы

1. Существуют ли ограничения для методов сортировки, основанных на сравнении?
2. Какие-либо сценарии, в которых будут использоваться методы сортировки без сравнения?

ура

Answer 1

Очевидно, что ограничения сортировок сравнения являются временным фактором - некоторые лучше, чем другие , но, учитывая достаточно большой набор данных, они все станут слишком медленными в какой-то момент. Хитрость заключается в том, чтобы выбрать правильный, учитывая тип и сочетание данных, которые вы сортируете.

Сортировка без сравнения основана на других факторах, игнорирующих данные, например, сортировка при подсчете упорядочит сбор данных путем проверки каждого элемента, а не сравнения с каким-либо другим значением в коллекции. Подсчет сортировки полезен для упорядочения коллекции на основе некоторых данных. Если бы у вас была коллекция целых чисел, она упорядочила бы их, взяв все элементы со значением 1 и поместив их сначала в место назначения, затем все элементы со значением 2 и т. Д. (хорошо, он использует «разреженный» массив для быстрого масштабирования коллекции и изменения порядка значений, оставляя пробелы, но это основной принцип)

Answer 2

Вы ответили более или менее самостоятельно. Методы сортировки на основе сравнения ограничены нижним пределом O (n Log (n)). Методы сортировки, не основанные на сравнении, не страдают от этого ограничения. Общая проблема с алгоритмами несортировки заключается в том, что домен должен быть лучше известен, и по этой причине он не настолько универсален, как методы, основанные на сравнении.

Pigeonhole sort - отличный и довольно простой пример, который довольно быстр, если количество возможных ключевых значений близко к числу элементов.

Answer 3

Легко понять, почему сортировка сравнения требует N log N сравнений. Нет! перестановок и, как мы знаем, ln (N!) составляет приблизительно N ln N - N + O (ln N). В больших обозначениях O мы можем пренебречь слагаемыми, меньшими, чем N ln N, и поскольку ln и log отличаются только на константу, мы получаем конечный результат O (N log N)