Rust 编程语言虽然有内置 BTreeSet 结构体,可以保证插入至该结构中的元素是有经过排序的。但 BTreeSet 是一个 Set 数据结构,无法保存复数个逻辑上相同的数据,所以在一些情况下我们还是需要用比较单纯的 Vec 结构或是其它的数据结构来保存已排序的数据。

先请看以下的代码:

fn main() {
    let mut v = vec![1, 3];

    // insert 2
}

假设我们不知道变量 v 保存的 Vec 结构实体内有什么数据,若要在程序第 2 行之后,插入元素 2 至 Vec 结构实体并保留递增顺序的话,该怎么做?

最简单的方式自然是先把 2 给 push 到 Vec 数据结构的最后面,接着再去调用这个 Vec 结构实体的 sort 方法或是 sort_unstable 方法,如下:

fn main() {
    let mut v = vec![1, 3];

    v.push(2);
    v.sort_unstable();
}

但是这样做的效率并不是很好,因为我们已经知道这个 Vec 结构实体在被插入新元素之前是递增顺序了,没有必要再全部重排。

所以比较好的作法是,利用插入排序法(只需迭代一次)来进行插入,如下:

fn main() {
    let mut v = vec![1, 3];

    v.push(2);
    insertion_sort_single(&mut v);
}

fn insertion_sort_single(array: &mut [i32]) {
    let i = array.len() - 1;

    let temp = array[i];

    let mut j = i - 1;

    while temp < array[j] {
        array[j + 1] = array[j];

        if j == 0 {
            array[j] = temp;
            return;
        }

        j -= 1;
    }

    array[j + 1] = temp;
}

有关于插入排序法的介绍可以参考这篇文章:

不过以上的插入排序法的实作是一个元素一个元素进行搬移的动作,我们其实可以单纯地从 Vec 数据结构的最后端去做线性搜索,寻找适当的插入位置,再使用 Vec 结构实体提供的 insert 方法来插入会比较好。程序如下:

fn main() {
    let mut v = vec![1, 3];

    let index = v.iter().copied().rposition(|e| e <= 2).map(|index| index + 1).unwrap_or(0);
    v.insert(index, 2);
}

有关于线性搜索法的介绍可以参考这篇文章:

不过既然提到了线性搜索法,且又是在数据已排序的情况下,自然就会去想到二元搜索法。在这边用二元搜索法也是可以的,但要注意二元搜索法比较适合用在数据长度比较长,或是两元素之间进行比较时所需的开支(overhead)有点大的时候。

Vec 结构实体提供的 binary_search 方法,本身就会在找不到元素时回传该元素如果存在,应该要被放在哪个索引值下,直接拿来利用即可。程序如下:

fn main() {
    let mut v = vec![1, 3];

    let index = match v.binary_search(&2) {
        Ok(index) => index + 1,
        Err(index) => index
    };
    
    v.insert(index, 2);
}

有关于二元搜索法的介绍可以参考这篇文章:

所以在 Rust 中要将元素插入至已排序好的 Vec 结构实体中,是一件简单的事情。不过简单的事情每次要用的时候都要再写一次差不多的代码也是挺无聊的,因此笔者另外做了一个套件来达成这个功能。当然,也不是只有支持 Vec 结构体而已。

Sorted Insert

「Sorted Insert」是笔者开发的套件,提供了一些特性,可以将元素插入至已排序好的集合中,并且维持集合的排序。

Crates.io

Cargo.toml

sorted-insert = "*"

使用方法

直接看以下例子吧!

use sorted_insert::SortedInsert;

let mut v = vec![1, 5];

v.sorted_insert_asc(2);

assert_eq!([1, 2, 5], v.as_slice());
use sorted_insert::SortedInsertBinary;

let mut v = vec![5, 1];

v.sorted_insert_desc_binary(2);

assert_eq!([5, 2, 1], v.as_slice());
use sorted_insert::SortedInsertByKey;

#[derive(Debug, Copy, Clone, Eq, PartialEq)]
struct A(i32, i32);

let mut v = vec![A(1, 10), A(2, 20)];

v.sorted_insert_asc_by_key(A(1, 15), |e| &e.1);

assert_eq!([A(1, 10), A(1, 15), A(2, 20)], v.as_slice());