爲什麼Rust的排序方法分配內存？

類似sort_by的方法在std::slice::MutableSliceAllocating或sort_by上collections::vec::Vec記載爲「分配大約2 * n，其中n是長度」。我不認爲好的C++ std::sort實現分配（在堆上），但它們完成相同的O（n log n）複雜性。雖然，Rust排序方法與C++ std :: sort不同，但它們是穩定的。爲什麼Rust的排序方法分配內存？

爲什麼Rust排序方法分配？對我來說，它不適合「零成本抽象」票據廣告here。

來源

2014-10-07 kmky

您引用的'sort_by'是穩定的，所以您應該將它與cpp的[穩定排序]（http://en.cppreference.com/w/cpp/algorithm/stable_sort）進行比較，它會分配內存以實現複雜性較低。 – aochagavia 2014-10-07 13:03:29

@aochagavia，哦，我不知道（也沒有打擾檢查）。 Rust標準庫中是否存在不穩定的排序功能？ – kmky 2014-10-07 13:11:36

我不知道：如果沒有標準的不穩定排序，我不會感到驚訝，因爲語言還沒有達到1.0。也許你可以提交公關！ – aochagavia 2014-10-07 13:51:11

正如評論所述，這是一個穩定的排序，它需要O（n）空間來執行。最好的O（n log n）穩定排序合併排序需要大約150個臨時項目。（我對Rust不熟悉，所以我不知道它爲什麼需要四次。）

在O（log n）空間中可以實現穩定的排序，但只有通過mergesort variant才能實現O（n log 2） n）時間。

來源

2014-10-07 13:19:37

我意識到這是一箇舊的帖子，但我發現它在谷歌和流行的答案是錯誤的。事實上，使用O（1）（甚至不記錄）內存和最壞情況O（nlogn）時間來執行穩定的就地排序是可能的。例如參見GrailSort或WikiSort。

來源

2015-04-25 08:42:54 terpstra

爲什麼Rust的排序方法分配內存？

回答

相關問題