人体工程学 Stooge 排序实现。

实现了 3 种 Stooge 排序方法 [T]/Vec<T>

• .stooge_sort() (适用于 Ord 类型)
• .stooge_sort_by() (适用于其他所有类型；自行提供比较函数！)
• .stooge_sort_by_key() (也适用于其他所有类型)

用法

将以下内容添加到您的 Cargo.toml 文件中，

[dependencies]
stoogesort = "0.2.0"

并导入 Stooge 扩展 trait。

use stoogesort::Stooge;

用法应与 slice::sort() 和 slice::sort_by() 相同。

示例

使用 .stooge_sort() 对 Ord 类型进行排序

use stoogesort::Stooge;
let mut nums = [3, 2, 1, -5];
nums.stooge_sort();
assert_eq!(nums, [-5, 1, 2, 3]);

使用 .stooge_sort_by() 对 PartialOrd 类型进行排序

use stoogesort::Stooge;
let mut floats = [0.1, 0.0, 1.0, -1.6];
floats.stooge_sort_by(|a, b| a.partial_cmp(b).unwrap());
assert_eq!(floats, [-1.6, 0.0, 0.1, 1.0]);

对末尾带数字的字符串进行排序

use stoogesort::Stooge;
let mut s = [ "foo_1", "bar_0", "quux_2" ];
s.stooge_sort_by_key(|t| t.split('_').last().unwrap().parse::<i64>().unwrap());
assert_eq!(s, [ "bar_0", "foo_1", "quux_2" ]);

致谢

• Rust 项目代码和文档（许可证在 LICENSE.rust 中）我公然剽窃

• Stooge 排序的 Wikipedia 文章中的伪代码

先有技术（或：“为什么要重复做？”）

在一个“闪电般快速”的语言中实现慢速算法很有趣！

此外，我想学习如何编写库（以及一个有自然界面的库），使用 traits，并将库发布到 crates.io。

据我所知，已经存在2种Stooge排序实现（不包括承诺包含Stooge排序的crate）

• stooge

• sorting_rs

冒着听起来粗鲁的风险，我非常喜欢它们。

stooge

stooge在这里可以原谅，因为它是明确作为学习项目编写的，但这是有说明性的。

摘自该crate的README（在Rust 2015的荣耀中）

extern crate stooge;

fn main() {
	let mut v: Vec<i32> = vec![1, 5, 4, 3];
	stooge::sort(&mut v);
	return v; // [1, 3, 4, 5]
}

名字很聪明，但并不特别有利于生产使用——如果这是一个严肃的项目，我可能不得不编写 stooge::sort(v) 或 sort(v) 而不是 v.sort()。这是倒序的。

sort()函数也实现了在[T: PartialOrd]上，这让我感到不满意。更多内容将在下一小节中介绍。

sorting_rs

这个版本理论上是为了'生产'使用（根据版本号判断），或者至少是为了分析。然而，它的接口仍然……很奇怪。

let mut vec = vec![5,3,2,4];
sorting_rs::oddeven_sort(&mut vec);
assert_eq!(vec, &[2,3,4,5]);

这里有一个明显的接收器，它应该是一个方法。

同时，它还在[T]上实现了这些排序算法，其中T: PartialOrd，我现在将描述我的问题

PartialOrd'的.lt()（由<运算符使用）、.gt()（由>使用）及其"-or-equal-to"变体在数学上并不严密。假设有一个整数类型，由于某种原因，它有一个NaN值。我将它称为NaNInt。NaN不是数字——在比较中使用NaN是没有意义的。由于至少有一对NaNInts的比较是不可能的或没有意义的，它们形成一个偏序集。因此，NaNInt类型只能被PartialOrd。因此

use std::cmp::Ordering;

let a = NaNInt::from(1);
let b = NaNInt::from(2);
let c = NaNInt::NaN;

assert_eq!(a.partial_cmp(b), Some(Ordering::Less));
assert_eq!(a.partial_cmp(c), None);
assert_eq!(c.partial_cmp(c), None);

好的，我们没问题。这是有意义的。现在，让我们考虑当我们在一个NaN上使用.lt()和.gt()时会发生什么，记住这些方法返回一个bool，而不是一个Option。

let a = NaNInt::from(1);
let b = NaNInt::from(2);
let c = NaNInt::NaN;

assert_eq!(c > a, false);
assert_eq!(c < a, false);
assert_eq!(b < c, false);
assert_eq!(b > c, false);
assert_eq!(c > c, false);
assert_eq!(c < c, false);

没错！这是没有意义的。NaN永远不会小于或大于任何其他东西，包括它自己。这导致如果[T: PartialOrd]包含不可比较的元素对时，排序是不确定的。

的确，这在 [slice::sort_by()] 中有所记录（虽然不是直接地）。

比较函数必须为切片中的元素定义一个全序。如果排序不是全序，元素的顺序是不确定的。

因此，标准库提供了3种用于排序切片的方法（还有不稳定（这不是说stooge排序是不稳定的）和缓存的变体）。它们是

• [slice::sort()]

• [slice::sort_by()]

• [slice::sort_by_key()]

注意 Ord 对 sort() 的限制，以及在 sort_by() 上没有这样的限制。还要注意 Ord 对 sort_by_key() 中类型参数 K 的限制。

标准库通过让你看到 PartialOrd 在 sort_by() 中的错误来保护你，这是 .sort_by(|a, b| a.partial_cmp(b).unwrap()) 的错误。

因此，我在这个库中模仿了标准库。这也使得实现变得容易，因为我可以复制函数签名，有时甚至可以复制代码本身。