Является ли F # ResizeArray sortBy стабильным?

Question

Делает ли функция ResizeArray.sortBy стабильную сортировку в том смысле, что она не меняет порядок элементов, имеющих одинаковое значение для ключевой функции?

А если нет, как написатьстабильная сортировка в F #?

Answer 1

Ответ на ваш вопрос unstable.

Первый ResizeArray.sortBy реализован следующим образом:

module ResizeArray =
    let sortBy f (arr: ResizeArray<'T>) = arr.Sort (System.Comparison(fun x y -> compare (f x) (f y)))

И ResizeArray - псевдоним для коллекции .Net List:

type ResizeArray<'T> = System.Collections.Generic.List<'T> // alias

Теперь давайте посмотрим на Список документации :

Этот метод использует Array.Sort, который использует алгоритм QuickSort.Эта реализация выполняет нестабильную сортировку;то есть, если два элемента равны, их порядок может не сохраниться.Напротив, стабильная сортировка сохраняет порядок элементов, которые равны.

Так неустойчиво.Если вам нужна стабильная сортировка, вы можете реализовать сортировку слиянием или тщательную быструю сортировку.Однако стабильная версия быстрой сортировки менее эффективна.

Answer 2

Seq.sort стабильно.