Какой алгоритм сортировки используется LINQ «OrderBy»?
Очевидно, что «OrderBy» LINQ первоначально был определен как неустойчивый, но ко времени Orca он был определен как стабильный. Не все документы обновлены соответственно – рассмотрите эти ссылки:
- Джон Скит на стабильности OrderBy
- Трой Магэннис на стабильности OrderBy
Но если OrderBy от LINQ теперь «стабилен», то это означает, что он не использует quicksort (который по своей сути неустойчив), хотя некоторые документы (например, книга Троя) говорят, что это так. Поэтому мой вопрос: если не quicksort, то какой именно алгоритм использует LINQ orderBy?
- Java - Удаление дубликатов в ArrayList
- Как определить BPM песни в php
- Поиск дубликатов в O (n) времени и O (1) пространстве
- Самый быстрый способ вычисления 128-битного целого по модулю 64-разрядного целого числа
- Какой был бы самый быстрый метод тестирования на простоту Java?
- Кто-нибудь действительно эффективно реализовал Fibonacci-Heap?
- синусоидальной волны, которая медленно увеличивает частоту от f1 до f2 в течение заданного времени
- Поиск всех циклов в ориентированном графе
- Разница между примечаниями Big-O и Little-O
- Постоянное амортизированное время
- Алгоритм сравнения слов
- Простое объяснение classификации Наив Байеса
- Что такое динамическое программирование?
Для LINQ to Objects это стабильная quicksort, которая используется. Для любого другого типа LINQ он остается для основной реализации.
Загрузите отражатель, откройте System.Linq.EnumerableSorter показывает, что Linq2Objects использует быструю сортировку
Используется Quicksort, но причина, по которой она стабильна, заключается в том, что индексы каждой пары элементов сравниваются, если все ключи совпадают.
Другими словами, вы можете сделать любую быструю сортировку устойчивой, включив в функцию компаратора сравнение исходных индексов двух элементов в качестве резервной копии.
Источник: http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1395017e067e5a34
Я понимаю, что OrderBy переводится в SQL, который выполняет сортировку в базе данных. По крайней мере, в случае LINQ to SQL