Просто интересно почему Javaи .NET Frameworkиспользует другой алгоритм сортировки по умолчанию.
В Java по умолчанию Array.Sort()используется алгоритм сортировки слиянием , и, как сказано в Wikipedia.com :
В Java методы Arrays.sort () используют сортировку слиянием или настроенную быструю сортировку в зависимости от типов данных и для переключения эффективности реализации на сортировку вставки, когда сортируется менее семи элементов массива
В .NET Framework Array.Sort/List.Sort() использует быструю сортировку в качестве алгоритма сортировки по умолчанию ( MSDN ):
List.Sort () использует Array.Sort, который использует алгоритм QuickSort. Эта реализация выполняет нестабильную сортировку; то есть, если два элемента равны, их порядок может не сохраниться. Напротив, стабильная сортировка сохраняет порядок элементов, которые равны.
Глядя на большую таблицу «Сравнение алгоритмов», мы видим, что оба алгоритма ведут себя довольно по-разному с точки зрения наихудшего случая и использования памяти:
И то, Javaи другое .NET- отличная платформа для разработки корпоративных решений, обе имеют платформы для встраиваемых разработок. Так почему они используют другой алгоритм сортировки по умолчанию, есть мысли?
Ответы:
Как бы ни были детерминистичны компьютеры, компьютерная инженерия не является точной наукой. Два человека, с учетом одной и той же предметной области, проведут анализ и разработают два разных решения, которые удовлетворяют всем ограничениям проблемы. Может быть трудно или невозможно эмпирически определить, какой из них «лучше» в общем случае.
Я полагаю, что .NET QuickSort наложена поверх чего-то в MFC или Windows API и, вероятно, унаследована от гораздо более старых версий Windows, где многопоточное преимущество MergeSort даже не рассматривалось для компьютеров день. ( РЕДАКТИРОВАТЬ: это не так, хотя разработчики Microsoft долгое время были фанатами QuickSort, о чем свидетельствует этот выбор реализации сортировки со времен MS-DOS).
Java, которая не может использовать какую-либо платформо-зависимую реализацию, потому что Java была разработана с нуля, чтобы быть полностью независимой от платформы, пошла другим путем. Кто знает, почему MergeSort вышел на первое место; Я предпочитаю предположить, что реализация выиграла какую-то конкуренцию в производительности по сравнению с некоторыми другими разработками, или, что O (n) -пространство MergeSort выглядело лучше всего на бумаге с точки зрения производительности в лучшем и худшем случаях. (MergeSort не имеет ахиллесовой пяты, связанной с выбором элементов, таких как QuickSort, и его лучший случай - почти отсортированный список, хотя это часто худший вариант QuickSort). Я сомневаюсь, что преимущества многопоточности изначально рассматривались, но текущая реализация вполне может быть многопоточной.
источник
List<T>.Sortв .NET использует собственный метод, реализованный в CLR (если вы не используете пользовательский компаратор), но не зависит от библиотек ОС.Различные команды разработчиков в двух разных компаниях пришли к разным выводам относительно обычного варианта использования их каркасов и компонентов и решили реализовать их соответствующим образом.
По сути, каждая компания провела свой анализ, посмотрела на свою клиентскую базу и приняла разные решения соответственно.
Вы не можете ожидать анализа от разных компаний и команд, используя разные предположения и исходные данные, чтобы прийти к одному и тому же выводу.
источник
Этот вопрос немного устарел, так как Java теперь использует Timsort ( начиная с Java 7)
Из конкретных упомянутых алгоритмов:
Быстрая сортировка имеет неблагоприятную производительность в наихудшем случае при O (n ^ 2), но она немного легче и требует меньше памяти, поэтому предлагает более высокую производительность в типичном случае.
Mergesort гарантирует производительность в худшем случае при O (n log n), но несет в себе немного больше накладных расходов и требований к памяти. Он также автоматически стабилен (т.е. поддерживает одинаковые элементы в одном и том же порядке).
Разработчики Java в целом выглядят немного более консервативными / сосредоточенными на «правильных вещах», поэтому неудивительно, что они выбрали Mergesort из двух, поскольку он предлагает лучшие гарантии.
Не знаете, почему Microsoft выбрала Quicksort, может быть, они хотя бы заставили их выглядеть лучше в некоторых микро-тестах?
источник