kmk*_*mky 2 sorting dynamic-allocation rust
像sort_byon std::slice::MutableSliceAllocating或sort_byon 这样的方法collections::vec::Vec被记录为"分配大约2*n,其中n是长度".我不认为好的C++ std::sort实现(在堆上)分配,但它们实现了相同的O(n log n)复杂性.虽然,与C++ std :: sort不同,Rust排序方法是稳定的.
为什么Rust排序方法分配？对我来说,它不符合这里宣传的"零成本抽象"法案.
如评论中所述,这是一种稳定的排序,需要执行O(n)空间.最好的O(n log n)稳定排序,mergesort,需要大约½n个临时项目.(我不熟悉Rust,所以我不知道它为什么需要四次.)
可以在O(log n)空间中实现稳定排序,但仅限于采用O(nlog²n)时间的mergesort变量.
我意识到这是一个旧帖子,但我发现它在谷歌和流行的答案是错误的.实际上可以使用O(1)(非偶数对数)存储器和最坏情况O(nlogn)时间来执行稳定的就地排序.参见例如GrailSort或WikiSort.
| 归档时间： |
|
| 查看次数： |
791 次 |
| 最近记录： |