Rust的内置`sort`使用什么排序算法?

问题描述 投票:-1回答:2

built-in [T]::sort method使用什么算法?是否可以查看该方法的代码?

algorithm sorting rust
2个回答
6
投票

根据文件:

sort

Current implementation

当前算法是受timsort启发的自适应迭代合并排序。它被设计为在切片几乎被分类的情况下非常快,或者由一个接一个地连接的两个或更多个分类序列组成。

此外,它分配临时存储大小为self的一半,但对于短切片,则使用非分配插入排序。

至于标准库的其余部分和整个编译器,源代码是available on GitHub

sort_unstable

Current implementation

目前的算法基于Orson Peters的pattern-defeating quicksort,它结合了随机快速排序的快速平均情况和最快的最差情况,同时在具有某些模式的切片上实现了线性时间。它使用一些随机化来避免退化情况,但使用固定种子来始终提供确定性行为。

它通常比稳定分拣更快,除了少数特殊情况,例如当切片由几个连接的排序序列组成时。

来源也是available on GitHub

(重点是我的)


2
投票

标准答案是,我认为,阅读精细手册;-)

https://doc.rust-lang.org/std/primitive.slice.html#current-implementation-3

是的,通过单击每个记录项目右侧的src链接,可以查看代码。对于sort方法,这导致:

https://doc.rust-lang.org/src/alloc/slice.rs.html#206-210

它使用私有merge_sort函数,在此定义:

https://doc.rust-lang.org/src/alloc/slice.rs.html#888-990

© www.soinside.com 2019 - 2024. All rights reserved.