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列表集合別名：

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

現在讓我們來看看List documentation：

這種方法使用Array.Sort，其中 使用QuickSort算法ithm。這個 執行執行不穩定的 排序;也就是說，如果兩個元素是 相等，則它們的順序可能不會被保存爲 。相反，穩定的分類 保留了 相等的元素的順序。

因此不穩定。如果你想要一個穩定的排序，你可以實現合併排序或仔細的快速排序。但穩定版本的快速排序效率較低。