LINQ Quicksort Нестабилен Кроме тех случаев, когда Расположение каскадом
На странице 64 "LINQ К Объектам Используя C# 4.0" (Tony Magennis) он заявляет, что quicksort LINQ упорядочивание алгоритма нестабилен...
... хотя это просто решено путем расположения каскадом результата в оператор ThenBy или ThenByDescending.
Ха? Почему был бы, располагая каскадом нестабильную сортировку в другую сортировку, фиксируют результат? На самом деле я сказал бы, что это не возможно. Первоначальный заказ, когда-то прошел через нестабильный вид, просто потерян. Что я пропускаю здесь?
3 ответа
Проще говоря, он неправ. Linq OrderBy и др. методы задокументированы как выполняющие стабильную сортировку:
Этот метод выполняет стабильную сортировку; то есть, если ключи двух элементов равны, порядок элементов сохраняется. Напротив, нестабильная сортировка не сохраняет порядок элементов с одним и тем же ключом.
Он говорит, что если сделать, скажем, orderby LastName только тогда все с одинаковыми фамилиями будут отсортированы в непредсказуемом порядке. Поэтому если вы объедините его, скажем, с orderby LastName, FirstName, вы сможете сделать порядок снова предсказуемым (за исключением людей с одинаковыми и фамилиями, конечно).
По крайней мере, я бы предположил именно это.
Нестабильная сортировка означает, что цепочка вызовов x.OrderBy (...). OrderBy (...) будет надежно сортировать только в соответствии с последним критерием. x.OrderBy (...). ThenBy (...) явно фиксирует информацию о предыдущем порядке сортировки при применении нового порядка сортировки. Я считаю, что это достигается путем вызова IOrderedEnumerable , хотя я не уверен в этом на 100%.
РЕДАКТИРОВАТЬ: Для ясности, когда я говорю «фиксирует знания ...», я не имею в виду, что первый OrderBy выполняет сортировку, а второй каким-то образом знает, что он сделал. Помните, что OrderBy возвращает IOrderedEnumerable , который вообще не выполняет никакой работы, пока кто-то не попытается использовать элементы. В этом сценарии он никогда не выполнит сортировку, поскольку ThenBy , используя сведения о том, как OrderBy будет выполнять сортировку, , создает совершенно новый сортировщик, который применяет оба порядка сортировки в ожидаемым образом и за один шаг.
Было указано, что Магеннис ошибается в отношении нестабильной сортировки. Однако приведенное выше описание остается в силе.