跳至主要內容
QuenTine的博客

QuenTine的博客

要多想

Rust与算法基础(14):桶排序(下)

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

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

需求分析

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

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

QuenTine...大约 14 分钟编程Rust算法
Rust与算法基础(13):桶排序(上)

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

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


QuenTine...大约 6 分钟编程Rust算法
Rust与算法基础(12):基数排序

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

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

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

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

先排个位数,得:321、153、356、26

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

然后再排十位数,得:321、26、153、356


QuenTine...大约 2 分钟编程Rust算法
Rust与算法基础(11):计数排序

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

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

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

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

对于规模为nn的数组,有kk种数据,存在knk \le n,简单的抽屉原理。


QuenTine...大约 7 分钟编程Rust算法
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算法
Rust与算法基础(9):堆排序的幂等性

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

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

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

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


QuenTine...大约 3 分钟编程Rust算法
Rust与算法基础(8):再度优化插入排序

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

证明算法的正确性

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


QuenTine...大约 8 分钟编程Rust算法
Rust与算法基础(7):归并排序(下)

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

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

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

大概是这样

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

QuenTine...大约 3 分钟编程Rust算法
Rust与算法基础(6):归并排序(中)

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

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

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

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

QuenTine...大约 7 分钟编程Rust算法
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 分钟编程Rust算法