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

现在让我们看一下List文档:

此方法使用Array.Sort,它使用QuickSort算法.此实现执行不稳定的排序; 也就是说,如果两个元素相等,则可能不会保留它们的顺序.相反,稳定的排序保留了相等元素的顺序.

如此不稳定.如果要进行稳定排序,可以实现合并排序或仔细快速排序.然而,稳定版快速排序效率较低.