Быстрая сортировка LINQ нестабильна, за исключением случаев каскадирования

Question

На странице 64 «LINQ To Objects Using C # 4.0» (Тони Магеннис) он заявляет, что алгоритм упорядочения быстрой сортировки LINQ неустойчив ...результат в оператор ThenBy или ThenByDescending.

А?Почему каскадирование нестабильной сортировки в другую сортировку может исправить результат?На самом деле, я бы сказал, что это невозможно.Первоначальный заказ, прошедший нестабильную сортировку, просто теряется.Что мне здесь не хватает?

Answer 1

Проще говоря, он не прав.Методы Linq OrderBy и др. задокументированы как как выполняющие стабильную сортировку:

Этот метод выполняет устойчивую сортировку;то есть, если ключи двух элементов равны, порядок элементов сохраняется.Напротив, нестабильная сортировка не сохраняет порядок элементов с одинаковым ключом.

Answer 2

Нестабильная сортировка означает, что цепочка вызовов x.OrderBy(...).OrderBy(...) будет надежно сортироваться только в соответствии с окончательным критерием. x.OrderBy(...).ThenBy(...) явно фиксирует знание предыдущего порядка сортировки при применении нового порядка сортировки. Я полагаю, что это происходит с помощью вызова IOrderedEnumerable<TElement>.CreateOrderedEnumerable<TKey>, хотя я не уверен на 100% в этом.

РЕДАКТИРОВАТЬ: Просто чтобы прояснить, когда я говорю, «захватывает знания ...», я не хочу сказать, что первый OrderBy выполняет сортировку, и каким-то образом второй знает, что он сделал. Помните, что OrderBy возвращает IOrderedEnumerable<T>, который вообще не выполняет никакой работы, пока кто-то не попытается использовать элементы. В этом сценарии он никогда не выполнит сортировку, поскольку ThenBy, используя знания о том, как OrderBy отсортировал бы , создает новый сортировщик, который применяет оба порядка сортировки ожидаемым образом и один шаг.

Было отмечено, что Магеннис ошибается в отношении нестабильной сортировки. Приведенное выше описание все еще действует, однако.

Answer 3

Он говорит, что если да, скажите orderby LastName, только тогда любой с такой же фамилией будет отсортирован в непредсказуемом порядке.Таким образом, если вы объедините его, скажем, с orderby LastName, FirstName, вы сможете снова сделать заказ предсказуемым (за исключением людей с одинаковыми именами и , конечно).

По крайней мере, вот чтоЯ бы предположил.