Introsort

这是 introsort 排序算法的实现。

此包不依赖于 std，并且可以与 #![no_std] 包一起使用。但是，它依赖于 core，除了测试之外没有其他依赖。

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

[dependencies]
introsort = "0.5.1"

并在您的包根目录中添加

extern crate introsort;

接口

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

示例

extern crate introsort;

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"];
    introsort::sort(&mut ss[..]);
    println!("alphabetically");
    for s in ss.iter() { println!("\t{}", s); }
    introsort::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要高效得多。

由于从标准库中删除了Float特质，启用浮点数支持将引入std作为传递依赖（#3）。这个问题应该只是暂时的，在我找到好的解决方案之前。在不启用浮点数支持的情况下构建（在[dependencies.introsort]下添加default-features = false）仍然可以通过#![no_std]工作。