首页 | QuenTine的博客

Rust与算法基础（14）：桶排序（中）

算法学习已经进入了一个新阶段，开始变得越来越难了。后面将会接触到各种各样的数据结构，这些数据结构大多是链式的。链式的数据结构对于rust来说是个大坑，错综复杂的索引关系和Rust的内存安全机制八字不合。

今天就来个开胃菜，用链表实现桶。

需求分析

首先确定一下需要什么接口，先看看序列桶用到了哪些功能，我们实现链表桶就出一个对应的：

建造桶的集合还是用Vec实现，只是桶换成链表而已
不需要插入后再集中排序，而是插入时就插入指定的位置，所以需要一个insert方法
桶要像Vec一样能转成迭代器，只需要实现吃所有权的迭代器就行，引用迭代器不用实现

QuenTine...大约 14 分钟

Rust与算法基础（13）：桶排序（上）

大家好啊，今天我们就来完成《算法导论（第三版）》第八章的最后一节——桶排序。

当我们需要对一串大小为 $[0,1)$ 的序列进行排序，我们可以用桶排序算法。这一串数在这个区间中分布越平均，算法的时间复杂度就越接近 $\Omicron(n)$ ，而最坏情形的时间复杂度为$\Omicron(n^2)。

QuenTine...大约 6 分钟

Rust与算法基础（12）：基数排序

上一篇我们实现了一个针对10以内数的计数排序，里面有一个回调函数的设计。这个回调函数将在这里用到。

基数排序需要用到一个稳定排序，首先确定排序元素的进制，然后按进制从低到高位一遍遍地排序。

比如现在要升序排一组数：153、356、321、26

我们先规定这组数都是十进制的数码构成的序列，是小于1000的自然数。基数排序需要进行这样的循环：

先排个位数，得：321、153、356、26

这里356和26的个位数是相同的，因为这是一个稳定排序，所以两者的前后顺序在排序后不变。

然后再排十位数，得：321、26、153、356

QuenTine...大约 2 分钟

Rust与算法基础（11）：计数排序

当输入数据的种类是可以确定的

快速排序中提到了一些最坏情形，当元素不够乱序，或者是重合元素过多时，快速排序越慢。

到目前为止，我们实现的算法都是一次性准备好的输入数据，求一个输出。这意味着输入的数据总是有限的，与之相对应的，也有“无限”的输入，比如流，这里就不展开了。

输入的数据是有限的，就意味着输入的每个元素的种类是有限的。如果每个元素不是各不相同，那就必然有重复的数据。

对于规模为 $n$ 的数组，有 $k$ 种数据，存在 $k \le n$ ，简单的抽屉原理。

QuenTine...大约 7 分钟

Rust与算法基础（10）：快速排序

先上实现

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
}

QuenTine...大约 3 分钟

Rust与算法基础（9）：堆排序的幂等性

之前的文章中提到了比较函数中，小于号与小于等于号的区别。比较函数应当符合许多性质，首先应当符合的就是传递性，如果函数返回的结果是随机的，那么整个排序的结果也是随机的。

比较函数使用小于号会使等于的情况下，把本来的先后关系对调。待插入对象是在已插入数组右边的，一直在向左移动。所以遇“等”就停合情合理。

但当用同样的测试测下面这个堆排序，就出了问题。

当vec里存在两个key相同的元素时，排序与理想的结果不符。两个相同key的元素应当在排序后维持原来的左右关系，然而并没有。

QuenTine...大约 3 分钟

Rust与算法基础（8）：再度优化插入排序

前面已经介绍了插入排序和归并排序以及实现，这都是书上教的，书本已经证明了算法的正确性。但当我们需要自己发明一个算法或者做习题的时候，得自己想方法，还得证明方法的正确性。运算的规模是个变量，证明算法正确性，本身就需要递归的方式，用数学归纳法或者强归纳法去证明。

证明算法的正确性

数学归纳法就是对于一系列命题 $p_1, p_2, ... , p_n$ ，当 $p_1$ 为真，且 $p_i \rightarrow p_{i+1}$ 也为真时， $p_1, p_2, ... , p_n$ 都为真。

QuenTine...大约 8 分钟

Rust与算法基础（7）：归并排序（下）

上一章结尾提到，反复复制还有优化空间，可以优化成环状的。在递推到最小单位的数组后，每次回归都是归并到更大的临时向量，最终回归到原来的向量。而在叶子节点，需要获得原来向量对应位置的数据，所以整个算法的拷贝流程是这样的

分析这些需求，可以简单定义一下接口是怎样的：

首先，排序函数依然是对原向量的修改，所以递归函数必须有vec: &mut Vec<T>这个参数。

大概是这样

merge_sort(vec, compare, 0, vec.len());

QuenTine...大约 3 分钟

Rust与算法基础（6）：归并排序（中）

除了forget外，另一种解决方式

上一篇结尾用了forget函数避免了资源的重复释放，但是这种方法需要再钻进临时向量中，对元素一个个执行。其实有另一种方法，可以在一开始就把资源标记为不需要释放，那就是 ManuallyDrop。

官方文档里的例子是类似这样的用法：

use std::mem::ManuallyDrop;
let mut x = ManuallyDrop::new(String::from("Hello World!"));

QuenTine...大约 7 分钟

Rust与算法基础（4++）：你以为的安全真的安全吗？

我们用了一个我们认为安全的复制方法，绕过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",
            })
        ]
    );
}

QuenTine...大约 5 分钟