算法学习已经进入了一个新阶段，开始变得越来越难了。后面将会接触到各种各样的数据结构，这些数据结构大多是链式的。 链式的数据结构对于rust来说是个大坑，错综复杂的索引关系和Rust的内存安全机制八字不合。
今天就来个开胃菜，用链表实现桶。
首先确定一下需要什么接口，先看看序列桶用到了哪些功能，我们实现链表桶就出一个对应的：
insert方法Vec一样能转成迭代器，只需要实现吃所有权的迭代器就行，引用迭代器不用实现大家好啊，今天我们就来完成《算法导论（第三版）》第八章的最后一节——桶排序。
当我们需要对一串大小为的序列进行排序，我们可以用桶排序算法。 这一串数在这个区间中分布越平均，算法的时间复杂度就越接近，而最坏情形的时间复杂度为$\Omicron(n^2)。
上一篇我们实现了一个针对10以内数的计数排序，里面有一个回调函数的设计。 这个回调函数将在这里用到。
基数排序需要用到一个稳定排序，首先确定排序元素的进制，然后按进制从低到高位一遍遍地排序。
比如现在要升序排一组数：153、356、321、26
我们先规定这组数都是十进制的数码构成的序列，是小于1000的自然数。 基数排序需要进行这样的循环：
先排个位数，得：321、153、356、26
这里356和26的个位数是相同的，因为这是一个稳定排序，所以两者的前后顺序在排序后不变。
然后再排十位数，得：321、26、153、356
快速排序中提到了一些最坏情形，当元素不够乱序，或者是重合元素过多时，快速排序越慢。
到目前为止，我们实现的算法都是一次性准备好的输入数据，求一个输出。 这意味着输入的数据总是有限的，与之相对应的，也有“无限”的输入，比如流，这里就不展开了。
输入的数据是有限的，就意味着输入的每个元素的种类是有限的。如果每个元素不是各不相同，那就必然有重复的数据。
对于规模为的数组，有种数据，存在，简单的抽屉原理。
先上实现
pub struct QuickSorter<'a, Seq>(pub &'a mut Seq);
impl<'a, Elem> Sorter for QuickSorter<'a, Vec<Elem>> {
type Element = Elem;
fn sort_by(&mut self, compare: fn(prev: &Self::Element, next: &Self::Element) -> bool) {
let vec = &mut self.0;
if vec.len() < 2 {
return;
}
quick_sort(vec, compare, 0, vec.len());
}
}
fn quick_sort<T>(
vec: &mut Vec<T>,
compare: fn(prev: &T, next: &T) -> bool,
first: usize,
end: usize
) {
if end - first > 1 {
// 用相同的末尾开区间原则，避免usize在0的情况下-1（即使是safe代码，这还是会panic）
let divider = partrition(vec, compare, first, end);
quick_sort(vec, compare, first, divider);
quick_sort(vec, compare, divider + 1, end);
}
}
fn partrition<T>(
vec: &mut Vec<T>,
compare: fn(prev: &T, next: &T) -> bool,
first: usize,
end: usize
) -> usize {
// 随机选一个主元，让划分更平均，但这样强行换位置，就做不到幂等了
// 而且最后一个元素的大小本来就是随机的，所以再随机并没有意义
// let random_pivot = rand::thread_rng().gen_range(first..end);
let last = end - 1;
// unsafe {
// ptr::swap_nonoverlapping(&mut vec[random_pivot], &mut vec[last], 1);
// }
let mut i = first;
for j in first..last {
// 最后一个是待换的
if compare(&vec[j], &vec[last]) {
unsafe {
ptr::swap_nonoverlapping(&mut vec[i], &mut vec[j], 1);
}
i += 1;
}
}
unsafe {
ptr::swap_nonoverlapping(&mut vec[i], &mut vec[last], 1);
}
i
}
之前的文章中提到了比较函数中，小于号与小于等于号的区别。 比较函数应当符合许多性质，首先应当符合的就是传递性，如果函数返回的结果是随机的，那么整个排序的结果也是随机的。
比较函数使用小于号会使等于的情况下，把本来的先后关系对调。待插入对象是在已插入数组右边的，一直在向左移动。 所以遇“等”就停合情合理。
但当用同样的测试测下面这个堆排序，就出了问题。
当vec里存在两个key相同的元素时，排序与理想的结果不符。两个相同key的元素应当在排序后维持原来的左右关系，然而并没有。
前面已经介绍了插入排序和归并排序以及实现，这都是书上教的，书本已经证明了算法的正确性。 但当我们需要自己发明一个算法或者做习题的时候，得自己想方法，还得证明方法的正确性。 运算的规模是个变量，证明算法正确性，本身就需要递归的方式，用数学归纳法或者强归纳法去证明。
数学归纳法就是对于一系列命题，当为真，且也为真时， 都为真。
上一章结尾提到，反复复制还有优化空间，可以优化成环状的。 在递推到最小单位的数组后，每次回归都是归并到更大的临时向量，最终回归到原来的向量。 而在叶子节点，需要获得原来向量对应位置的数据，所以整个算法的拷贝流程是这样的
分析这些需求，可以简单定义一下接口是怎样的：
首先，排序函数依然是对原向量的修改，所以递归函数必须有vec: &mut Vec<T>这个参数。
大概是这样
merge_sort(vec, compare, 0, vec.len());
上一篇结尾用了forget函数避免了资源的重复释放，但是这种方法需要再钻进临时向量中，对元素一个个执行。 其实有另一种方法，可以在一开始就把资源标记为不需要释放，那就是 ManuallyDrop。
官方文档里的例子是类似这样的用法：
use std::mem::ManuallyDrop;
let mut x = ManuallyDrop::new(String::from("Hello World!"));
我们用了一个我们认为安全的复制方法，绕过Copy Trait实现了向量内元素的移动。然而它真的安全吗？
在插入排序的单元测试里加入这么一个用例：
#[test]
fn it_struct_sort_ascending_equal_box() {
#[derive(Debug, PartialEq)]
struct Foo {
id: u32,
name: &'static str,
}
let mut v = vec![
Box::new(Foo {
id: 22,
name: "ZS",
}),
Box::new(Foo {
id: 43,
name: "LS",
}),
Box::new(Foo {
id: 145,
name: "WW",
}),
Box::new(Foo {
id: 1,
name: "ZL",
}),
Box::new(Foo {
id: 9,
name: "SQ",
}),
Box::new(Foo {
id: 43,
name: "LS2",
})
];
InsertionSorter(&mut v).sort_by(|prev, next| prev.id <= next.id);
assert_eq!(
v,
vec![
Box::new(Foo {
id: 1,
name: "ZL",
}),
Box::new(Foo {
id: 9,
name: "SQ",
}),
Box::new(Foo {
id: 22,
name: "ZS",
}),
Box::new(Foo {
id: 43,
name: "LS",
}),
Box::new(Foo {
id: 43,
name: "LS2",
}),
Box::new(Foo {
id: 145,
name: "WW",
})
]
);
}