built-in [T]::sort
method使用什么算法?是否可以查看该方法的代码?
根据文件:
sort
:
Current implementation
当前算法是受timsort启发的自适应迭代合并排序。它被设计为在切片几乎被分类的情况下非常快,或者由一个接一个地连接的两个或更多个分类序列组成。
此外,它分配临时存储大小为self的一半,但对于短切片,则使用非分配插入排序。
至于标准库的其余部分和整个编译器,源代码是available on GitHub。
Current implementation
目前的算法基于Orson Peters的pattern-defeating quicksort,它结合了随机快速排序的快速平均情况和最快的最差情况,同时在具有某些模式的切片上实现了线性时间。它使用一些随机化来避免退化情况,但使用固定种子来始终提供确定性行为。
它通常比稳定分拣更快,除了少数特殊情况,例如当切片由几个连接的排序序列组成时。
来源也是available on GitHub。
(重点是我的)
标准答案是,我认为,阅读精细手册;-)
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
函数,在此定义: