Я использую алгоритмы сортировки. Сорт Radix указывается как сортировка без сравнения, но он сравнивает цифры в числе и сортирует их. Может кто-нибудь Пожалуйста, дайте мне знать, что фактически означает сравнение сравнения.Определение сортировки без сравнения?
Алгоритм сортировки сравнения сравнивает пары отсортированных элементов, а выход каждого сравнения двоичный (то есть или not smaller than). Сортировка Radix учитывает цифры чисел в последовательности и вместо их сравнения группирует числа в ведрах по отношению к значению цифры (стабильным образом). Обратите внимание, что цифра не сравнивается ни с чем - она просто помещается в ведро, соответствующее его значению.
Важно знать, почему мы заботимся о алгоритмах сравнения/сравнения без сравнения. Если мы будем использовать алгоритм сортировки сравнения, то при каждом сравнении мы разделим набор возможных результатов примерно наполовину (потому что выход двоичный код), таким образом, лучшая сложность, которую мы можем иметь, - O(log(n!)) = O(n*log(n)). Это ограничение не выполняется для непересекающихся сортов.
Правильно ли говорить о лучшей сложности с точки зрения обозначения Big-O? – brz
К моему пониманию, различия между алгоритмом сравнения и сравнения не сравниваются с тем, существуют ли сравнения в алгоритме , но используют ли они внутренний символ подлежащих сортировке элементов.
Алгоритм сортировки сортировки сортирует элементы, сравнивая значения между собой. Он может применяться к любым случаям сортировки. И лучшая сложность - O(n*log(n)), что можно доказать математически.
Алгоритм сортировки сортировки использует внутренний символ сортируемых значений. Он может применяться только к некоторым конкретным случаям и требует определенных значений. И лучшая сложность, вероятно, лучше в зависимости от случаев, таких как O(n).
Все проблемы сортировки, которые могут быть отсортированы с помощью алгоритма сортировки без сравнения, могут быть отсортированы с алгоритмом сортировки сравнения, но не наоборот.
Для сортировки Radix, это выгодно, что отсортированные элементы - это числа, которые можно свести к цифрам. Он заботится о том, что такое отсортированные предметы. Хотя алгоритму сортировки сравнения требуется только порядок элементов.
http://en.wikipedia.org/wiki/Comparison_sort –
Он считается только сравнением, если вы сравниваете два элемента в списке. Глядя на последнюю цифру номера, чтобы выяснить, какое ведро положить в нее, не сравнивает два элемента. – Kevin
Форматы сортировки radix, которые я знаю, не сравнивают цифры. Они используют числовые значения цифр для доступа к массивам. – delnan