sorting - F# ResizeArray sortBy 稳定吗？

Question

函数 ResizeArray.sortBy 是否进行稳定排序，即它不会更改与键函数具有相同值的元素的顺序？

如果没有，如何在 F# 中编写稳定排序？

Answer 1

您的问题的答案是不稳定。

第一个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 :

This method uses Array.Sort, which uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

太不稳定了。如果你想要稳定的排序，你可以实现合并排序或仔细的快速排序。然而稳定版本的快速排序效率较低。