ky
诸如sort_byonstd::slice::MutableSliceAllocating或sort_byon之类的collections::vec::Vec方法记录为“分配大约2 * n，其中n为长度”。我不认为良好的C ++std::sort实现会在堆上分配资源，但是它们实现了相同的O（n log n）复杂度。尽管，Rust排序方法很稳定，与C ++ std :: sort不同。
为什么Rust排序方法分配？对我来说，这不适合此处宣传的“零成本抽象”法案。
弗雷德·富
如评论中所述，这是一种稳定的排序，需要O（n）空间才能执行。最佳O（n log n）稳定排序，mergesort需要大约½n个临时项。（我对Rust不熟悉，所以我不知道为什么它需要它的四倍。）
稳定的排序可以在O（log n）空间中实现，但只能通过需要O（nlog²n）时间的mergesort变体来实现。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
我来说两句