sortrs

使用内省排序的 Rust 快速不稳定排序。

Rust 默认的排序是 std::slice::SliceExt::sort_by。它使用归并排序实现，执行原地稳定的排序，复杂度为 O(n log n)，并分配大约 2 * n T 字节。比较需要 Ord 特性。

如果不需要稳定的排序，则可以使用不同的排序算法，该算法不执行内存分配，只需要 PartialOrd 特性。

Introsort 或内省排序是 C++ std::sort 的默认不稳定排序算法。

从 维基百科上的 Introsort

排序使用 Introsort 算法实现。Introsort 或内省排序是一种混合排序算法，它提供了快速的平均性能和（渐近的）最优最坏情况性能。它从快速排序开始，当递归深度超过基于（排序元素数量的对数）的某个级别时，切换到堆排序。它结合了两种算法的优点，在典型数据集上的性能与快速排序相当，并且由于堆排序，最坏情况下的运行时间为 O(n log n)。

性能

Introsort 在所有自己的基准测试中均优于 Rust 的默认归并排序，特别是在排序或近乎排序的数据中表现尤为出色。

以下数据由在 Intel(R) Core(TM) i7-4710HQ CPU @ 2.50GHz 运行 Linux 3.16.0-28 x86_64 的系统上运行的 cargo bench 生成。

introsort_big_random_large   ... bench:    735398 ns/iter (+/- 8984) = 434 MB/s
introsort_big_random_medium  ... bench:      4165 ns/iter (+/- 317) = 768 MB/s
introsort_big_random_small   ... bench:       136 ns/iter (+/- 3) = 1176 MB/s
introsort_big_sorted         ... bench:    147710 ns/iter (+/- 5675) = 2166 MB/s
introsort_random_large       ... bench:    498945 ns/iter (+/- 7336) = 160 MB/s
introsort_random_medium      ... bench:      2764 ns/iter (+/- 133) = 289 MB/s
introsort_random_small       ... bench:        96 ns/iter (+/- 2) = 416 MB/s
introsort_sorted             ... bench:     87369 ns/iter (+/- 1538) = 915 MB/s
stdsort_big_random_large     ... bench:    932398 ns/iter (+/- 18704) = 343 MB/s
stdsort_big_random_medium    ... bench:      4218 ns/iter (+/- 82) = 758 MB/s
stdsort_big_random_small     ... bench:       142 ns/iter (+/- 4) = 1126 MB/s
stdsort_big_sorted           ... bench:    375462 ns/iter (+/- 7778) = 852 MB/s
stdsort_random_large         ... bench:    550943 ns/iter (+/- 7290) = 145 MB/s
stdsort_random_medium        ... bench:      2822 ns/iter (+/- 76) = 283 MB/s
stdsort_random_small         ... bench:        96 ns/iter (+/- 2) = 416 MB/s
stdsort_sorted               ... bench:    236815 ns/iter (+/- 8846) = 337 MB/s

用法

在您的 Cargo.toml 中添加以下内容

[dependencies]
sortrs = "*"

并在您的 crate 根目录中添加以下内容

extern crate sortrs;