已弃用

实际上已经没有必要使用这个库了。它所有好的功能都已经集成到Rust标准库的 std::sort_unstable 中，它甚至使用了更好的算法。只需使用那个。

quickersort

文档

这是 introsort 排序算法的实现。

这是 veddan/rust-introsort 的分支，并进行了一些改进。

要使用 cargo，请将以下内容添加到您的 Cargo.toml

[dependencies]
quickersort = "3.0"

并在您的crate根目录中添加

extern crate quickersort;

接口

该接口与标准库中的 sort 和 sort_by 函数类似。

示例

extern crate quickersort;

fn main() {
    let mut ss = vec!["Introsort", "or", "introspective", "sort", "is",
                      "a", "hybrid", "sorting", "algorithm", "that",
                      "provides", "both", "fast", "average",
                      "performance", "and", "(asymptotically)", "optimal",
                      "worst-case", "performance"];
    quickersort::sort(&mut ss[..]);
    println!("alphabetically");
    for s in ss.iter() { println!("\t{}", s); }
    quickersort::sort_by(&mut ss[..], &|a, b| a.len().cmp(&b.len()));
    println!("\nby length");
    for s in ss.iter() { println!("\t{}", s); }
}

与标准库中的排序函数不同，introsort 不是稳定的排序。

细节

在核心，它是一个双轴快速排序。对于具有许多相等元素的分区，它将使用针对此情况优化的单轴快速排序。它检测快速排序中的过度递归，并在需要时切换到堆排序，保证所有输入的 O(n log(n)) 运行时间。对于小的分区，它使用插入排序而不是快速排序。

与 std 排序不同，它不分配。

性能

它非常快，在所有我尝试的数据集上都优于标准排序。性能差异取决于数据的特征。在大型、完全随机数组中，introsort 仅比标准排序快 5-10%。然而，如果数据具有少量唯一值或（部分）排序（包括逆序数据），introsort 的性能将大大提高。对于排序数据，introsort 快 ~4-5 倍，而对于唯一值较少的数据，它可以快 20 倍以上。

详细基准数据（目前仅限整数）可用。

浮点数

如果使用“float”特性（默认选项）构建crate，则还包括一个sort_floats函数。浮点数不是Ord，只有PartialOrd，因此不能在它们上使用sort。sort_floats使用的排序方式为

| -inf | < 0 | -0 | +0 | > 0 | +inf | NaN |

sort_floats比将实现此排序的比较函数传递给sort_by要高效得多。