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

Question

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

А если нет, то как написать стабильный вид в F #?

Answer 1

Seq.sort стабильный.

Answer 2

Ответ на ваш вопрос: 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 

Теперь давайте посмотрим на List documentation:

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

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