Какой алгоритм сортировки используется в поиске по умолчанию в stl и .net base library?
-
12-09-2019 - |
Вопрос
Сейчас я работаю над усовершенствованной версией сортировки слиянием.Я реализовал это с помощью C ++ и C #.Затем сравнил их с алгоритмом stl sort и array.sort() соответственно.В C ++ я получил равный (иногда лучший) результат.Но в C # мне пришлось использовать небезопасный код для использования указателей.Здесь производительность не настолько сопоставима с сортировкой по умолчанию.Итак, я хочу знать-
1.Какие алгоритмы используются в stl и библиотеке базовых классов .net?(Лучше со ссылками)
2.Есть ли у небезопасных кодов проблемы с производительностью?
3.Есть какие-нибудь предложения для меня относительно измерения производительности нового алгоритма?
Решение
.NET использует разновидность быстрой сортировки (медиана по Седжвику составляет 3 быстрой сортировки).
Если вы не являетесь экспертом в сортировке, я был бы удивлен, если бы вы смогли превзойти встроенную сортировку по широкому диапазону данных (включая случайные, уже упорядоченные и наоборот упорядоченные наборы).Прибегать к небезопасному коду обычно плохая идея...
Другие советы
Сортировка STL может зависеть от реализации, но (как говорится в Википедии) обычно это самосортировка, комбинация быстрой сортировки и сортировки кучно.Он должен иметь среднюю сложность O (n log n) сравнений.
.NET использует быструю сортировку.Вы можете использовать Отражатель чтобы просмотреть реализацию в системе.Коллекции.Универсальный.ArraySortHelper
В большинстве случаев быстрая сортировка будет выполняться быстрее, чем сортировка слиянием, даже несмотря на то, что в наихудшем случае время выполнения больше.Я думаю, что также были некоторые улучшения в стандартной быстрой сортировке, но я не уверен, используется ли что-либо из этого.
Кажется, я припоминаю, что STL также использует быструю сортировку, но я не совсем уверен.