数据结构与算法 - Rust 语言实现

fn main() {
    let numbers: [i32; 6] = [1, 1, 2, 3, 5, 8];
    assert_eq!(numbers[0], 1);
    assert_eq!(numbers[3], 3);
    assert_eq!(numbers[5], 8);
}

交换数组中的两个元素

在进行数组排序时, 经常需要交换其中的元素, 其时间复杂度是 O(1):

fn main() {
    let mut numbers: [i32; 6] = [1, 1, 2, 3, 5, 8];
    assert_eq!(numbers[0], 1);
    numbers.swap(0, 5);
    assert_eq!(numbers[5], 1);
}

批量填充新的值

如果需要批量修改数组中的元素, 可以使用这个方法:

use std::sync::atomic::{AtomicI32, Ordering};

fn get_next_id() -> i32 {
    static NEXT_ID: AtomicI32 = AtomicI32::new(1);
    NEXT_ID.fetch_add(1, Ordering::Relaxed)
}

fn main() {
    let mut numbers = [1, 1, 2, 3, 5];
    numbers.fill(0);
    assert_eq!(numbers, [0, 0, 0, 0, 0]);
    numbers.fill_with(|| get_next_id().pow(2));
    assert_eq!(numbers, [1, 4, 9, 16, 25]);
}

反转数组 Reverse

反转数组, 就是将数组中各元素转换到它相反的位置:

第一个位置的元素移到最后一位
第二个位置的元素移到倒数第二位
依次类推

得到的结果如下图所示:

reverse array

操作过程

根据反转数组的描述, 使用靠拢型双指针法遍历整个数组, 并交换元素的值.

操作步骤如下图所示:

reverse array steps

代码实现

#![allow(unused)]
fn main() {
pub fn reverse_array(arr: &mut [i32]) {
    if arr.len() < 2 {
        return;
    }

    let mut start = 0;
    let mut end = arr.len() - 1;
    while start < end {
        let tmp = arr[end];
        arr[end] = arr[start];
        arr[start] = tmp;
        start += 1;
        end -= 1;
    }
}

#[cfg(test)]
mod tests {
    use super::reverse_array;

    #[test]
    fn test_reverse_array() {
        let mut arr = [1, 2, 3, 4, 5];
        reverse_array(&mut arr);
        assert_eq!(arr, [5, 4, 3, 2, 1]);
    }
}
}

旋转数组 Rotate

给定一个数组, 包含 n 个元素, 要求将数组中的元素都依次向左移动 k 个位置. 如果 k 小于0, 就向右移动. 比如:

输入: arr = [1, 2, 3, 4]; k = -2, 输出: arr = [3, 4, 1, 2]
输入: arr = [1, 2, 3, 4]; k = 1, 输出: arr = [2, 3, 4, 1]

首先先将问题简化:

如果向右移动 k 个位置, 其实就相当于向左移动了 n-k 个位置; 所以我们刚开始只需要考虑左移的问题
如果向左移动了 c * n + k 个位置, 就相当于向左移动了 k 个位置, 因为经过 c * n 轮移动后, 元素位置并没有变化

方法1: 使用临时数组, 拷贝一份

操作过程如下:

将 arr[k..n] 存储到临时数组
将 arr[0..k] 存储到临时数组
将临时数组中的元素拷贝回原数组

这个方法的时间复杂度是 O(n), 空间复杂度是 O(n).

代码如下:

#![allow(unused)]
fn main() {
/// 使用临时数组
pub fn rotate_left_1(slice: &mut [i32], k: usize) {
    if slice.is_empty() {
        return;
    }

    let len = slice.len();
    let k = k % len;
    if k == 0 {
        return;
    }
    debug_assert!(k > 0 && k < len);

    let mut tmp: Vec<i32> = Vec::with_capacity(len);
    // 复制第一部分
    for &num in &slice[k..] {
        tmp.push(num);
    }

    // 复制第二部分
    for &num in &slice[..k] {
        tmp.push(num);
    }

    // 写回到原数组
    for (i, &num) in tmp.iter().enumerate() {
        slice[i] = num;
    }
}

/// 支持向右旋转
#[allow(clippy::cast_possible_wrap)]
#[allow(clippy::cast_sign_loss)]
pub fn rotate_array_1(slice: &mut [i32], k: isize) {
    let len = slice.len() as isize;
    if len == 0 {
        return;
    }
    let quot: isize = k / len;
    let k = if k < 0 { (1 - quot) * len + k } else { k };

    let k = k as usize;
    rotate_left_1(slice, k);
}
}

方法2: 三次反转法

操作过程如下:

将 arr[k..n] 进行反转
将 arr[0..k] 进行反转
将 arr[..] 进行反转

这个方法是在原地操作的, 其时间复杂度是 O(n), 空间复杂度是 O(1).

流程如下图所示:

array rotate with reversal

代码如下:

#![allow(unused)]
fn main() {
/// 原地反转数组
pub fn rotate_left_2(slice: &mut [i32], k: usize) {
    if slice.is_empty() {
        return;
    }

    let len = slice.len();
    let k = k % len;
    if k == 0 {
        return;
    }
    debug_assert!(k > 0 && k < len);

    slice[k..len].reverse();
    slice[..k].reverse();
    slice.reverse();
}

/// 支持向右旋转
#[allow(clippy::cast_possible_wrap)]
#[allow(clippy::cast_sign_loss)]
pub fn rotate_array_2(slice: &mut [i32], k: isize) {
    let len = slice.len() as isize;
    if len == 0 {
        return;
    }
    let quot: isize = k / len;
    let k = if k < 0 { (1 - quot) * len + k } else { k };

    let k = k as usize;
    rotate_left_2(slice, k);
}
}

方法3: 一步到位

所谓的一步到位法, 就是先计算好每个元素在旋转后的新位置, 然后依次转移每一个元素, 一步到位; 每个元素只移动一次.

操作过程如下:

计算数组中元素个数 n 与偏移量 k 的最大公约数 divisor
然后从 0 循环到 divisor, 把数组中的元素分成以 k 为步长, 组成的集合; 如果索引值超过了数组长度, 就取余
在循环体内部, 将集合中的第一个元素存到临时变量
依次将集合中的后一元素移动前一个元素
将临时变量存储到集合中的最后一个元素
最终将该集合中所有元素依次移位

这个方法是在原地操作的, 其时间复杂度是 O(n), 空间复杂度是 O(1).

流程如下图所示:

array rotate with juggling

#![allow(unused)]
fn main() {
#[must_use]
pub fn gcd(mut a: usize, mut b: usize) -> usize {
    debug_assert!(a > 0 && b > 0);
    while a != b {
        (a, b) = if a > b { (a - b, b) } else { (b - a, a) }
    }
    a
}

/// 一步到位
pub fn rotate_left_3(slice: &mut [i32], k: usize) {
    if slice.is_empty() {
        return;
    }

    let len = slice.len();
    let k = k % len;
    if k == 0 {
        return;
    }
    debug_assert!(k > 0 && k < len);

    // 第一步: 计算最大公约数
    let divisor = gcd(k, len);

    // 第二步: 从0遍历到最大公约数, 分隔成多个子集
    for i in 0..divisor {
        // 遍历每个子集中的元素, 依次移位
        // 先将集合中的第一个元素存到临时变量
        let tmp = slice[i];
        let mut head = i;
        loop {
            let next = (head + k) % len;
            if next == i {
                break;
            }
            // 依次将集合中的后一个元素移到前一个元素所有位置
            slice[head] = slice[next];
            head = next;
        }
        // 最后临时变量的值存到集合中最后一个元素
        slice[head] = tmp;
    }
}

/// 支持向右旋转
#[allow(clippy::cast_possible_wrap)]
#[allow(clippy::cast_sign_loss)]
pub fn rotate_array_3(slice: &mut [i32], k: isize) {
    let len = slice.len() as isize;
    if len == 0 {
        return;
    }
    let quot: isize = k / len;
    let k = if k < 0 { (1 - quot) * len + k } else { k };

    let k = k as usize;
    rotate_left_3(slice, k);
}
}

前缀和数组 Prefix Sum Array

什么是前缀和数组? prefix_sum_array[i] = prefix_sum_array[i - 1] + arr[i],

上面的定义不好理解的话, 我们再看一下例子, 原数组是 arr[] = [1, 2, 3, 4, 5];, 则前缀和数组就是: prefix_sum = [1, 3, 6, 10, 15];.

前缀和数组的算法倒是蛮简单, 如下所示:

#![allow(unused)]
fn main() {
use std::ops::Add;

pub fn prefix_sum<T>(arr: &[T]) -> Vec<T>
where
    T: Clone + Add<T, Output=T>,
{
    if arr.is_empty() {
        return vec![];
    }
    let mut list = Vec::with_capacity(arr.len());
    list.push(arr[0].clone());
    for i in 1..arr.len() {
        list.push(arr[i].clone() + list[i - 1].clone());
    }
    debug_assert!(list.len() == arr.len());
    list
}
}

该算法的时间复杂度是 O(n), 空间复杂度是 O(n).

这种算法思想主要是用于缓存某些需要频繁计算的过程, 以空间换取时间.

前缀和数组的应用

给定一个数组 arr, 计算 arr[l] 与 arr[r] 之间的所有元素之和.

频繁的计算数组的部分连续项之和时, 每次计算都要从头算. 我们可以用前缀和数组, 这样每次计算时可以立即得到结果.

有下面的公式:

arr[left..=right].sum() = prefix_sum_array[right] - prefix_sum_array[left - 1];

算法实现如下:

fn prefix_sum(numbers: &[i32]) -> Vec<i32> {
    let mut accum = 0;
    let mut ps = Vec::with_capacity(numbers.len());
    for num in numbers {
        accum += num;
        ps.push(accum);
    }
    ps
}

fn main() {
    let arr = [8, 19, 28, 21, 33, 97, 62, 7, 45];
    let ps = prefix_sum(&arr);
    for left in 0..2 {
        for right in 3..arr.len() {
            let sum = if left == 0 {
                ps[right]
            } else {
                ps[right] - ps[left - 1]
            };
            let sum_slice = arr[left..=right].iter().sum();
            assert_eq!(sum, sum_slice);
        }
    }
}

Suffix Array

参考

Suffix Arrays for Competitive Programming

矩阵 Matrix

矩阵的常用操作

稀疏矩阵

矩阵是由 m 行和 n 列组成的二维数据对象, 因此总共有 m x n 个值. 如果矩阵的大多数元素都有 0 值, 则称为稀疏矩阵 sparse matrix.

我们可以只存储稀疏矩阵中的非 0 元素, 这样做的好处有:

存储空间: 非零元素的数量少于零元素的数量, 因此可以使用较少的内存来存储这些元素
计算时间: 通过逻辑设计仅遍历非零元素的数据结构可以节省计算时间

用二维数组表示稀疏矩阵会导致大量内存浪费, 因为矩阵中的零在大多数情况下都是无用的. 因此我们只存储非零元素, 而不是将零与非零元素一起存储. 这意味着用三元组 (行, 列, 值) 存储非零元素.

稀疏矩阵表示可以通过多种方式完成, 以下是两种常见的表示形式:

数组表示
链表表示

接下来的章节将分别对这两类表示形式展示详细的说明.

数组

数组表示法来存储稀疏矩阵, 就是只在数组中存储里面非零的元素.

数组中每个元素项都包含三部分:

该元素在矩阵中的行号
该元素在矩阵中的列号
该元素的值

比如:

\begin{bmatrix} \ 0 & 0 & 3 & 0 & 4 \\ 0 & 0 & 5 & 7 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 6 & 0 & 0 \ \end{bmatrix}

这个矩阵用数组存放, 效果如下图:

array sparse matrix

这种存储方式的特点是:

Row major 风格
数组中元素的排序方法是
- 从头到尾以行编号递增
- 相同行编号时, 以列编号递增
- 即整体上行编号有序递增, 整体上列编号无序, 但局部上列编号递增
查找矩阵中某个节点的值时的性能是 O(log(m) * log(n)), 其中 m 和 n 是矩阵中非 0 元素的最大行列数, 因为是有序排列的, 可以用二分查找法
比较适合存放固定不变的矩阵, 插入或者删除元素的成本比较高

算法的实现

因为数组支持随机索引, 而且都是有序存储的, 向其中插入和移除元素的操作都比较快.

#![allow(unused)]
fn main() {
use std::{fmt, mem};
use std::cmp::Ordering;

use crate::traits::IsZero;

/// Each element node in the array.
pub struct MatrixElement<T: IsZero> {
    /// Row number of element.
    pub row: usize,
    /// Column number of element.
    pub column: usize,
    /// Value of element.
    pub value: T,
}

/// Store sparse matrix with array.
pub struct ArraySparseMatrix<T: IsZero> {
    vec: Vec<MatrixElement<T>>,
}

impl<T: IsZero> ArraySparseMatrix<T> {
    #[must_use]
    pub fn construct<I, I2>(sparse_matrix: I) -> Self
    where
        I: IntoIterator<Item=I2>,
        I2: IntoIterator<Item=T>,
    {
        let mut vec = Vec::new();

        for (row, row_list) in sparse_matrix.into_iter().enumerate() {
            for (column, element) in row_list.into_iter().enumerate() {
                if element.is_not_zero() {
                    let element = MatrixElement {
                        row,
                        column,
                        value: element,
                    };
                    vec.push(element);
                }
            }
        }
        Self { vec }
    }

    #[must_use]
    #[inline]
    pub fn len(&self) -> usize {
        self.vec.len()
    }

    #[must_use]
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.vec.is_empty()
    }

    fn find_element(&self, row: usize, column: usize) -> Result<usize, usize> {
        self.vec.binary_search_by(|node| {
            match node.row.cmp(&row) {
                Ordering::Equal => node.column.cmp(&column),
                order => order
            }
        })
    }

    /// Get node value at (row, column).
    #[must_use]
    pub fn value(&self, row: usize, column: usize) -> Option<T> {
        let result = self.find_element(row, column);
        result.ok().map(|index| self.vec[index].value)
    }

    /// Get mutable reference to node value at (row, column).
    #[must_use]
    pub fn value_mut(&mut self, row: usize, column: usize) -> Option<&mut T> {
        let result = self.find_element(row, column);
        result.ok().map(|index| &mut self.vec[index].value)
    }

    /// If found old node at (row, column), returns old value; otherwise returns None.
    pub fn add_element(&mut self, row: usize, column: usize, mut value: T) -> Option<T> {
        let result = self.find_element(row, column);

pub trait IsZero: Copy {
    fn is_zero(self) -> bool;
    fn is_not_zero(self) -> bool {
        !self.is_zero()
    }
}

macro_rules! impl_is_zero {
    ($($t:ty)*) => {$(
    impl IsZero for $t {
        fn is_zero(self) -> bool {
            self == 0
        }
    }
    )*}
}

impl_is_zero! { i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize }

impl IsZero for f32 {
    fn is_zero(self) -> bool {
        self == 0.0
    }
}

impl IsZero for f64 {
    fn is_zero(self) -> bool {
        self == 0.0
    }
}
}

链表

上文介绍了使用数组存储稀疏矩阵的方法, 但该方法不适合动态地插入和删除元素. 我们可以换成链表来存储, 链表上删减节点的操作很灵活.

链表中每个节点项都包含这几部分:

该元素在矩阵中的行号
该元素在矩阵中的列号
该元素的值
指向下个节点的指针

同样的矩阵:

\begin{bmatrix} \ 0 & 0 & 3 & 0 & 4 \\ 0 & 0 & 5 & 7 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 6 & 0 & 0 \ \end{bmatrix}

用链表来记录的话, 其结构如下图所示:

linked list sparse matrix

这种存储方式的特点是:

同样是Row major 风格
链表中节点的排序方法是
- 从头到尾以行编号递增
- 相同行编号时, 以列编号递增
- 即整体上行编号有序递增, 整体上列编号无序, 但局部上列编号递增
可以在任意位置插入或者移除节点
查找元素的效率很低, 因为链表不支持随机访问, 只能从头到尾依次遍历. 其时间复杂度是 O(n), n 是矩阵中非 0 节点的个数

算法的实现

为了节省功夫, 我们使用了标准库中的双链表 LinkedList<T>, 而不是上面提到的单链表的形式.

#![allow(unused)]
fn main() {
pub trait IsZero: Copy {
    fn is_zero(self) -> bool;
    fn is_not_zero(self) -> bool {
        !self.is_zero()
    }
}

macro_rules! impl_is_zero {
    ($($t:ty)*) => {$(
    impl IsZero for $t {
        fn is_zero(self) -> bool {
            self == 0
        }
    }
    )*}
}

impl_is_zero! { i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize }

impl IsZero for f32 {
    fn is_zero(self) -> bool {
        self == 0.0
    }
}

impl IsZero for f64 {
    fn is_zero(self) -> bool {
        self == 0.0
    }
}

#![allow(dead_code)]

use std::fmt;
use std::marker::PhantomData;
use std::ptr::NonNull;

use crate::traits::IsZero;

/// Each element node in the linked list.
pub struct Node<T: IsZero> {
    /// Row number of element.
    pub row: usize,
    /// Column number of element.
    pub column: usize,
    /// Value of element.
    pub value: T,
    /// Pointer to next node.
    prev: NodePtr<T>,
    /// Pointer to next node.
    next: NodePtr<T>,
}

type NodePtr<T> = Option<NonNull<Node<T>>>;

/// Store sparse matrix with linked list.
#[allow(clippy::linkedlist)]
pub struct LinkedListSparseMatrix<T: IsZero> {
    len: usize,
    head: NodePtr<T>,
    tail: NodePtr<T>,
}

pub struct Iter<'a, T: 'a + IsZero> {
    head: NodePtr<T>,
    len: usize,
    _marker: PhantomData<&'a Node<T>>,
}

pub struct IterMut<'a, T: 'a + IsZero> {
    head: NodePtr<T>,
    len: usize,
    _marker: PhantomData<&'a mut Node<T>>,
}

impl<T: IsZero> LinkedListSparseMatrix<T> {
    #[must_use]
    pub fn construct<I, I2>(sparse_matrix: I) -> Self
    where
        I: IntoIterator<Item = I2>,
        I2: IntoIterator<Item = T>,
    {
        let mut head: NodePtr<T> = None;
        let mut tail: NodePtr<T> = None;
        let mut len: usize = 0;

        for (row, row_list) in sparse_matrix.into_iter().enumerate() {
            for (column, value) in row_list.into_iter().enumerate() {
                if value.is_not_zero() {
                    let mut node: NonNull<Node<T>> = Node::new_ptr(row, column, value);
                    len += 1;
                    if let Some(mut tail_ref) = tail {
                        unsafe {
                            node.as_mut().prev = tail;
                            tail_ref.as_mut().next = Some(node);
                        }
                    } else {
                        head = Some(node);
                    }
                    tail = Some(node);
                }
            }
        }
        Self { len, head, tail }
    }

    #[must_use]
    #[inline]
    pub const fn len(&self) -> usize {
        self.len
    }

    #[must_use]
    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    #[must_use]
    pub fn value(&self, row: usize, column: usize) -> Option<T> {
        for node in self {
            if node.row == row && node.column == column {
                return Some(node.value);
            }
            if node.row > row {
                return None;
            }
        }
        None
    }

    #[must_use]
    pub fn value_mut(&mut self, row: usize, column: usize) -> Option<&mut T> {
        for node in self.iter_mut() {
            if node.row == row && node.column == column {
                return Some(&mut node.value);
            }
            if node.row > row {
                return None;
            }
        }
        None
    }

    /// Add an element to the beginning of list.
    pub fn push_front(&mut self, row: usize, column: usize, value: T) {
        let node_ptr = Node::new_ptr(row, column, value);
        self.push_front_node(node_ptr);
    }

    /// Remove the first node in the list.
    pub fn pop_front(&mut self) -> Option<(usize, usize, T)> {
        self.pop_front_node().map(Node::into_inner)
    }

    pub fn push_back(&mut self, row: usize, column: usize, value: T) {
        let node_ptr = Node::new_ptr(row, column, value);
        self.push_back_node(node_ptr);
    }

    pub fn pop_back(&mut self) -> Option<(usize, usize, T)> {
        self.pop_back_node().map(Node::into_inner)
    }

    /// If found old node at (row, column), returns old value; otherwise returns None.
    #[must_use]
    pub fn add_element(&mut self, row: usize, column: usize, value: T) -> Option<T> {
        let len = self.len;
        for (index, node) in self.iter_mut().enumerate() {
            if node.row == row && node.column == column {
                let old_value = node.value;
                node.value = value;
                return Some(old_value);
            }
            if (node.row == row && node.column > column) || node.row > row {
                if index == 0 {
                    self.push_front(row, column, value);
                } else if index == len - 1 {
                    self.push_back(row, column, value);
                } else {
                    // Insert new node to previous of current node.
                    let new_node: NonNull<Node<T>> = Node::new_ptr(row, column, value);
                    unsafe { Self::insert_before(node, new_node) };
                    self.len += 1;
                }

                return None;
            }
        }

        // Add new node to end of list.
        self.push_back(row, column, value);
        None
    }

    /// If found node at (row, column), returns value of that node; otherwise returns None.
    #[must_use]
    pub fn remove_element(&mut self, row: usize, column: usize) -> Option<T> {
        let len = self.len;

        for (index, node) in self.iter_mut().enumerate() {
            if node.row == row && node.column == column {
                let value = node.value;
                if index == 0 {
                    self.pop_front();
                } else if index == len - 1 {
                    self.pop_back();
                } else {
                    unsafe {
                        Self::remove_node(node);
                    }
                    self.len -= 1;
                }
                return Some(value);
            }
            if (node.row == row && node.column > column) || node.row > row {
                // Node not found.
                return None;
            }
        }
        None
    }

    // Iterators
    #[must_use]
    pub const fn iter(&self) -> Iter<'_, T> {
        Iter {
            head: self.head,
            len: self.len,
            _marker: PhantomData,
        }
    }

    #[allow(clippy::needless_pass_by_ref_mut)]
    #[must_use]
    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut {
            head: self.head,
            len: self.len,
            _marker: PhantomData,
        }
    }
}

impl<T: IsZero> LinkedListSparseMatrix<T> {
    /// Insert `new_node` before `current_node`.
    unsafe fn insert_before(current_node_ref: &mut Node<T>, mut new_node: NonNull<Node<T>>) {
        if let Some(mut prev_node) = current_node_ref.prev {
            new_node.as_mut().prev = Some(prev_node);
            let current_node = prev_node.as_mut().next.take().unwrap();
            prev_node.as_mut().next = Some(new_node);

            new_node.as_mut().next = Some(current_node);
            current_node_ref.prev = Some(new_node);
        }
    }

    /// Insert `new_node` after `current_node`.
    unsafe fn insert_after(mut current_node: NonNull<Node<T>>, mut new_node: NonNull<Node<T>>) {
        if let Some(mut next_node) = current_node.as_mut().next {
            new_node.as_mut().next = Some(next_node);
            next_node.as_mut().prev = Some(new_node);
        }
        new_node.as_mut().prev = Some(current_node);
        current_node.as_mut().next = Some(new_node);
    }

    /// Remove `node` from list.
    ///
    /// Both prev and next node are valid.
    unsafe fn remove_node(node: &mut Node<T>) {
        let mut prev_node = node.prev.unwrap();
        let mut next_node = node.next.unwrap();
        prev_node.as_mut().next = Some(next_node);
        next_node.as_mut().prev = Some(prev_node);

        node.prev = None;
        node.next = None;
    }

    fn push_front_node(&mut self, node_ptr: NonNull<Node<T>>) {
        unsafe {
            (*node_ptr.as_ptr()).next = self.head;
            (*node_ptr.as_ptr()).prev = None;
        }
        let node = Some(node_ptr);

        match self.head {
            Some(head) => unsafe { (*head.as_ptr()).prev = node },
            None => self.tail = node,
        }

        self.head = node;
        self.len += 1;
    }

    fn push_back_node(&mut self, node_ptr: NonNull<Node<T>>) {
        unsafe {
            (*node_ptr.as_ptr()).next = None;
            (*node_ptr.as_ptr()).prev = self.tail;
        }
        let node = Some(node_ptr);

        match self.tail {
            Some(tail) => unsafe { (*tail.as_ptr()).next = node },
            None => self.head = node,
        }

        self.tail = node;
        self.len += 1;
    }

    fn pop_front_node(&mut self) -> Option<Box<Node<T>>> {
        self.head.map(|old_head| {
            let old_head = unsafe { Node::from_ptr(old_head) };
            self.head = old_head.next;

            match self.head {
                Some(head) => unsafe { (*head.as_ptr()).prev = None },
                None => self.tail = None,
            }

            self.len -= 1;
            old_head
        })
    }

    fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
        self.tail.map(|old_tail| {
            let old_tail = unsafe { Node::from_ptr(old_tail) };
            self.tail = old_tail.prev;

            match self.tail {
                Some(tail) => unsafe { (*tail.as_ptr()).next = None },
                None => self.head = None,
            }

            self.len -= 1;
            old_tail
        })
    }
}

impl<T: fmt::Debug + IsZero> fmt::Debug for LinkedListSparseMatrix<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self).finish()
    }
}

impl<'a, T: IsZero> IntoIterator for &'a LinkedListSparseMatrix<T> {
    type Item = &'a Node<T>;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, T: IsZero> IntoIterator for &'a mut LinkedListSparseMatrix<T> {
    type Item = &'a mut Node<T>;
    type IntoIter = IterMut<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

impl<'a, T: IsZero> Iterator for Iter<'a, T> {
    type Item = &'a Node<T>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.len == 0 {
            None
        } else {
            self.head.map(|node| unsafe {
                let node: &Node<T> = node.as_ref();
                self.len -= 1;
                self.head = node.next;
                node
            })
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }
}

impl<T: IsZero> ExactSizeIterator for Iter<'_, T> {}

impl<'a, T: IsZero> Iterator for IterMut<'a, T> {
    type Item = &'a mut Node<T>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.len == 0 {
            None
        } else {
            self.head.map(|mut node| unsafe {
                let node: &mut Node<T> = node.as_mut();
                self.len -= 1;
                self.head = node.next;
                node
            })
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }
}

impl<T: IsZero> ExactSizeIterator for IterMut<'_, T> {}

impl<T: IsZero> Node<T> {
    #[must_use]
    #[inline]
    const fn new(row: usize, column: usize, value: T) -> Self {
        Self {
            row,
            column,
            value,
            prev: None,
            next: None,
        }
    }

    #[must_use]
    #[inline]
    fn new_ptr(row: usize, column: usize, value: T) -> NonNull<Self> {
        let node = Box::new(Self::new(row, column, value));
        NonNull::from(Box::leak(node))
    }

    #[must_use]
    #[inline]
    #[allow(clippy::unnecessary_box_returns)]
    unsafe fn from_ptr(ptr: NonNull<Self>) -> Box<Self> {
        Box::from_raw(ptr.as_ptr())
    }

    #[must_use]
    #[inline]
    #[allow(clippy::boxed_local)]
    fn into_inner(self: Box<Self>) -> (usize, usize, T) {
        (self.row, self.column, self.value)
    }
}

#[allow(clippy::missing_fields_in_debug)]
impl<T: fmt::Debug + IsZero> fmt::Debug for Node<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Node")
            .field("row", &self.row)
            .field("column", &self.column)
            .field("value", &self.value)
            .finish()
}

List of Lists

稀疏矩阵的一种可能表示是列表嵌套 (List of Lists, LIL). 其中一个列表用于表示行, 每行包含三元组列表: 列索引, 值 (非零元素) 和非零元素的地址字段. 为了获得最佳性能, 两个列表都应按升序键的顺序存储.

以下面的矩阵为例:

\begin{bmatrix} \ 0 & 0 & 3 & 0 & 4 \\ 0 & 0 & 5 & 7 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 6 & 0 & 0 \ \end{bmatrix}

这个矩阵用数组存放, 效果如下图:

list of lists sparse matrix

这种存储方式的特点是:

Row major 风格
分两层链表来存储
- 第一层是行级链表, 存储非空行, 且以行号递增排序
- 第二层, 在每个行链表节点中, 存储非空列的链表, 且以列号递增排序
查找矩阵中某个节点的值时的性能是 O(m * n), 其中 m 和 n 是矩阵中非 0 元素的最大行列数, 目前使用的是顺序查找, 效率比较低
比较适合存放随时增减节点的矩阵, 插入或者删除元素的成本比较低, 很灵活, 但缓存不友好

算法的实现

为了简化实现, 我们使用了标准库中的双向链表实现.

比较复杂的操作是插入和删除节点, 这个要同时判断行列表和列列表都是有效的.

#![allow(unused)]
#![allow(clippy::linkedlist)]
#![allow(dead_code)]

fn main() {
use std::collections::LinkedList;
use std::fmt;

use crate::traits::IsZero;

#[derive(Debug)]
pub struct ListOfListsSparseMatrix<T: IsZero + fmt::Debug> {
    rows: LinkedList<Row<T>>,
    len: usize,
}

/// Row number in list is ordered ascending.
#[derive(Debug)]
pub struct Row<T: fmt::Debug> {
    row: usize,
    columns: LinkedList<Column<T>>,
}

/// Column number in list is ordered ascending.
#[derive(Debug)]
pub struct Column<T: fmt::Debug> {
    column: usize,
    value: T,
}

impl<T: IsZero + fmt::Debug> ListOfListsSparseMatrix<T> {
    #[must_use]
    pub fn construct<I, I2>(sparse_matrix: I) -> Self
    where
        I: IntoIterator<Item=I2>,
        I2: IntoIterator<Item=T>,
    {
        let mut row_list = LinkedList::new();
        let mut len = 0;

        for (row, rows) in sparse_matrix.into_iter().enumerate() {
            let mut column_list = LinkedList::new();
            for (column, element) in rows.into_iter().enumerate() {
                if element.is_not_zero() {
                    column_list.push_back(Column { column, value: element });
                }
            }
            if !column_list.is_empty() {
                len += column_list.len();
                row_list.push_back(Row { row, columns: column_list });
            }
        }
        Self { rows: row_list, len }
    }

    #[must_use]
    #[inline]
    pub const fn len(&self) -> usize {
        self.len
    }

    #[must_use]
    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Get node value at (row, column).
    #[must_use]
    pub fn value(&self, row: usize, column: usize) -> Option<T> {
        for row_list in &self.rows {
            if row_list.row == row {
                for column_element in &row_list.columns {
                    if column_element.column == column {
                        return Some(column_element.value);
                    }
                }
                break;
            }
        }
        None
    }

    /// Get mutable reference to node value at (row, column).
    #[must_use]
    pub fn value_mut(&mut self, row: usize, column: usize) -> Option<&mut T> {
        for row_list in &mut self.rows {
            if row_list.row == row {
                for column_element in &mut row_list.columns {
                    if column_element.column == column {
                        return Some(&mut column_element.value);
                    }
                }
                break;
            }
        }
        None
    }

    /// If found old node at (row, column), returns old value; otherwise returns None.
    #[allow(dead_code)]
    pub fn add_element(&self, _ow: usize, _column: usize, _value: T) -> Option<T> {
        // 1. Find the element at (row, column)
        // 2. If no columns_list found in rows, add a new one
        // 3. Add that element to selected column_list
        todo!()
        // 1. if rows list if empty, push to back
        // 2. if front
    }

    /// If found node at (row, column), returns value of that node; otherwise returns None.
    pub fn remove_element(&mut self, row: usize, column: usize) -> Option<T> {
        // 1. Find the element at (row, column)
        // 2. Remove the element in columns list
        // 3. If the columns list is empty, remove it from rows list

        let mut value = None;
        let mut row_index = 0;
        let mut remove_column_list = false;
        for row_list in &mut self.rows {
            row_index += 1;
            if row_list.row == row {
                for column_element in &mut row_list.columns {
                    if column_element.column == column {
                        value = Some(column_element.value);
                        break;
                    }
                }

                if row_list.columns.is_empty() && value.is_some() {
                    remove_column_list = true;
                }

                break;
            }
        }

        if remove_column_list {
            let mut tail = self.rows.split_off(row_index);
            // Remove that columns list.
            tail.pop_front();
            // Then merge together again.
            if !tail.is_empty() {
                self.rows.append(&mut tail);
            }
        }
        if value.is_some() {
            self.len -= 1;
        }
        value
    }
}

pub trait IsZero: Copy {
    fn is_zero(self) -> bool;
    fn is_not_zero(self) -> bool {
        !self.is_zero()
    }
}

macro_rules! impl_is_zero {
    ($($t:ty)*) => {$(
    impl IsZero for $t {
        fn is_zero(self) -> bool {
            self == 0
        }
    }
    )*}
}

impl_is_zero! { i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize }

impl IsZero for f32 {
    fn is_zero(self) -> bool {
        self == 0.0
    }
}

impl IsZero for f64 {
    fn is_zero(self) -> bool {
        self == 0.0
    }
}
}

十字链表 Orthogonal linked list

BTree

以下面的矩阵为例:

\begin{bmatrix} \ 0 & 0 & 3 & 0 & 4 \\ 0 & 0 & 5 & 7 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 6 & 0 & 0 \ \end{bmatrix}

这个矩阵用数组存放, 效果如下图:

btree sparse matrix

这种存储方式的特点是:

BTree 中节点是按照 key 的顺序进行存储的, 而我们选用 (row, column) 作为 key, 这样
- 首先以行号递增排序
- 如果行号相同, 以列号递增排序
查找/插入/删除矩阵中某个节点的值时的性能是 O(log(m * n)), 其中 m 和 n 是矩阵中非 0 元素的最大行列数
比较适合存放随时增减节点的矩阵, 插入或者删除元素的成本比较低, 很灵活
支持范围查找, 比如查找某一行中所有的列
实现简单

算法的实现

使用 BTree 进行存储, 实现起来最简单, 因为我们要求的接口与 BTreeMap 本身的接口非常匹配, 需要额外花费的精力很少.

#![allow(unused)]
fn main() {
use std::collections::BTreeMap;

use crate::traits::IsZero;

#[derive(Debug, Default, Clone, Copy, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct MatrixIndex {
    row: usize,
    column: usize,
}

/// Store sparse matrix with btree.
#[derive(Debug, Default, Clone)]
pub struct BTreeSparseMatrix<T: IsZero> {
    map: BTreeMap<MatrixIndex, T>,
}

impl<T: IsZero> BTreeSparseMatrix<T> {
    #[must_use]
    pub fn construct<I, I2>(sparse_matrix: I) -> Self
    where
        I: IntoIterator<Item=I2>,
        I2: IntoIterator<Item=T>,
    {
        let mut map = BTreeMap::new();

        for (row, row_list) in sparse_matrix.into_iter().enumerate() {
            for (column, element) in row_list.into_iter().enumerate() {
                if element.is_not_zero() {
                    map.insert(MatrixIndex { row, column }, element);
                }
            }
        }
        Self { map }
    }

    #[must_use]
    #[inline]
    pub fn len(&self) -> usize {
        self.map.len()
    }

    #[must_use]
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// Get node value at (row, column).
    #[must_use]
    pub fn value(&self, row: usize, column: usize) -> Option<T> {
        self.map.get(&MatrixIndex { row, column }).copied()
    }

    /// Get mutable reference to node value at (row, column).
    #[must_use]
    pub fn value_mut(&mut self, row: usize, column: usize) -> Option<&mut T> {
        self.map.get_mut(&MatrixIndex { row, column })
    }

    /// If found old node at (row, column), returns old value; otherwise returns None.
    pub fn add_element(&mut self, row: usize, column: usize, value: T) -> Option<T> {
        self.map.insert(MatrixIndex { row, column }, value)
    }

    /// If found node at (row, column), returns value of that node; otherwise returns None.
    pub fn remove_element(&mut self, row: usize, column: usize) -> Option<T> {
        self.map.remove(&MatrixIndex { row, column })
    }
}
}

动态数组 Vectors

另外, 像字符串这样的数据结构, 其底层也是使用动态数组 Vec<u8> 来实现的, 但是字符串的操作函数更加丰富, 我们放在后面的章节单独介绍.

动态数组的常用操作

标准库中 Vec 的实现

位图 BitSet

BitSet 又称为 bit map, bit array, bit mask 或者 bit vector, 是一个数组结构, 里面只存储单个的比特, 每一个比特可以表示两个状态. 它是一种很简单的集合数据结构.

位图的实现

#![allow(unused)]
fn main() {
use std::ops::Index;

const BITS_PER_ELEM: usize = 8;
const TRUE: bool = true;
const FALSE: bool = false;

#[derive(Debug, Clone)]
pub struct BitSet {
    bits: Vec<u8>,
}

impl Default for BitSet {
    fn default() -> Self {
        Self::new()
    }
}

impl BitSet {
    #[must_use]
    #[inline]
    pub const fn new() -> Self {
        Self { bits: Vec::new() }
    }

    #[must_use]
    #[inline]
    pub fn with_len(len: usize) -> Self {
        let bits_len = len.div_ceil(BITS_PER_ELEM);
        Self {
            bits: vec![0; bits_len],
        }
    }

    #[must_use]
    #[inline]
    pub fn from_bytes(bytes: &[u8]) -> Self {
        Self {
            bits: bytes.to_vec(),
        }
    }

    #[must_use]
    #[inline]
    pub fn as_bytes(&self) -> &[u8] {
        &self.bits
    }

    #[must_use]
    #[inline]
    pub fn into_vec(self) -> Vec<u8> {
        self.bits
    }

    fn expand(&mut self, index: usize) {
        let bits_len = (index + 1).div_ceil(BITS_PER_ELEM);
        if self.bits.len() < bits_len {
            // TODO(Shaohua): Adjust resize policy.
            self.bits.resize(bits_len, 0);
        }
    }

    pub fn set(&mut self, index: usize) {
        self.expand(index);
        let word = index / BITS_PER_ELEM;
        let bit = index % BITS_PER_ELEM;
        let flag = 1 << bit;
        self.bits[word] |= flag;
    }

    pub fn unset(&mut self, index: usize) {
        self.expand(index);
        let word = index / BITS_PER_ELEM;
        let bit = index % BITS_PER_ELEM;
        let flag = 1 << bit;
        self.bits[word] &= !flag;
    }

    pub fn flip(&mut self, index: usize) {
        self.expand(index);
        let word = index / BITS_PER_ELEM;
        let bit = index % BITS_PER_ELEM;
        let flag = 1 << bit;
        // FIXME(Shaohua):
        self.bits[word] &= !flag;
    }

    /// Check bit at `index` is set or not.
    #[must_use]
    pub fn get(&self, index: usize) -> Option<bool> {
        let word = index / BITS_PER_ELEM;
        if word >= self.bits.len() {
            return None;
        }
        let bit = index % BITS_PER_ELEM;
        let flag = 1 << bit;
        Some((self.bits[word] & flag) == flag)
    }

    /// Returns the number of bits set to `true`.
    #[must_use]
    pub fn count_ones(&self) -> usize {
        self.bits
            .iter()
            .map(|byte| byte.count_ones() as usize)
            .sum()
    }

    /// Returns the number of bits set to `false`.
    #[must_use]
    pub fn count_zeros(&self) -> usize {
        self.bits
            .iter()
            .map(|byte| byte.count_zeros() as usize)
            .sum()
    }

    #[must_use]
    #[inline]
    pub const fn iter(&self) -> BitSetIter {
        BitSetIter {
            bit_set: self,
            index: 0,
        }
    }

    /// # Panics
    /// Raise panic if length of two bitset not equal.
    #[must_use]
    pub fn union(&self, other: &Self) -> Self {
        assert_eq!(self.bits.len(), other.bits.len());
        let bits = self
            .bits
            .iter()
            .zip(other.bits.iter())
            .map(|(a, b)| a | b)
            .collect();
        Self { bits }
    }

    /// # Panics
    /// Raise panic if length of two bitset not equal.
    #[must_use]
    pub fn intersect(&self, other: &Self) -> Self {
        assert_eq!(self.bits.len(), other.bits.len());
        let bits = self
            .bits
            .iter()
            .zip(other.bits.iter())
            .map(|(a, b)| a & b)
            .collect();
        Self { bits }
    }

    /// # Panics
    /// Raise panic if length of two bitset not equal.
    #[must_use]
    pub fn difference(&self, other: &Self) -> Self {
        assert_eq!(self.bits.len(), other.bits.len());
        let bits = self
            .bits
            .iter()
            .zip(other.bits.iter())
            .map(|(a, b)| a & !b)
            .collect();
        Self { bits }
    }
}

impl From<String> for BitSet {
    fn from(value: String) -> Self {
        Self {
            bits: value.into_bytes(),
        }
    }
}

impl From<&str> for BitSet {
    fn from(s: &str) -> Self {
        Self::from_bytes(s.as_bytes())
    }
}

macro_rules! from_number_impl {
    ($($t:ty)*) => {$(
        impl From<$t> for BitSet {
            fn from(value: $t) -> Self {
                Self {
                    bits: value.to_le_bytes().to_vec(),
                }
            }
        }
    )*};
}

from_number_impl! {i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize}

impl Index<usize> for BitSet {
    type Output = bool;

    fn index(&self, index: usize) -> &Self::Output {
        if self.get(index).expect("index out of range") {
            &TRUE
        } else {
            &FALSE
        }
    }
}

pub struct BitSetIter<'a> {
    bit_set: &'a BitSet,
    index: usize,
}

impl Iterator for BitSetIter<'_> {
    type Item = bool;

    fn next(&mut self) -> Option<Self::Item> {
        let is_set = self.bit_set.get(self.index);
        if is_set.is_some() {
            self.index += 1;
        }
        is_set
    }
}

impl<'a> IntoIterator for &'a BitSet {
    type IntoIter = BitSetIter<'a>;
    type Item = bool;
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}
}

布隆过滤器 Bloom filter

Hashed Array Tree

字符串 String

字符串编码

字符串的常用操作

链表 List

与数组类似, 链表也是计算机科学里的常用的数据结构.

与数组相比, 链表的最大特点是:

支持高效地在任意节点位置插入和删除元素
在内存中非连续地存储各个元素
不支持随机访问各个元素

链表是线性数据结构 (linear data structure), 它由一系列的节点组成; 节点内部保存着元素的值, 节点之间使用指针或者引用引连, 可以顺着指针/引用找到下个节点在内存中的位置.

list layout

链表的类型

根据链表的结构, 有这几种类型:

单链表 singly linked list
双链表 doubly linked list
环状链表 circular linked list
环状双链表 doubly circular linked list
header linked list
multiply linked list
unrolled linked list

单链表 Singly Linked List

在单链表中, 每个节点包括一个指针, 指向下个节点.

特点:

只能从链表头部单向地遍历整个链表
每个节点只需要存储一个指针元素, 可以节省一些内存空间

单链表的结构如下图所示:

singly linked list

C语言中对应的结构体声明如下:

// 单链表
struct singly_list_s {
  int value;
  struct singly_list_s* next;
};

双链表 Doubly Linked List

在双链表中, 每个节点持有两个指针, 分别指向它的前一个节点以及后一个节点.

特点:

可以向前和向后双向遍历整个链表
每个节点要存储两个指针, 占用更多的内存空间

双链表的结构如下图所示:

doubly linked list

C语言中对应的结构体声明如下:

// 双链表
struct doubly_list_s {
  int value;
  struct doubly_list_s* previous;
  struct doubly_list_s* next;
};

环状链表 Circular Linked List

与单链表不同, 环状链表的最后一个节点指向链表的第一个节点, 形成一个环.

特点是:

遍历环状链表一周后, 可以回到起始节点

环状链表的结构如下图所示:

circular linked list

C语言中对应的结构体声明如下:

// 环状链表
struct circular_list_s {
  int value;
  struct circular_list_s* next;
};

环状双链表 Doubly Circular Linked List

与双链表不同, 环状双链表的首尾节点也有指针相互链表, 所以它里面不存在指向空节点的指针.

特点:

支持向前向后双向遍历
遍历链表一周之后会回到起始点

环状双链表的结构如下图所示:

doubly circular linked list

C语言中对应的结构体声明如下:

// 环状双链表
struct doubly_circular_list_s {
  int value;
  struct doubly_circular_list_s* previous;
  struct doubly_circular_list_s* next;
};

Header Linked List

这种链表是对单链表的改进, 在实现的编码中, 如果链表指针指向链表中的第一个节点时, 有很多操作, 比如删除节点或者交换节点的操作, 处理起来比较麻烦, 需要单独考虑第一个节点.

为此, 我们可以在第一个节点之前再加一个 header node, 或者称为 dummy node, 链表的指针指向该节点, 然后该节点再指向链表的真正存放数据元素的第一个节点.

特点:

支持向后单向遍历节点
更方便针对链表节点的操作

该链表的结构如下图所示:

header linked list

C语言中对应的结构体声明如下:

// 环状双链表
struct doubly_circular_list_s {
  int value;
  struct doubly_circular_list_s* previous;
  struct doubly_circular_list_s* next;
};

Multiply Linked List

上面介绍的双链表, 每个节点有两个指针分别指向节点的前后相邻节点.

如果一个节点中有多个指针指向别的节点呢? 这就是 Multiply Linked List, 或者称为 Multi-level Linked List.

特点:

节点之间有多个连接
遍历节点的方式有多种

C语言中的结构体声明如下:

// Multiply Linked List
struct multi_list_s {
    int value;
    int len;
    struct multi_list_s* right;
    struct multi_list_s* bottom;

该类链表可以表示基于不同方式排序节点, 比如用于记录个人信息:

struct person {
  char* name;
  int age;
};

记录个人信息的列表, 可以基于人的姓名排序, 也可以基于年龄排序, 其结构图如下所示:

person linked list

或者展示稀疏矩阵:

-	0	1	2
0	0	5	0
1	0	0	0
2	20	0	10
3	6	0	0

使用以下数据结构:

struct coordinate_s {
  int row;
  int column;
};

struct sparse_matrix_s {
  struct coordinate_s coord;
  int value;
  struct sparse_matrix_s* next_row;
  struct sparse_matrix_s* next_column;
};

这样的稀疏矩阵可以同时基于行号和列号进行线性查找, 比较方便. 其结构图如下所示:

sparse matrix

或者表示多层链表 Multi-level linked list, 又称十字链表法 Orthogonal linked list.如下图所示:

multi-level linked list

还有一种简化了的, 称为 List of lists (LIL), 这种的, 索引方式要简单些. 如下图所示:

list of lists

Unrolled Linked List

上面的链表中, 每个节点都只存储一个元素值, 我们也可以在一个节点中存储多个元素值. 这种链表就是 Unrolled Linked List.

特点:

CPU 缓存更友好, 提高缓存命中率
访问相邻的元素的性能更好

其结构图如下所示:

unrolled linked list

C语言中的结构体声明如下:


// Unrolled Linked List
struct unrolled_list_s {
  struct unrolled_list_s* next;
  int len;
  int elements[0];

链表的基本操作

常用的链表操作比较多.

构造函数:

new(), 创建一个新的链表, 不包含任何节点

元素访问:

front(), 返回第一个元素的引用
front_mut(), 返回第一个元素的可变更引用
back(), 返回最后一个元素的引用
back_mut(), 返回最后一个元素的可变更引用
contains(value), 检查链表中是否包含给定的元素

链表容量:

len(), 返回节点个数
is_empty(), 链表是否为空

修改链表:

clear(), 移除链表中的所有节点, 移除之后, len() 函数返回 0
insert_at(pos, value), 在给定的特定位置插入新的节点
insert_iter(pos, iter), 在给定的特定位置插入一系列的节点
pop(), 从链表中移除特定值相等的第一个节点
pop_at(pos), 在给定的特定位置移除节点, 并返回该节点的值
pop_if(), 从链表中移除满足特定条件的所有节点
push_back(), 在链表尾部追加新的节点
pop_back(), 移除链表尾部的节点
push_front(), 在链表头部加入新的节点
pop_front(), 移除链表头部的节点
resize(new_size), 调整链表中节点的个数, 如果需要追加新的节点, 就使用默认值
resize_with(new_size, new_value), 调整链表中节点的个数, 如果需要追加新的节点, 就使用 new_value
append(list), 在链表尾部追加一系列的节点
prepend(list), 在链表头部加入一系列的节点

链表操作:

merge(), 合并两个链表
splice(), 将节点从一个链表转移到另一个链表
reverse(), 将链表中的节点反转
unique(), 从链表中移除有相同值的相邻的节点
sort(), 对链表中的节点进行排序, 排序相关的函数放在了后面排序算法章节
sort_by(), 依照相应的条件函数对链表中的节点进行排序
sort_by_key(), 依照相应的条件对链表中的节点进行排序

实现的 traits:

Debug
Clone
PartialEq
Eq
Hash
Drop
FromIterator
Extend

迭代器:

iter(), 返回一个迭代器
iter_mut(), 返回一个迭代器, 可以通过它修改链表中节点的值
into_iter()
DoubleEndedIterator, 对于双链表, 返回的迭代器需要实现双向迭代

插入 Insertion

在链表中插入一个新的节点, 分好几种情况:

在链表的头部插入节点
在链表的尾部插入节点
在给定的索引位置插入节点
在给定的节点后面插入节点

单链表 Singly Linked List

双链表 Doubly Linked List

相对于前文提到的单链表, 双链表 doubly linked list (DLL) 中每个节点包含两个指针, 分别指向左右相邻的节点.

其结构如下图所示:

doubly linked list

双链表的优点:

反转双向链表非常容易
它可以在执行过程中轻松分配或重新分配内存
与单链表一样, 它是最容易实现的数据结构
此双向链表的遍历是双向的, 这在单链表中是不可能的
与单链表相比, 删除节点很容易. 单链表删除需要指向要删除的节点和前一个节点的指针, 但在双向链表中, 它只需要要删除的指针. 与其他数据结构 (如数组) 相比, 双向链表的开销较低
可用于实现图算法 graph algorithms

双链表的不足:

与数组和单链表相比, 它使用额外的内存来存储左侧相邻接点
由于内存中的元素是随机存储的, 因此元素是按顺序访问的, 不允许随机访问
遍历双向链表可能比遍历单链表慢
实现和维护双向链表可能比单链表更复杂

双链表的应用场景:

它用于需要前后双向访问的系统
浏览器使用它来实现访问过的网页的前后导航, 即后退和前进按钮
它也用于表示经典的纸牌游戏
各种应用程序也使用它来实现撤消和重做功能
双向链表也用于构建 MRU/LRU (最近使用/最近最少使用) 缓存系统
其他数据结构, 如堆栈, 哈希表, 二叉树也可以使用双向链表构建或编程
在许多操作系统中, 线程调度程序 scheduler (选择哪个进程需要在什么时候运行的东西) 维护当时运行的所有进程的双向链表
实现图算法

链表的节点信息

我们使用单独的链表表头来记录链表的头尾节点信息, 同时还单独记录链表中节点的个数 len.

每个节点包含两个指针分别指向左右相邻节点, 同时在节点上存储元数的值.

其结构大致如下:

#![allow(unused)]

fn main() {
pub struct DoublyLinkedList<T> {
    head: NodePtr<T>,
    tail: NodePtr<T>,
    len: usize,
    _marker: PhantomData<Box<Node<T>>>,
}

type NodePtr<T> = Option<NonNull<Node<T>>>;

struct Node<T> {
    prev: NodePtr<T>,
    next: NodePtr<T>,
    value: T,
}
}

访问节点

只有头部节点和尾部节点可以直接访问, 其它节点需要遍历之后才能访问.

#![allow(unused)]
fn main() {
    /// Access the first node.
    #[must_use]
    #[inline]
    pub fn front(&self) -> Option<&T> {
        unsafe { self.head.as_ref().map(|node| &node.as_ref().value) }
    }

    /// Access the first node exclusively.
    #[must_use]
    #[inline]
    pub fn front_mut(&mut self) -> Option<&mut T> {
        unsafe { self.head.as_mut().map(|node| &mut node.as_mut().value) }
    }

    /// Access the last node.
    #[must_use]
    #[inline]
    pub fn back(&self) -> Option<&T> {
        unsafe { self.tail.as_ref().map(|node| &node.as_ref().value) }
    }

    /// Access the last node exclusively.
    #[must_use]
    #[inline]
    pub fn back_mut(&mut self) -> Option<&mut T> {
        unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().value) }
    }
}

算法实现

#![allow(unused)]
fn main() {
use std::cmp::Ordering;
use std::fmt::Formatter;
use std::hash::{Hash, Hasher};
use std::marker::PhantomData;
use std::ptr::NonNull;
use std::{fmt, mem};

pub struct DoublyLinkedList<T> {
    head: NodePtr<T>,
    tail: NodePtr<T>,
    len: usize,
    _marker: PhantomData<Box<Node<T>>>,
}

type NodePtr<T> = Option<NonNull<Node<T>>>;

struct Node<T> {
    prev: NodePtr<T>,
    next: NodePtr<T>,
    value: T,
}

pub struct IntoIter<T>(DoublyLinkedList<T>);

pub struct Iter<'a, T: 'a> {
    head: NodePtr<T>,
    tail: NodePtr<T>,
    len: usize,
    _marker: PhantomData<&'a Node<T>>,
}

pub struct IterMut<'a, T: 'a> {
    head: NodePtr<T>,
    tail: NodePtr<T>,
    len: usize,
    _marker: PhantomData<&'a mut Node<T>>,
}

// Public functions for list.
impl<T> DoublyLinkedList<T> {
    /// Create an empty list.
    #[must_use]
    #[inline]
    pub const fn new() -> Self {
        Self {
            len: 0,
            head: None,
            tail: None,
            _marker: PhantomData,
        }
    }

    // Element access

    /// Access the first node.
    #[must_use]
    #[inline]
    pub fn front(&self) -> Option<&T> {
        unsafe { self.head.as_ref().map(|node| &node.as_ref().value) }
    }

    /// Access the first node exclusively.
    #[must_use]
    #[inline]
    pub fn front_mut(&mut self) -> Option<&mut T> {
        unsafe { self.head.as_mut().map(|node| &mut node.as_mut().value) }
    }

    /// Access the last node.
    #[must_use]
    #[inline]
    pub fn back(&self) -> Option<&T> {
        unsafe { self.tail.as_ref().map(|node| &node.as_ref().value) }
    }

    /// Access the last node exclusively.
    #[must_use]
    #[inline]
    pub fn back_mut(&mut self) -> Option<&mut T> {
        unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().value) }
    }

    pub fn contains(&self, value: &T) -> bool
    where
        T: PartialEq<T>,
    {
        self.iter().any(|item| item == value)
    }

    // Capacity operations

    /// Returns the number of elements in list.
    #[must_use]
    #[inline]
    pub const fn len(&self) -> usize {
        self.len
    }

    /// Check whether the list is empty.
    #[must_use]
    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    // Iterators
    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            head: self.head,
            tail: self.tail,
            len: self.len,
            _marker: Default::default(),
        }
    }

    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut {
            head: self.head,
            tail: self.tail,
            len: self.len,
            _marker: Default::default(),
        }
    }

    // Modifiers

    /// Clear the contents.
    ///
    /// Erases all elements from the list.
    /// After calling this function, size of list is zero.
    pub fn clear(&mut self) {
        let mut other = Self::new();
        mem::swap(self, &mut other);
        drop(other);
    }

    /// Insert element at `pos`.
    ///
    /// # Panics
    ///
    /// Panic if `index > len`.
    pub fn insert_at(&mut self, mut pos: usize, value: T) {
        assert!(pos <= self.len);
        if pos == 0 {
            self.push_front(value);
            return;
        }
        if pos == self.len {
            self.push_back(value);
            return;
        }

        let new_node_ptr = Node::new_ptr(value);
        if let Some(mut node) = self.head {
            while let Some(next_node) = unsafe { node.as_mut().next } {
                if pos == 1 {
                    break;
                }
                pos -= 1;
                node = next_node;
            }

            unsafe {
                Self::insert_after(node, new_node_ptr);
            }
            self.len += 1;
        }
    }

    pub fn insert_iter<I: IntoIterator<Item = T>>(&mut self, mut pos: usize, iter: I) {
        assert!(pos <= self.len);
        let mut new_list = DoublyLinkedList::from_iter(iter);

        if pos == 0 {
            self.prepend(&mut new_list);
            return;
        }
        if pos == self.len {
            self.append(&mut new_list);
            return;
        }

        if let Some(mut node) = self.head {
            while let Some(next_node) = unsafe { node.as_mut().next } {
                if pos == 1 {
                    break;
                }
                pos -= 1;
                node = next_node;
            }

            self.len += new_list.len();
            unsafe {
                Self::append_nodes(node, &mut new_list);
            }
        }
    }

    /// Removes the first element equals specific `value`.
    pub fn pop(&mut self, value: &T) -> Option<T>
    where
        T: PartialEq<T>,
    {
        for (index, item) in self.iter().enumerate() {
            if item == value {
                return self.pop_at(index);
            }
        }
        None
    }

    /// Removes the first element satisfying specific condition and returns that element.
    pub fn pop_if<F>(&mut self, f: F) -> Option<T>
    where
        F: Fn(&T) -> bool,
    {
        let mut index: usize = 0;
        for item in self.iter() {
            if f(item) {
                break;
            }
            index += 1;
        }
        self.pop_at(index)
    }

    /// Remove element at `pos` and returns that element.
    ///
    /// # Panics
    ///
    /// Raise panic if `pos >= len`
    pub fn pop_at(&mut self, mut pos: usize) -> Option<T> {
        assert!(pos < self.len);
        if pos == 0 {
            return self.pop_front();
        }
        if pos == self.len - 1 {
            return self.pop_back();
        }
        if let Some(mut node) = self.head {
            while let Some(next_node) = unsafe { node.as_mut().next } {
                if pos == 1 {
                    break;
                }
                pos -= 1;
                node = next_node;
            }

            self.len -= 1;
            unsafe { Self::remove_after(node).map(Node::into_inner) }
        } else {
            None
        }
    }

    /// Add an element to the beginning of list.
    pub fn push_front(&mut self, value: T) {
        let node_ptr = Node::new_ptr(value);
        self.push_front_node(node_ptr);
    }

    /// Remove the first node in the list.
    pub fn pop_front(&mut self) -> Option<T> {
        self.pop_front_node().map(Node::into_inner)
    }

    /// Add an element to the end of list.
    pub fn push_back(&mut self, value: T) {
        let node_ptr = Node::new_ptr(value);
        self.push_back_node(node_ptr);
    }

    /// Remove the last node in the list.
    pub fn pop_back(&mut self) -> Option<T> {
        self.pop_back_node().map(Node::into_inner)
    }

    /// Append all elements in another list to self.
    pub fn append(&mut self, other: &mut Self) {
        match self.tail {
            Some(mut tail) => {
                // connect tail of self to head of other.
                if let Some(mut other_head) = other.head.take() {
                    unsafe {
                        tail.as_mut().next = Some(other_head);
                        other_head.as_mut().prev = Some(tail);
                    }

                    self.tail = other.tail.take();
                    self.len += other.len();
                    other.len = 0;
                }
            }
            None => {
                // self is empty.
                mem::swap(self, other);
            }
        }
    }

    /// Prepend all elements in another list to self.
    #[inline]
    pub fn prepend(&mut self, other: &mut Self) {
        other.append(self);
        self.swap(other);
    }

    /// Change number of elements stored.
    ///
    /// If the current size is greater than `new_size`, extra elements will
    /// be removed.
    /// If current size is less than `new_size`, more elements with default
    /// value are appended.
    pub fn resize(&mut self, new_size: usize)
    where
        T: Default,
    {
        match self.len.cmp(&new_size) {
            Ordering::Equal => (),
            Ordering::Less => {
                for _ in 0..(new_size - self.len) {
                    self.push_back(T::default());
                }
            }
            Ordering::Greater => {
                for _ in 0..(self.len - new_size) {
                    let _node = self.pop_back_node();
                }
            }
        }
    }

    /// Change number of elements stored.
    pub fn resize_with(&mut self, new_size: usize, value: T)
    where
        T: Clone,
    {
        match self.len.cmp(&new_size) {
            Ordering::Equal => (),
            Ordering::Less => {
                for _ in 0..(new_size - self.len) {
                    self.push_back(value.clone());
                }
            }
            Ordering::Greater => {
                for _ in 0..(self.len - new_size) {
                    let _node = self.pop_back_node();
                }
            }
        }
    }

    /// Swap the contents.
    #[inline]
    pub fn swap(&mut self, other: &mut Self) {
        mem::swap(self, other);
    }

    // Operations

    /// Merges two sorted lists.
    pub fn merge(&mut self, _other: &mut Self)
    where
        T: PartialOrd<T>,
    {
        todo!()
    }

    // pub fn merge_by(&mut self, other: &mut Self, predict: P)
    // where
    //     P: PartialOrd<T>,
    // {
    //     todo!()
    // }

    /// Move elements from another list.
    pub fn splice(&mut self, _other: &mut Self) {
        todo!()
    }

    /// Reverses the order of the elements.
    pub fn reverse(&mut self) {
        unsafe { Self::base_reverse(self.head) };
        mem::swap(&mut self.head, &mut self.tail);
    }

    /// Removes consecutive duplicate elements.
    ///
    /// Returns number of elements removed.
    pub fn unique(&mut self) -> usize
    where
        T: PartialEq<T>,
    {
        let mut count = 0;
        if let Some(mut node) = self.head {
            while let Some(next_node) = unsafe { node.as_mut().next } {
                unsafe {
                    if node.as_ref().value == next_node.as_ref().value {
                        Self::remove_after(node);
                        count += 1;
                    } else {
                        node = next_node;
                    }
                }
            }
        }

        count
    }

    pub fn sort(&mut self) {
        todo!()
    }

    //pub fn sort_by(&mut self) { }
    //pub fn sort_by_key(&mut self) { }
}

// Private or unsafe functions for list.
impl<T> DoublyLinkedList<T> {
    fn push_front_node(&mut self, node_ptr: NonNull<Node<T>>) {
        unsafe {
            (*node_ptr.as_ptr()).next = self.head;
            (*node_ptr.as_ptr()).prev = None;
        }
        let node = Some(node_ptr);

        match self.head {
            Some(head) => unsafe { (*head.as_ptr()).prev = node },
            None => self.tail = node,
        }

        self.head = node;
        self.len += 1;
    }

    fn push_back_node(&mut self, node_ptr: NonNull<Node<T>>) {
        unsafe {
            (*node_ptr.as_ptr()).next = None;
            (*node_ptr.as_ptr()).prev = self.tail;
        }
        let node = Some(node_ptr);

        match self.tail {
            Some(tail) => unsafe { (*tail.as_ptr()).next = node },
            None => self.head = node,
        }

        self.tail = node;
        self.len += 1;
    }

    fn pop_front_node(&mut self) -> Option<Box<Node<T>>> {
        self.head.map(|old_head| {
            let old_head = unsafe { Node::from_ptr(old_head) };
            self.head = old_head.next;

            match self.head {
                Some(head) => unsafe { (*head.as_ptr()).prev = None },
                None => self.tail = None,
            }

            self.len -= 1;
            old_head
        })
    }

    fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
        self.tail.map(|old_tail| {
            let old_tail = unsafe { Node::from_ptr(old_tail) };
            self.tail = old_tail.prev;

            match self.tail {
                Some(tail) => unsafe { (*tail.as_ptr()).next = None },
                None => self.head = None,
            }

            self.len -= 1;
            old_tail
        })
    }

    unsafe fn insert_after(mut prev_node: NonNull<Node<T>>, mut new_node_ptr: NonNull<Node<T>>) {
        if let Some(mut next_node) = prev_node.as_mut().next {
            new_node_ptr.as_mut().next = Some(next_node);
            next_node.as_mut().prev = Some(new_node_ptr);
        }
        new_node_ptr.as_mut().prev = Some(prev_node);
        prev_node.as_mut().next = Some(new_node_ptr);
    }

    unsafe fn append_nodes(mut prev_node: NonNull<Node<T>>, other: &mut Self) {
        if other.is_empty() {
            return;
        }

        if let Some(mut next_node) = prev_node.as_mut().next {
            if let Some(mut other_tail) = other.tail.take() {
                other_tail.as_mut().next = Some(next_node);
                next_node.as_mut().prev = Some(other_tail);
            }
        }
        if let Some(mut other_head) = other.head.take() {
            prev_node.as_mut().next = Some(other_head);
            other_head.as_mut().prev = Some(prev_node);
        }

        other.len = 0;
    }

    unsafe fn remove_after(mut node: NonNull<Node<T>>) -> Option<Box<Node<T>>> {
        if let Some(mut next_node) = node.as_mut().next {
            let mut next_next_node = next_node.as_mut().next.take();
            if let Some(next_next_node) = next_next_node.as_mut() {
                next_next_node.as_mut().prev = Some(node);
            }
            node.as_mut().next = next_next_node;

            Some(Node::from_ptr(next_node))
        } else {
            None
        }
    }

    unsafe fn base_reverse(node: NodePtr<T>) {
        let mut temp = node;
        while let Some(mut temp_node) = temp {
            mem::swap(&mut temp_node.as_mut().prev, &mut temp_node.as_mut().next);
            // Old next node is now prev.
            temp = temp_node.as_mut().prev;
        }
    }
}

impl<T> Drop for DoublyLinkedList<T> {
    fn drop(&mut self) {
        while self.pop_front_node().is_some() {
            // dropped
        }
    }
}

impl<T> Default for DoublyLinkedList<T> {
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}

impl<T: fmt::Debug> fmt::Debug for DoublyLinkedList<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self).finish()
    }
}

impl<T: Clone> Clone for DoublyLinkedList<T> {
    fn clone(&self) -> Self {
        let mut list = Self::new();
        list.extend(self.iter().cloned());
        list
    }
}

impl<T: PartialEq> PartialEq for DoublyLinkedList<T> {
    fn eq(&self, other: &Self) -> bool {
        self.len == other.len && self.iter().eq(other.iter())
    }
}

impl<T: Eq> Eq for DoublyLinkedList<T> {}

impl<T: Hash> Hash for DoublyLinkedList<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // state.write_length_prefix(self.len);
        state.write_usize(self.len);
        for element in self {
            element.hash(state);
        }
    }
}

impl<T> Extend<T> for DoublyLinkedList<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        iter.into_iter().for_each(|value| self.push_back(value));
    }
}

impl<T> FromIterator<T> for DoublyLinkedList<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut list = Self::new();
        list.extend(iter);
        list
    }
}

impl<T> IntoIterator for DoublyLinkedList<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter(self)
    }
}

impl<'a, T> IntoIterator for &'a DoublyLinkedList<T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, T> IntoIterator for &'a mut DoublyLinkedList<T> {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        self.0.pop_front()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.0.len, Some(self.0.len))
    }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0.pop_back()
    }
}

impl<T> ExactSizeIterator for IntoIter<T> {}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.len == 0 {
            None
        } else {
            self.head.map(|node| unsafe {
                let node: &Node<T> = node.as_ref();
                self.len -= 1;
                self.head = node.next;
                &node.value
            })
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }

    #[inline]
    fn last(mut self) -> Option<Self::Item>
    where
        Self: Sized,
    {
        self.next_back()
    }
}

impl<T> DoubleEndedIterator for Iter<'_, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.len == 0 {
            None
        } else {
            self.tail.map(|node| unsafe {
                let node: &Node<T> = node.as_ref();
                self.tail = node.prev;
                self.len -= 1;
                &node.value
            })
        }
    }
}

impl<T> ExactSizeIterator for Iter<'_, T> {}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.len == 0 {
            None
        } else {
            self.head.map(|mut node| unsafe {
                let node: &mut Node<T> = node.as_mut();
                self.len -= 1;
                self.head = node.next;
                &mut node.value
            })
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }

    #[inline]
    fn last(mut self) -> Option<Self::Item>
    where
        Self: Sized,
    {
        self.next_back()
    }
}

impl<T> DoubleEndedIterator for IterMut<'_, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.len == 0 {
            None
        } else {
            self.tail.map(|mut node| unsafe {
                let node: &mut Node<T> = node.as_mut();
                self.tail = node.prev;
                self.len -= 1;
                &mut node.value
            })
        }
    }
}

impl<T> ExactSizeIterator for IterMut<'_, T> {}

impl<T> Node<T> {
    #[must_use]
    #[inline]
    const fn new(value: T) -> Self {
        Self {
            prev: None,
            next: None,
            value,
        }
    }

    #[must_use]
    #[inline]
    fn new_ptr(value: T) -> NonNull<Self> {
        let node = Box::new(Self::new(value));
        NonNull::from(Box::leak(node))
    }

    #[must_use]
    #[inline]
    unsafe fn from_ptr(ptr: NonNull<Self>) -> Box<Self> {
        Box::from_raw(ptr.as_ptr())
    }

    #[must_use]
    #[inline]
    #[allow(clippy::boxed_local)]
    fn into_inner(self: Box<Self>) -> T {
        self.value
    }
}

#[cfg(test)]
mod tests {
    use super::DoublyLinkedList;

    #[test]
    fn test_is_empty() {
        let list = DoublyLinkedList::<i32>::new();
        assert!(list.is_empty());
    }

    #[test]
    fn test_push() {
        let mut list = DoublyLinkedList::new();
        list.push_front(2);
        list.push_front(3);
        list.push_front(5);
        list.push_front(7);
        list.push_front(11);
        assert_eq!(list.len(), 5);
    }

    #[test]
    fn test_pop_front() {
        let mut list = DoublyLinkedList::new();
        list.push_front(3);
        list.push_front(5);
        list.push_front(7);
        assert_eq!(list.pop_front(), Some(7));
        assert_eq!(list.len(), 2);
        assert_eq!(list.pop_front(), Some(5));
        assert_eq!(list.pop_front(), Some(3));
        assert!(list.is_empty());
    }

    #[test]
    fn test_pop_back() {
        let mut list = DoublyLinkedList::new();
        list.push_back(3);
        list.push_back(5);
        list.push_back(7);
        assert_eq!(list.pop_back(), Some(7));
        assert_eq!(list.len(), 2);
        assert_eq!(list.pop_back(), Some(5));
        assert_eq!(list.pop_back(), Some(3));
        assert!(list.is_empty());
    }

    #[test]
    fn test_back() {
        let mut list = DoublyLinkedList::new();
        list.push_back(5);
        list.push_back(7);
        assert_eq!(list.back(), Some(&7));
        assert_eq!(list.front(), Some(&5));
    }

    #[test]
    fn test_back_mut() {
        let mut list = DoublyLinkedList::new();
        list.push_back(5);
        list.push_back(7);
        if let Some(value) = list.back_mut() {
            *value = 11;
        }
        assert_eq!(list.back(), Some(&11));
    }

    #[test]
    fn test_drop() {
        let mut list = DoublyLinkedList::new();
        for i in 0..(128 * 200) {
            list.push_front(i);
        }
        drop(list);
    }

    #[test]
    fn test_into_iter() {
        let mut list = DoublyLinkedList::new();
        list.push_front(2);
        list.push_front(3);
        list.push_front(5);
        list.push_front(7);
        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(7));
        assert_eq!(iter.next(), Some(5));
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_append() {
        let numbers = [1, 2, 3];
        let mut list1 = DoublyLinkedList::new();
        let mut list2 = DoublyLinkedList::from_iter(numbers);
        assert_eq!(list2.len(), numbers.len());
        list1.append(&mut list2);
        assert_eq!(list1.len(), numbers.len());
        assert!(list2.is_empty());
    }

    #[test]
    fn test_prepend() {
        let numbers = [1, 2, 3];
        let mut list1 = DoublyLinkedList::new();
        list1.push_back(4);
        let mut list2 = DoublyLinkedList::from_iter(numbers);
        assert_eq!(list2.len(), numbers.len());
        list1.prepend(&mut list2);
        assert!(list2.is_empty());
        assert_eq!(list1.len(), numbers.len() + 1);
        assert_eq!(list1, DoublyLinkedList::from_iter([1, 2, 3, 4]));
    }

    #[test]
    fn test_extend() {
        let mut list = DoublyLinkedList::new();
        let numbers = [1, 2, 3];
        list.extend(numbers);
        assert_eq!(list, DoublyLinkedList::from_iter(numbers));
    }

    #[test]
    fn test_insert() {
        let mut list = DoublyLinkedList::new();
        list.insert_at(0, 1);
        list.insert_at(0, 0);
        list.insert_at(2, 3);
        list.insert_at(2, 2);
        assert_eq!(list.into_iter().collect::<Vec<_>>(), [0, 1, 2, 3]);
    }

    #[test]
    fn test_insert_range() {
        let mut list = DoublyLinkedList::new();
        list.push_back(0);
        list.push_back(3);
        list.insert_iter(1, [1, 2]);
        assert_eq!(list, DoublyLinkedList::from_iter([0, 1, 2, 3]));
    }

    #[test]
    fn test_contains() {
        let list = DoublyLinkedList::from_iter([1, 2, 3, 4, 5]);
        assert!(list.contains(&3));
        assert!(list.contains(&4));
        assert!(!list.contains(&6));
        assert!(!list.contains(&0));
    }

    #[test]
    fn test_pop() {
        let mut list = DoublyLinkedList::from_iter([1, 2, 3, 4]);
        list.pop(&2);
        assert_eq!(list.len(), 3);
    }

    #[test]
    fn test_pop_at() {
        let mut list = DoublyLinkedList::from_iter([1, 2, 3, 4]);
        let ret = list.pop_at(1);
        assert_eq!(ret, Some(2));
        assert_eq!(list.len(), 3);
    }

    #[test]
    fn test_pop_if() {
        let mut list = DoublyLinkedList::from_iter([1, 2, 3, 4]);
        let ret = list.pop_if(|value| value % 2 == 0);
        assert_eq!(ret, Some(2));
        assert_eq!(list.len(), 3);
        let ret = list.pop_if(|value| value % 2 == 0);
        assert_eq!(ret, Some(4));
        assert_eq!(list.len(), 2);
    }

    #[test]
    fn test_unique() {
        let mut list = DoublyLinkedList::from_iter([1, 1, 2, 2, 3, 1, 1, 2]);
        let expected = [1, 2, 3, 1, 2];
        let ret = list.unique();
        assert_eq!(ret, 3);
        assert_eq!(list.into_iter().collect::<Vec<_>>(), expected);
    }

    #[test]
    fn test_reverse() {
        let mut list = DoublyLinkedList::from_iter([1, 2, 3, 4]);
        assert_eq!(list.iter().copied().collect::<Vec<_>>(), [1, 2, 3, 4]);
        list.reverse();
        assert_eq!(list.into_iter().collect::<Vec<_>>(), [4, 3, 2, 1]);
    }
}
}

环状双链表

与上文提到的双链表相比, 环状双向链表只是连接了链表的头部节点和尾部节点, 其它操作都差不多.

其结构如下图所示:

doubly circular linked list

Header Linked List

Unrolled Linked List

List of Lists

多层链表 Multi-level Linked List

多层链表 Multi-level linked list, 又称为十字链表 Orthogonal linked list.

可以使用它存储稀疏矩阵和图等数据结构.

链表中的每个节点包括两个指针, 分别指向左右水平的邻接节点和上下垂直邻结节点. 如果使用双链表风格的话, 每个节点会包含四个指针.

十字链表的应用: 十字链表最常见的应用是稀疏矩阵表示. 简而言之, 稀疏矩阵是其中大多数元素为零 (或任何已知常数) 的矩阵. 它们经常出现在科学应用中, 将稀疏矩阵表示为二维数组会浪费大量内存; 相反地, 稀疏矩阵表示为十字链表. 我们仅为矩阵中的非零元素创建一个节点, 并且在每个节点中存储值, 行索引和列索引以及指向其他节点的必要指针. 这节省了大量性能开销, 并且是实现稀疏矩阵最节省内存的方法.

单链表风格

每个节点只存储两个指针, 分别指向右侧和下层相邻的节点.

双链表风格

每个节点存储四个指针, 分别指向左右水平的邻接节点和上下垂直邻结节点.

跳跃表 Skip List

参考

Skip list

跳跃表的基本操作

跳跃表的实现

跳跃表的应用

栈 Stacks

栈 (stack) 是一个线性数据结构, 内部存放的元素依照先入后出 (last in first out, FILO) 的顺序进行操作. 即先放入栈的元素离栈底较近, 出栈顺序比较晚, 后放入栈的元素离栈顶较近, 出栈顺序较早.

栈的基本结构如下图所示:

stack

跟据栈的大小可以分类为:

固定大小的栈: 一旦初始化完成, 便不允许调整栈的大小. 如果当前栈已满, 再向栈顶加入新元素时就会触发栈已满的错误; 如果当前栈是空的, 调用pop() 进行出栈时, 就会触发栈已空的错误
可以动态调整大小的栈: 可以根据需要进行扩容或者缩容

栈的基本操作

栈的基本操作 ADT, 包括:

fn new(capacity) -> Stack: 初始化栈, 指定栈的大小
fn push(value: T) -> Result<(), T>: 将一个元素加入到栈顶
fn pop() -> Option<T>: 从栈顶移出一个元素
fn top() -> Option<&T>: 返回栈顶的元素, 但并不移除它
fn is_empty() -> bool: 检查栈是否为空
fn len() -> usize: 返回当前栈中包含的元素个数
fn capacity() -> usize: 对于静态栈, 返回栈的最大容量

要实现的 traits 有这些:

FromIterator<T>: 从迭代器构造栈, 如果是静态栈, 其容量大小就是迭代器中包含的元素个数
PartialEq<T>, Eq<T>, PartialOrd<T>, Ord<T>, 比较操作
Hash<T>: 支持哈稀函数

入栈 push()

将一个元素入栈:

如果栈已满, 就不能再插入新的元素了, 返回栈已满的错误
将栈顶的索引值 top 加上 1, 并将新元素加入到栈顶的位置

stack push

如果是动态栈, 不受容量限制, 那这个函数就没有返回值, 也不存在栈满的问题.

出栈 pop()

元素出栈顺序跟其入栈顺序是相反的.

从栈顶移出元素:

如果栈已空, 就直接返回 None
将栈顶的索引值 top 减去1, 并返回旧的栈顶元素

stack pop

返回栈顶的元素 top()

返回栈顶元素:

返回之前先检查栈是否为空, 如果为空, 就直接返回栈空的错误
返回当前的栈顶元素, 对栈不做任何改动

stack top

检查栈是否为空 is_empty()

检查栈里的 top 的值
如果 top == 0, 则说明栈为空, 返回 true
否则栈中存有元素, 不为空, 返回 false

stack is empty

检查栈中当前的元素个数 len()

直接返回 len 属性

检查栈的容量 capacity()

直接返回 capacity 属性

栈的实现

使用数组实现

使用数组实现的栈结构, 它能保存的元素个数是固定的, 需要在初始化栈时指定栈的容量.

这里, 我们使用 Box<[Option<T>]> 用于指示数组中是否存储了元素, 如果它为 None 则表示在位置没有元素.

另外一种实现方式是 Box<[T]>, 并且要求类型 T 实现 Clone trait.

array stack

#![allow(unused)]
fn main() {
use std::cmp::Ordering;
use std::fmt;
use std::fmt::Formatter;
use std::hash::{Hash, Hasher};

/// 使用数组实现静态栈结构
pub struct ArrayStack<T> {
    top: usize,
    buf: Box<[Option<T>]>,
}

impl<T> ArrayStack<T> {
    /// 初始化栈, 指定栈的容量
    #[must_use]
    pub fn new(capacity: usize) -> Self {
        debug_assert!(capacity > 0);
        
        let values: Vec<Option<T>> = (0..capacity).map(|_| None).collect();

        Self {
            top: 0,
            buf: values.into_boxed_slice(),
        }
    }

    /// 将元素入栈
    ///
    /// # Errors
    ///
    /// 当栈已满时再将元素入栈, 就会返回错误, 以及原有的元素 `value`.
    pub fn push(&mut self, value: T) -> Result<(), T> {
        if self.top >= self.buf.len() {
            return Err(value);
        }
        self.buf[self.top] = Some(value);
        self.top += 1;
        Ok(())
    }

    /// 将栈顶元素出栈
    ///
    /// 当栈已经空时, 返回 `None`
    pub fn pop(&mut self) -> Option<T> {
        if self.top > 0 {
            self.top -= 1;
            self.buf[self.top].take()
        } else {
            None
        }
    }

    /// 返回栈顶元素
    #[must_use]
    pub const fn top(&self) -> Option<&T> {
        if self.top > 0 {
            self.buf[self.top - 1].as_ref()
        } else {
            None
        }
    }

    /// 检查栈是否空
    #[must_use]
    pub const fn is_empty(&self) -> bool {
        self.top == 0
    }

    /// 返回当前栈中的元素个数
    #[must_use]
    pub const fn len(&self) -> usize {
        self.top
    }

    /// 返回栈的容量
    #[must_use]
    pub const fn capacity(&self) -> usize {
        self.buf.len()
    }
}

impl<T: PartialEq> PartialEq for ArrayStack<T> {
    fn eq(&self, other: &Self) -> bool {
        self.top == other.top && PartialEq::eq(&self.buf, &other.buf)
    }
}

impl<T: Eq> Eq for ArrayStack<T> {}

impl<T: PartialOrd> PartialOrd for ArrayStack<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        PartialOrd::partial_cmp(&self.buf, &other.buf)
    }
}

impl<T: Ord> Ord for ArrayStack<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        Ord::cmp(&self.buf, &other.buf)
    }
}

impl<T: Hash> Hash for ArrayStack<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.buf, state);
    }
}

impl<T> FromIterator<T> for ArrayStack<T> {
    fn from_iter<U: IntoIterator<Item=T>>(iter: U) -> Self {
        let vec: Vec<Option<T>> = iter.into_iter().map(|item| Some(item)).collect();
        Self {
            top: vec.len(),
            buf: vec.into_boxed_slice(),
        }
    }
}

impl<T: fmt::Debug> fmt::Debug for ArrayStack<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.buf, f)
    }
}
}

使用数组实现 - 消除 Option

上面的实现过程中, 使用了 Option<T> 来向数组中存储元素, 这会额外占用一些内存, 操作效率有影响. 我们可以手动操作内存, 来消除 Option<T>:

#![allow(unused)]
fn main() {
use std::{fmt, ptr};
use std::alloc::{alloc, Layout};
use std::cmp::Ordering;
use std::fmt::Formatter;
use std::hash::{Hash, Hasher};
use std::mem::ManuallyDrop;
use std::ptr::NonNull;

/// 使用数组实现静态栈结构
pub struct ArrayStack2<T> {
    top: usize,
    buf: Box<[T]>,
}

struct RawVec<T> {
    ptr: NonNull<T>,
    cap: usize,
}

#[derive(Debug, Clone, Copy, Eq, PartialEq)]
enum AllocError {
    CapacityOverflow,
    AllocateError,
}

impl<T> ArrayStack2<T> {
    /// # Panics
    ///
    /// Raise panic if failed to allocate memory.
    #[must_use]
    pub fn new(capacity: usize) -> Self {
        debug_assert!(capacity > 0);

        let raw_vec = RawVec::<T>::try_allocate(capacity).expect("Failed to allocate buffer");
        let buf: Box<[T]> = unsafe { raw_vec.into_box() };

        Self {
            top: 0,
            buf,
        }
    }

    /// # Errors
    ///
    /// 当栈已满时再将元素入栈, 就会返回错误, 以及原有的元素 `value`.
    pub fn push(&mut self, value: T) -> Result<(), T> {
        if self.top >= self.buf.len() {
            return Err(value);
        }
        self.buf[self.top] = value;
        self.top += 1;
        Ok(())
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.top > 0 {
            self.top -= 1;
            unsafe {
                Some(ptr::read(self.buf.as_ptr().wrapping_add(self.top)))
            }
        } else {
            None
        }
    }

    #[must_use]
    pub const fn top(&self) -> Option<&T> {
        if self.top > 0 {
            Some(&self.buf[self.top - 1])
        } else {
            None
        }
    }

    #[must_use]
    pub const fn is_empty(&self) -> bool {
        self.top == 0
    }

    #[must_use]
    pub const fn len(&self) -> usize {
        self.top
    }

    #[must_use]
    pub const fn capacity(&self) -> usize {
        self.buf.len()
    }
}

impl<T: PartialEq> PartialEq for ArrayStack2<T> {
    fn eq(&self, other: &Self) -> bool {
        self.top == other.top && PartialEq::eq(&self.buf, &other.buf)
    }
}

impl<T: Eq> Eq for ArrayStack2<T> {}

impl<T: PartialOrd> PartialOrd for ArrayStack2<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        PartialOrd::partial_cmp(&self.buf, &other.buf)
    }
}

impl<T: Ord> Ord for ArrayStack2<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        Ord::cmp(&self.buf, &other.buf)
    }
}

impl<T: Hash> Hash for ArrayStack2<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.buf, state);
    }
}

impl<T> FromIterator<T> for ArrayStack2<T> {
    fn from_iter<U: IntoIterator<Item=T>>(iter: U) -> Self {
        let vec: Vec<T> = iter.into_iter().collect();
        Self {
            top: vec.len(),
            buf: vec.into_boxed_slice(),
        }
    }
}

impl<T: fmt::Debug> fmt::Debug for ArrayStack2<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.buf, f)
    }
}


impl<T> RawVec<T> {
    fn try_allocate(
        capacity: usize,
    ) -> Result<Self, AllocError> {
        debug_assert!(capacity > 0);
        let Ok(layout) = Layout::array::<T>(capacity) else {
            return Err(AllocError::CapacityOverflow);
        };

        let ptr = unsafe { alloc(layout) };
        if ptr.is_null() {
            return Err(AllocError::AllocateError);
        }
        let ptr = unsafe {
            NonNull::new_unchecked(ptr.cast::<T>())
        };

        Ok(Self { ptr, cap: capacity })
    }

    unsafe fn into_box(self) -> Box<[T]> {
        let me = ManuallyDrop::new(self);
        unsafe {
            let slice = ptr::slice_from_raw_parts_mut(me.ptr.as_ptr(), me.cap);
            Box::from_raw(slice)
        }
    }
}
}

使用动态数组 Vec 实现动态栈

使用 Vec<T> 实现的栈可以进行动态扩容, 但每次扩容时可能要进行内存的批量拷贝.

这个比较简单, 因为 Vec<T> 本身就实现了基本的栈操作接口, 我们只需要再包装一下就行:

#![allow(unused)]
fn main() {
use std::cmp::Ordering;
use std::fmt;
use std::fmt::Formatter;
use std::hash::{Hash, Hasher};

pub struct VecStack<T: Sized>(Vec<T>);

impl<T> Default for VecStack<T> {
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}

impl<T> VecStack<T> {
    /// 初始化栈, 默认的容量为 0
    #[must_use]
    #[inline]
    pub const fn new() -> Self {
        Self(Vec::new())
    }

    /// 初始化栈, 指定栈的容量, 但可以自动扩容.
    #[must_use]
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        Self(Vec::with_capacity(capacity))
    }

    /// 将元素入栈
    #[inline]
    pub fn push(&mut self, value: T) {
        self.0.push(value);
    }

    /// 将栈顶元素出栈
    ///
    /// 当栈已经空时, 返回 `None`
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        self.0.pop()
    }

    /// 返回栈顶元素
    #[must_use]
    #[inline]
    pub fn top(&self) -> Option<&T> {
        self.0.last()
    }

    /// 检查栈是否空
    #[must_use]
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }

    /// 返回当前栈中的元素个数
    #[must_use]
    #[inline]
    pub fn len(&self) -> usize {
        self.0.len()
    }

    /// 返回栈的容量
    #[must_use]
    #[inline]
    pub fn capacity(&self) -> usize {
        self.0.capacity()
    }
}


impl<T: PartialEq> PartialEq for VecStack<T> {
    fn eq(&self, other: &Self) -> bool {
        PartialEq::eq(&self.0, &other.0)
    }
}

impl<T: Eq> Eq for VecStack<T> {}

impl<T: PartialOrd> PartialOrd for VecStack<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        PartialOrd::partial_cmp(&self.0, &other.0)
    }
}

impl<T: Ord> Ord for VecStack<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        Ord::cmp(&self.0, &other.0)
    }
}

impl<T: Hash> Hash for VecStack<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.0, state);
    }
}

impl<T> FromIterator<T> for VecStack<T> {
    fn from_iter<U: IntoIterator<Item=T>>(iter: U) -> Self {
        let vec: Vec<T> = iter.into_iter().collect();
        Self(vec)
    }
}

impl<T: fmt::Debug> fmt::Debug for VecStack<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.0, f)
    }
}
}

使用链表实现动态栈

使用链表实现动态栈, 也是一个可行的方式, 为了简化代码, 我们使用了标准库中的双链表. 但是在这里使用单链表就足够了.

#![allow(unused)]
fn main() {
use std::cmp::Ordering;
use std::collections::LinkedList;
use std::fmt;
use std::fmt::Formatter;
use std::hash::{Hash, Hasher};

#[allow(clippy::linkedlist)]
pub struct ListStack<T> (LinkedList<T>);

impl<T> ListStack<T> {
    #[must_use]
    #[inline]
    pub const fn new() -> Self {
        Self(LinkedList::new())
    }


    /// 将元素入栈
    #[inline]
    pub fn push(&mut self, value: T) {
        self.0.push_back(value);
    }

    /// 将栈顶元素出栈
    ///
    /// 当栈已经空时, 返回 `None`
    #[must_use]
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        self.0.pop_back()
    }

    /// 返回栈顶元素
    #[must_use]
    #[inline]
    pub fn top(&self) -> Option<&T> {
        self.0.back()
    }

    #[must_use]
    #[inline]
    pub fn len(&self) -> usize {
        self.0.len()
    }

    #[must_use]
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }
}

impl<T> Default for ListStack<T> {
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}

impl<T: PartialEq> PartialEq for ListStack<T> {
    fn eq(&self, other: &Self) -> bool {
        PartialEq::eq(&self.0, &other.0)
    }
}

impl<T: Eq> Eq for ListStack<T> {}

impl<T: PartialOrd> PartialOrd for ListStack<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        PartialOrd::partial_cmp(&self.0, &other.0)
    }
}

impl<T: Ord> Ord for ListStack<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        Ord::cmp(&self.0, &other.0)
    }
}

impl<T: Hash> Hash for ListStack<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.0, state);
    }
}

impl<T> FromIterator<T> for ListStack<T> {
    fn from_iter<U: IntoIterator<Item=T>>(iter: U) -> Self {
        let list: LinkedList<T> = iter.into_iter().collect();
        Self(list)
    }
}

impl<T: fmt::Debug> fmt::Debug for ListStack<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.0, f)
    }
}
}

栈的应用

栈是一个线性的数据结构. 它在编程领域有广泛的使用. 比如操作系统会为每个线程分配一个函数调用栈, 用于保存函数内的局部变量.

stack

常见的栈的应用有:

函数调用: 用于记录函数返回地址, 当被调用函数执行完后可以将返回值正确还回给函数调用处
递归: 递归函数的调用, 通常可以将它们转换成迭代的形式, 这时可以利用栈来存放每次递归调用时的值
语法解析: 可以利用栈来检验编程语言中表达式的语法
表达式求值: 可以用栈来实现对后缀表达式的求值

单调栈 Monotonic Stack

队列 Queues

队列是计算机科学里的基础的概念, 它用于以一定顺序存储和管理数据.

它遵循"先进先出" (First In First Out, FIFO) 的原则, 即先进入到队列里的元素会先出队列. 它是两端开口的线性数据结构 (linear data structure),

基本的操作如下图所示:

queue data flow

队列的分类

根据队列可以容纳的元素个数不同, 可以被分为:

静态队列, 或者固定队列: 即队列在初始化时就指定它的容量, 队列中的元素个数不同超过该容量, 否则就出队 (enqueue) 失败
动态队列: 即队列中的元素个数不受限制

根据其结构不同, 队列可以分成几种类型:

简单队列 simple queue: 从一端入队 (enqueue), 而从另一端出队 (dequeue)
双端队列 double-ended queue(deque): 左右两端都可以入队出队
- 限制入队队列 input-restricted queue: 元素可以从两端出队, 但只能从一端入队
- 限制出队队列 output-restricted queue: 元素可以从两端入队, 但只能从一端出队
环形队列 circular queue: 又称为环状缓冲区, 整个队列的队首与队尾相连, 元素只从队列的头部出队, 从队列的尾部入队
优先级队列 priority queue: 队列中的元素按照某个规则升序或者降序依次排列

因为双端队列和优先级队列比较复杂, 在后面有单独的章节介绍它们, 本章内容不再提及.

队列的基本操作

队列的基本接口包括:

fn new() -> Self, 创建一个动态队列, 其容量不受限制
fn new(capacity) -> Self, 创建一个静态队列, 初始化时就指定队列的容量
fn len() -> usize, 返回当前队列中的元素个数
fn capacity() -> usize, 对于静态队列, 返回队列中的容量
fn is_empty() -> bool, 对于静态队列, 查看队列是否已满
fn front() -> Option<&T>, 返回队列头部元素的共享引用, 如果有的话
fn front_mut() -> Option<&mut T>, 返回队列头部元素的可变引用, 如果有的话
fn back() -> Option<&T>, 返回队列尾部元素的共享引用, 如果有的话
fn back_mut() -> Option<&mut T>, 返回队列尾部元素的可变引用, 如果有的话
fn push(value: T) -> Result<(), T>, 简单队列需要实现的接口, 从队列的一端插入元素
fn pop() -> Option<T>, 简单队列需要实现的接口, 从队列的另一端弹出元素

要实现的 traits 有这些:

FromIterator<T>: 从迭代器构造隐列, 如果是静态队列, 其容量大小就是迭代器中包含的元素个数
PartialEq<T>, Eq<T>, PartialOrd<T>, Ord<T>, 比较操作
Hash<T>: 支持哈稀函数

实现简单队列

使用数组实现

对于有静态队列, 使用数组来实现比较符合直觉.

#![allow(unused)]
fn main() {
use std::cmp::Ordering;
use std::fmt;
use std::hash::{Hash, Hasher};

pub struct ArrayQueue<T> {
    len: usize,
    buf: Box<[Option<T>]>,
}

impl<T> ArrayQueue<T> {
    #[must_use]
    pub fn new(capacity: usize) -> Self {
        let values: Vec<Option<T>> = (0..capacity).map(|_| None).collect();

        Self {
            len: 0,
            buf: values.into_boxed_slice(),
        }
    }

    /// # Errors
    ///
    /// 当栈已满时再将元素入队, 就会返回错误, 以及原有的元素 `value`.
    pub fn push(&mut self, value: T) -> Result<(), T> {
        if self.len == self.buf.len() {
            return Err(value);
        }

        self.buf[self.len] = Some(value);
        self.len += 1;

        Ok(())
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len > 0 {
            let front = self.buf[0].take();
            for i in 1..self.len {
                self.buf.swap(i - 1, i);
            }
            self.len -= 1;
            front
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub const fn len(&self) -> usize {
        self.len
    }

    #[must_use]
    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    #[must_use]
    #[inline]
    pub const fn capacity(&self) -> usize {
        self.buf.len()
    }

    #[must_use]
    #[inline]
    pub const fn front(&self) -> Option<&T> {
        if self.len > 0 {
            self.buf[0].as_ref()
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub fn front_mut(&mut self) -> Option<&mut T> {
        if self.len > 0 {
            self.buf[0].as_mut()
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub const fn back(&self) -> Option<&T> {
        if self.len > 0 {
            self.buf[self.len - 1].as_ref()
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub fn back_mut(&mut self) -> Option<&mut T> {
        if self.len > 0 {
            self.buf[self.len - 1].as_mut()
        } else {
            None
        }
    }
}

impl<T: PartialEq> PartialEq for ArrayQueue<T> {
    fn eq(&self, other: &Self) -> bool {
        self.len == other.len && PartialEq::eq(&self.buf, &other.buf)
    }
}

impl<T: Eq> Eq for ArrayQueue<T> {}

impl<T: PartialOrd> PartialOrd for ArrayQueue<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        PartialOrd::partial_cmp(&self.buf, &other.buf)
    }
}

impl<T: Ord> Ord for ArrayQueue<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        Ord::cmp(&self.buf, &other.buf)
    }
}

impl<T: Hash> Hash for ArrayQueue<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.buf, state);
    }
}

impl<T> FromIterator<T> for ArrayQueue<T> {
    fn from_iter<U: IntoIterator<Item=T>>(iter: U) -> Self {
        let vec: Vec<Option<T>> = iter.into_iter().map(|item| Some(item)).collect();
        Self {
            len: vec.len(),
            buf: vec.into_boxed_slice(),
        }
    }
}

impl<T: fmt::Debug> fmt::Debug for ArrayQueue<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.buf, f)
    }
}

使用数组实现 - 消除 `Option<T>` 类型

上面中的队列, 使用了 [Option<T>] 来表示数组中的元素类型, 这有些占用空间, 我们可以将这个问题消除, 通过手动操作内存的方式. 当然这会引入 unsafe 的函数:

#![allow(unused)]
fn main() {
use std::{fmt, ptr};
use std::alloc::{alloc, Layout};
use std::cmp::Ordering;
use std::hash::{Hash, Hasher};
use std::mem::ManuallyDrop;
use std::ptr::NonNull;

pub struct ArrayQueue2<T> {
    len: usize,
    buf: Box<[T]>,
}

struct RawVec<T> {
    ptr: NonNull<T>,
    cap: usize,
}

#[derive(Debug, Clone, Copy, Eq, PartialEq)]
enum AllocError {
    CapacityOverflow,
    AllocateError,
}

impl<T> ArrayQueue2<T> {
    /// # Panics
    ///
    /// Raise panic if failed to allocate memory.
    #[must_use]
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0);
        let raw_vec = RawVec::<T>::try_allocate(capacity).expect("Failed to allocate buffer");
        let buf: Box<[T]> = unsafe { raw_vec.into_box() };
        Self {
            len: 0,
            buf,
        }
    }

    /// # Errors
    ///
    /// 当栈已满时再将元素入队, 就会返回错误, 以及原有的元素 `value`.
    pub fn push(&mut self, value: T) -> Result<(), T> {
        if self.len == self.buf.len() {
            return Err(value);
        }

        self.buf[self.len] = value;
        self.len += 1;

        Ok(())
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len > 0 {
            // Take the first value, without calling drop method.
            let front = unsafe {
                Some(ptr::read(self.buf.as_ptr()))
            };
            // Move memory.
            unsafe {
                ptr::copy(self.buf.as_ptr().wrapping_add(1), self.buf.as_mut_ptr(), self.len - 1);
            }
            self.len -= 1;
            front
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub const fn len(&self) -> usize {
        self.len
    }

    #[must_use]
    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    #[must_use]
    #[inline]
    pub const fn capacity(&self) -> usize {
        self.buf.len()
    }

    #[must_use]
    #[inline]
    pub const fn front(&self) -> Option<&T> {
        if self.len > 0 {
            Some(&self.buf[0])
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub fn front_mut(&mut self) -> Option<&mut T> {
        if self.len > 0 {
            Some(&mut self.buf[0])
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub const fn back(&self) -> Option<&T> {
        if self.len > 0 {
            Some(&self.buf[self.len - 1])
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub fn back_mut(&mut self) -> Option<&mut T> {
        if self.len > 0 {
            Some(&mut self.buf[self.len - 1])
        } else {
            None
        }
    }
}

impl<T: PartialEq> PartialEq for ArrayQueue2<T> {
    fn eq(&self, other: &Self) -> bool {
        self.len == other.len && PartialEq::eq(&self.buf, &other.buf)
    }
}

impl<T: Eq> Eq for ArrayQueue2<T> {}

impl<T: PartialOrd> PartialOrd for ArrayQueue2<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        PartialOrd::partial_cmp(&self.buf, &other.buf)
    }
}

impl<T: Ord> Ord for ArrayQueue2<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        Ord::cmp(&self.buf, &other.buf)
    }
}

impl<T: Hash> Hash for ArrayQueue2<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.buf, state);
    }
}

impl<T> FromIterator<T> for ArrayQueue2<T> {
    fn from_iter<U: IntoIterator<Item=T>>(iter: U) -> Self {
        let vec: Vec<T> = iter.into_iter().collect();
        Self {
            len: vec.len(),
            buf: vec.into_boxed_slice(),
        }
    }
}

impl<T: fmt::Debug> fmt::Debug for ArrayQueue2<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.buf, f)
    }
}

impl<T> RawVec<T> {
    fn try_allocate(
        capacity: usize,
    ) -> Result<Self, AllocError> {
        debug_assert!(capacity > 0);
        let Ok(layout) = Layout::array::<T>(capacity) else {
            return Err(AllocError::CapacityOverflow);
        };

        let ptr = unsafe { alloc(layout) };
        if ptr.is_null() {
            return Err(AllocError::AllocateError);
        }
        let ptr = unsafe {
            NonNull::new_unchecked(ptr.cast::<T>())
        };

        Ok(Self { ptr, cap: capacity })
    }

    unsafe fn into_box(self) -> Box<[T]> {
        let me = ManuallyDrop::new(self);
        unsafe {
            let slice = ptr::slice_from_raw_parts_mut(me.ptr.as_ptr(), me.cap);
}

使用链表实现

可以使用链表来实现动态数组, 不限制队列中的元素个数.

对标准库中的双链表, 就可以很容易支持队列的接口.

#![allow(unused)]
fn main() {
use std::cmp::Ordering;
use std::collections::LinkedList;
use std::fmt;
use std::hash::{Hash, Hasher};

#[allow(clippy::linkedlist)]
pub struct ListQueue<T> (LinkedList<T>);

impl<T> Default for ListQueue<T> {
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}

impl<T> ListQueue<T> {
    #[must_use]
    #[inline]
    pub const fn new() -> Self {
        Self(LinkedList::new())
    }

    #[inline]
    pub fn push(&mut self, value: T) {
        self.0.push_back(value);
    }

    #[must_use]
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        self.0.pop_front()
    }

    #[must_use]
    #[inline]
    pub fn len(&self) -> usize {
        self.0.len()
    }

    #[must_use]
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }

    #[must_use]
    #[inline]
    pub fn front(&self) -> Option<&T> {
        self.0.front()
    }

    #[must_use]
    #[inline]
    pub fn front_mut(&mut self) -> Option<&mut T> {
        self.0.front_mut()
    }

    #[must_use]
    #[inline]
    pub fn back(&self) -> Option<&T> {
        self.0.back()
    }

    #[must_use]
    #[inline]
    pub fn back_mut(&mut self) -> Option<&mut T> {
        self.0.back_mut()
    }
}

impl<T: PartialEq> PartialEq for ListQueue<T> {
    fn eq(&self, other: &Self) -> bool {
        PartialEq::eq(&self.0, &other.0)
    }
}

impl<T: Eq> Eq for ListQueue<T> {}

impl<T: PartialOrd> PartialOrd for ListQueue<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        PartialOrd::partial_cmp(&self.0, &other.0)
    }
}

impl<T: Ord> Ord for ListQueue<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        Ord::cmp(&self.0, &other.0)
    }
}

impl<T: Hash> Hash for ListQueue<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.0, state);
    }
}

impl<T> FromIterator<T> for ListQueue<T> {
    fn from_iter<U: IntoIterator<Item=T>>(iter: U) -> Self {
        let list = iter.into_iter().collect();
        Self(list)
    }
}

impl<T: fmt::Debug> fmt::Debug for ListQueue<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.0, f)
    }
}
}

环形缓冲区 Circular Buffer

环形缓冲区 Circular Buffer 又称为 Ring Buffer, Cyclic Buffer 或者 Circular Queue.

环形缓冲区是线性数据结构, 通常由数组来实现, 如下图所示:

circular buffer linear

将尾部与头部相连, 组成一个环形索引, 逻辑上的关系如下图所示.:

circular buffer circular

所以才称为环形缓冲区.

环形缓冲区实现的是单生产者-单消费者模式 (single-producer, single-consumer), 生产者将元素加到尾部, 然后消费者从头部读取元素, FIFO (first in first out).

与链表相比, 这种数据结构更加紧凑, 空间利用率高, 对CPU的缓存友好, 常用作 I/O buffering.

环形缓冲区的基本操作

TODO(Shaohua):

初始化缓冲区

因为缓冲区的容量是事先确定的, 在初始化它的同时, 可以分配好相应的堆内存. 如果分配内存失败, 就直接产生 panic 异常.

函数签名是: pub fn new(capacity: usize) -> Self

向缓冲区中加入元素

函数签名是: pub fn push(&mut self, value: T) -> Result<(), T>

生产者调用它, 加入元素时, 如果缓冲区已经满了, 就直接返回 Err(value). 为了简化实现, 我们并没有定义相应的错误类型.

从缓冲区中读取元素

消费者调用它, 每次读取一个元素.

函数签名是: pub fn pop(&mut self) -> Option<T>

如果缓冲区已经空了, 就返回 None

环形缓冲区的实现

考虑到性能, 下面的 CircularBuffer 使用了几个 unsafe 接口, 要特别留意指针的操作.

#![allow(unused)]
fn main() {
use std::alloc::{alloc, dealloc, Layout};
use std::marker::PhantomData;
use std::ptr::NonNull;
use std::{mem, ops, ptr, slice};

pub struct CircularBuffer<T: Sized> {
    start: usize,
    len: usize,
    cap: usize,
    ptr: NonNull<T>,
    _marker: PhantomData<T>,
}

impl<T: Sized> CircularBuffer<T> {
    /// # Panics
    ///
    /// 分配内存失败时直接返回 panic
    #[must_use]
    #[inline]
    pub fn new(capacity: usize) -> Self {
        // 为了方便处理, 我们强制要求 capacity 是正数, 并且目前还没有考虑 ZST (zero sized type).
        assert!(capacity > 0);

        let layout = Layout::array::<T>(capacity).expect("Layout error");
        let ptr = unsafe { alloc(layout) };
        let ptr = NonNull::new(ptr).expect("Failed to alloc");

        Self {
            start: 0,
            len: 0,
            cap: capacity,
            ptr: ptr.cast(),
            _marker: PhantomData,
        }
    }

    #[must_use]
    #[inline]
    pub const fn as_mut_ptr(&self) -> *mut T {
        self.ptr.as_ptr()
    }

    #[must_use]
    #[inline]
    pub const fn as_ptr(&self) -> *const T {
        self.ptr.as_ptr()
    }

    #[must_use]
    #[inline]
    pub fn as_slice(&self) -> &[T] {
        self
    }

    #[must_use]
    #[inline]
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        self
    }

    /// # Errors
    ///
    /// 当缓冲区已满时返回 `Err(value)`
    pub fn push(&mut self, value: T) -> Result<(), T> {
        if self.is_full() {
            Err(value)
        } else {
            unsafe {
                // 计算新元素的指针位置
                let end = (self.start + self.len) % self.cap;
                let end_ptr = self.as_mut_ptr().add(end);
                self.len += 1;
                ptr::write(end_ptr, value);
            }
            Ok(())
        }
    }

    /// 从缓冲区消费元素, 如果缓冲区已空, 就返回 `None`
    pub fn pop(&mut self) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            unsafe {
                // 计算起始元素的地址
                let start_ptr = self.as_ptr().add(self.start);
                self.start = (self.start + 1) % self.cap;
                self.len -= 1;
                Some(ptr::read(start_ptr))
            }
        }
    }

    /// 返回当前缓冲区中的元素个数
    #[must_use]
    #[inline]
    pub const fn len(&self) -> usize {
        self.len
    }

    #[must_use]
    #[inline]
    pub const fn capacity(&self) -> usize {
        self.cap
    }

    #[must_use]
    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len() == 0
    }

    #[must_use]
    #[inline]
    pub const fn is_full(&self) -> bool {
        self.len() == self.cap
    }

    // 计算当前的内存结构
    fn current_memory(&self) -> (NonNull<u8>, Layout) {
        assert_eq!(mem::size_of::<T>() % mem::align_of::<T>(), 0);
        unsafe {
            let align = mem::align_of::<T>();
            let size = mem::size_of::<T>().unchecked_mul(self.cap);
            let layout = Layout::from_size_align_unchecked(size, align);
            (self.ptr.cast(), layout)
        }
    }
}

/// 释放堆内存
impl<T> Drop for CircularBuffer<T> {
    fn drop(&mut self) {
        let (ptr, layout) = self.current_memory();
        unsafe { dealloc(ptr.as_ptr(), layout) }
    }
}

/// 实现 `Deref` 和 `DerefMut` traits.
impl<T> ops::Deref for CircularBuffer<T> {
    type Target = [T];

    #[inline]
    fn deref(&self) -> &[T] {
        unsafe { slice::from_raw_parts(self.as_ptr(), self.len) }
    }
}

impl<T> ops::DerefMut for CircularBuffer<T> {
    #[inline]
    fn deref_mut(&mut self) -> &mut [T] {
        unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) }
    }
}

/// 支持从迭代器初始化.
impl<T> FromIterator<T> for CircularBuffer<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        // 为了实现简单, 我们重用了 vec 的 `FromIterator` 实现.
        let vec: Vec<T> = iter.into_iter().collect();
        let len = vec.len();
        let cap = vec.capacity();
        let boxed = vec.into_boxed_slice();
        let ptr = Box::leak(boxed);
        let ptr = NonNull::new(ptr.as_mut_ptr()).unwrap();
        Self {
            start: 0,
            len,
            cap,
            ptr,
            _marker: PhantomData,
        }
    }
}
}

环形缓冲区的应用

有不少软件有使用它来管理缓冲区, 下面就列举几个.

比如, 在 linux 内核的网络栈, 接收到对方发送的数据包后, 就先放到对应的环形缓冲区, 并且根据它剩下的空间大小, 来通知发送方调整滑动窗口的大小.

参考

Circular buffer

单调队列 Monotonic queue

TODO(Shaohua)

双端队列 Deque

双端队列的基本操作

双端队列的实现

标准库中 VecDeque 的实现

哈稀表 Hash Tables

标准库中 HashMap 的实现

标准库中 HashSet 的实现

LinkedHashMap

树

二叉树

二叉树的线性存储结构

二叉树的链式存储结构

二叉树的遍历 Traversal

二叉树的前序遍历 Pre-order Traversal

二叉树的中序遍历

二叉树的后序遍历

二叉树的层序遍历

二叉搜索树 Binary Search Tree

平衡二叉树 Optimal BST

AVL树

Splay Tree

红黑树 Red-Black Trees

Left-leaning Red–Black Tree

多叉树

参考

m-ary tree

B-Trees

B+ Trees

B*-Tree

T-tree

参考

T-tree

LSM tree

Fractal-tree

标准库中 BTreeMap 的实现

字典树 Trie

Radix Tree

参考

Radix tree

Suffix Tree

参考

Suffix tree

R-tree

参考

R-tree

R-tree

Priority R-tree

参考

Priority R-tree

R*-tree

参考

R*-tree

R+-tree

参考

R+-tree

X-tree

参考

X-tree

K-d Tree

优先级队列 Priority Queues

Binary Heap

参考

Binary heap

双优先级队列 Dual Priority Queues

Skew Heap

Binomial Heap

参考

Binomial heap

Brodal Queue

参考

Brodal queue

Fibonacci Heap

参考

Fibonacci heap

Strict Fibonacci Heap

参考

Strict Fibonacci heap

标准库中 Binary Heap 的实现

图算法

深度优先搜索

广度优先搜索

最短路径

最小生成树

并发数据结构 Concurrent Data Structures

简介

并发数据结构 Concurrent data structures, CDS 有三个关键的主题:

安全 Safety, 满足多线程并发的规范
- 顺序规则 sequential specification, 像一个队列一样按顺序操作
- 同步 synchronization
可扩展性 Scalability, 随着处理器核心数的增多, 性能更好
- 理想情况下, 线性递增
- 实际情况, 超过 16 个线程之后, 会退化成次线性递增 (sublinear scaling)
有进度 Progress, 保证操作过程向前推进
- lock freedom: 至少有一个进度向前推进
- wait freedom: 所有的进度都向前推进

安全性 Safety

使用锁或者其它同步原语 (primitive synchronization) 来保护并发数据结构.

使用全局锁来保护顺序数据结构
使用自定义的同步协议来保护数据结构

可扩展性 Scalability

减少锁保护的作用域
- 读写锁 read-write locking
- hand-over-hand locking
- lock coupling
避免写数据以便减少无效的缓存
- 乐观锁

Lock-coupling Linked List

Concurrent Ring Buffer

Single-producer, single-consumer lock-free FIFO

Concurrent Hash Map

Concurrent List

Concurrent Deque

Concurrent Queue

Multi-producer, multi-consumer lock-free FIFO

参考

Concurrent SkipList Map

Concurrent SkipList Set

Concurrent Radix Tree

Skip Graph

参考

Skip graph

算法分析

测试用的数据集

algs4

排序 Sorting

所谓的数组排序, 就是按照相同的顺序将数组中所有元素依次排好.

排序算法的特点:

稳定排序 (stable sort): 排序相同值的元素时, 会保持它们在数组中的原有顺序
不稳定排序 (unstable sort): 排序相同值的元素时, 会打乱它们在数组中的原有顺序
adaptive sort: 能利用输入数组的已有顺序, 如果输入的是基本已排序好的数组, 排序效率更高
non-adaptive sort: 即使输入的数组已基本有序, 仍然需要固定的步骤完成排序工作, 所以排序效率较低
原地排序 (in-place sort): 不需要额外的内存空间, 只在原先的数组上进行排序; 当然, 在交换元素时用到的一个临时变量不算在内

参考

Sorting algorithm

冒泡排序 Bubble sort

该算法将数组分成了两个部分, 左侧部分是未排序的, 右侧部分是已排序好的.

排序的步骤

从左到右遍历数组, 比较相邻的元素, 将较大的元素放在右侧
重复这个过程, 这样最大的元素就会放在数组最右侧
重复步骤1-2, 找到第二大的元素, 并放在数组右侧第二个位置
直到没有元素需要被交换, 整个数组变得有序

下面以 arr = [9, 4, 1, 7]; 为例来进行演示.

第一阶段, 从左到右遍历数组, 找到最大的元素 9, 并将它放在数组最右侧.

bubble sort stage 1

第一阶段, 从左到右遍历数组, 找到最大的元素 7, 并将它放在数组右侧第二个位置.

bubble sort stage 2

第一阶段, 从左到右遍历数组, 发现数组已排序完成.

bubble sort stage 3

实现冒泡排序算法

#![allow(unused)]
fn main() {
/// 如果传入的数据是增序排好的, 那么只需要 `n-1` 次的比较, 以及 0 次的交换;
/// 平珓情况以及最坏情况下, 使用 `n^2 / 2` 次比较以及 `n^2 / 2` 次交换.
pub fn bubble_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    for i in 0..len {
        let mut swapped = false;
        // 以 (len - i - 1) 为分隔点, 左侧部分是无序的, 右侧部分是有序的
        for j in 0..(len - i - 1) {
            if arr[j] > arr[j + 1] {
                swapped = true;
                arr.swap(j, j + 1);
            }
        }

        // 如果没有元素需要交换, 说明左侧部分也是有序的
        if !swapped {
            break;
        }
    }
}
}

递归实现冒泡排序

根据上面的描述, 冒泡排序的第一步, 将最大的元素移到数组最右侧; 在第二步中, 将第二大的元素移到右侧第二位. 基于此, 就可以编写递归形式的冒泡排序算法:

如果数组长度为1, 就直接返回
将最大的元素移到数组最右侧
递归调用冒泡排序, 但忽略数组的最右侧元素

递归形式的冒泡排序算法需要额外占用 O(n) 的内存空间, 用于递归函数调用栈.

#![allow(unused)]
fn main() {
/// 递归形式的冒泡排序算法.
///
/// 与迭代形式的算法相比, 递归形式实现的算法, 并没有性能上的优势.
pub fn recursive_bubble_sort<T>(list: &mut [T])
where
    T: PartialOrd,
{
    let len = list.len();
    if len < 2 {
        return;
    }

    let mut swapped = false;
    for j in 0..(len - 1) {
        if list[j] > list[j + 1] {
            swapped = true;
            list.swap(j, j + 1);
        }
    }

    // 如果没有元素需要交换, 说明数组有序的
    if !swapped {
        return;
    }

    recursive_bubble_sort(&mut list[..(len - 1)]);
}
}

冒泡排序的特点

时间复杂度是 O(n^2), 空间复杂度是 O(1)
在交换元素时, 只与相邻的元素交换, 交换次数可能比较多
属于稳定排序 (stable sort)
是 adaptive sort
比较适合已经基本排序好的数组, 可以显著提高排序效率; 对于已排序好的数组, 时间复杂度是 O(n)
只适合元素比较少的数组

插入排序 Insertion sort

插入排序实现方法比较简单. 它一次排序一个元素, 将数组分成两部分, 左侧部分是有序的, 右侧部分是待排序的.

插入排序的步骤

从第二个元素开始遍历数组, 因为数组中的第一个元素是有序的
将第二个元素与第一个元素比较, 如果比第一个元素小, 就交换两者的位置
将第三个元素与第二个位置的元素比较, 如果比它小, 就交换位置, 并重复第2步
继续以上的步骤, 将无序元素与前面的有序的元素进行比较以及交换位置
重复操作, 直到整个数组都是有序的

第一阶段, 将第二个元素 4 与第一个元素 9 进行比较, 并交换位置:

insertion sort pass 1

第二阶段, 将第三个元素 1 与前面的元素比较, 并交换位置:

insertion sort pass 2

第三阶段, 将第四个元素 7 与前面的元素比较并交换位置:

insertion sort pass 3

插入排序的实现

#![allow(unused)]
fn main() {
/// 其思路是, 先将前 i 个元素调整为增序的, 随着 i 从 0 增大到 n, 整个序列就变得是增序了.
pub fn insertion_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    for i in 1..len {
        for j in (1..=i).rev() {
            if arr[j - 1] > arr[j] {
                arr.swap(j - 1, j);
            } else {
                break;
            }
        }
    }
}
}

递归实现插入排序

根据上面的描述, 插入排序会将数组分成两部分, 左侧部分是已经排好序的, 右侧部分是待排序的. 现在用递归的形式重新实现这个步骤:

对于第 k 个元素, 先将 list[0..k] 进行递归排序
然后将第 k 个元素与前面已经排序好的 list[0..k] 进行比较并交换位置, 以便让它放在合适的位置
这样的话, 整个数组最终就会变成有序的

#![allow(unused)]
fn main() {
/// 递归风格的插入排序算法
pub fn recursive_insertion_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    if len < 2 {
        return;
    }

    // 先将 list[..(len-1)] 中的元素排序.
    recursive_insertion_sort(&mut arr[..len - 1]);

    // 然后将最后一个元素插入到合适的位置.
    for i in (1..len).rev() {
        if arr[i - 1] > arr[i] {
            arr.swap(i - 1, i);
        } else {
            break;
        }
    }
}
}

二分插入排序法 Binary Insertion Sort

二分插入排序法结合了二分查找 (binary search) 与插入排序 (insertion sort).

根据上面的描述, 在对第 k 个元素进行排序时, list[0..k] 这部分已经是有序的了, 然后拿着第 k 个元素与它左侧的每个元素进行比较并交换, 直到找到合适的位置, 这个过程的时间复杂度是 O(k). 但因为 list[0..k] 数组已经是有序的了, 我们可以利用二分查找法 (binary search) 快速查找到第 k 个元素合适的位置, 这个过程的时间复杂度是 O(log k).

算法的实现如下所示:

#![allow(unused)]
fn main() {
fn binary_search<T>(arr: &[T], target: &T) -> usize
where
    T: PartialOrd,
{
    let mut left = 0;
    let mut right = arr.len() - 1;
    while left < right {
        let middle = left + (right - left) / 2;
        // 找到了相等的元素, 就返回该位置的下一个位置
        if arr[middle] == *target {
            return middle + 1;
        } else if arr[middle] < *target {
            left = middle + 1;
        } else {
            right = middle;
        }
    }

    // 没有找到相等的元素, 就返回期望的位置.
    if arr[arr.len() - 1] < *target {
        return arr.len();
    }
    if arr[0] > *target {
        return 0;
    }
    left
}

/// 二分插入排序法 binary insertion sort
pub fn binary_insertion_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    if len < 2 {
        return;
    }

    for i in 1..len {
        let target_pos = binary_search(&arr[..i], &arr[i]);
        for j in (target_pos..i).rev() {
            arr.swap(j, j + 1);
        }
    }
}
}

上述优化对选择排序的影响不大, 主要原因是耗时的操作在于移动数组中的元素, 而不是查找元素的合适位置.

插入排序的特点

时间复杂度是 O(n^2), 空间复杂度是 O(1)
- 如果传入的数据是增序排好的, 那么只需要 N-1 次的比较, 以及 0 次的交换
- 如果传入的数据是降序排好的, 那么需要 N^2/2 次的比较, 以及 N^2/2 次的交换
- 如果是乱序的, 大概需要 N^2/4 次的比较, 以及 N^2/4 次的交换
插入排序是稳定排序 (stable sort)
它是原地排序 in-place sort
插入排序比较适合元素较少的数组
插入排序适合基本已排序好的数组
插入排序常用于组合排序算法中, 用于排序较少元素的部分数组; 比如 cpp 里面的 std::sort() 以及 python 里的 timsort

选择排序 Selection sort

选择排序的逻辑很简单, 将数组分成两部分:

左侧部分是排序好的, 按顺序放着较小的元素
右侧部分是未排序的, 放着较大的元素

选择排序的步骤

遍历数组, 找到最小的元素, 让它与最左侧元素交换
遍历数组中剩下的元素, 找到最小的元素, 让它与最左侧第二位元素交换
重复上面的步骤, 直到所有元素都有序排列

我们以 arr = [9, 4, 1, 7]; 为例进行演示:

首先找到最小的元素 1, 把它与最左侧元素相交换:

selection sort pass 1

第二阶段, 找到剩下元素中最小的元素 4, 把它与左侧第二位相交换:

selection sort pass 2

第三阶段, 找到最小的元素 7, 把它与左侧第三个元素相交换:

selection sort pass 3

到达了数组的最右侧, 所有元素都已排好序.

选择排序的代码实现

#![allow(unused)]
fn main() {
pub fn selection_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    if arr.len() < 2 {
        return;
    }
    for i in 0..(len - 1) {

        // 找到最小元素的索引
        let mut min_index = i;
        for j in (i + 1)..len {
            if arr[j] < arr[min_index] {
                min_index = j;
            }
        }

        // 如果最小元素不是 `list[i]`, 就交换两个元素
        if i != min_index {
            arr.swap(i, min_index);
        }
    }
}
}

递归实现选择排序

以上代码是用的迭代方式实现的选择排序, 接下来我们以递归的方式重新实现它.

#![allow(unused)]
fn main() {
/// 递归实现选择排序
pub fn recursive_selection_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    fn get_min_index<T>(list: &[T], i: usize, len: usize) -> usize
    where
        T: PartialOrd,
    {
        if i == len - 1 {
            return i;
        }
        let j = get_min_index(list, i + 1, len);
        if list[i] < list[j] {
            i
        } else {
            j
        }
    }

    let len = arr.len();
    if arr.len() < 2 {
        return;
    }

    let min_index = get_min_index(arr, 0, len);
    // 将最小的元素交换到最左侧
    if min_index != 0 {
        arr.swap(0, min_index);
    }

    // 递归排序剩下的元素
    recursive_selection_sort(&mut arr[1..]);
}
}

优化选择排序

默认实现的选择排序, 在每次循环时会找到最小的元素, 然后把它放在数组的左侧部分. 每次循环时, 我们可以同时找到最大的元素, 然后把它放在数组的右侧部分. 这样的话, 每个循环就可以同时找到最小和最大的元素.

#![allow(unused)]
fn main() {
/// 选择排序的一个小优化.
///
/// 将最小的元素放在左侧的同时, 将最大的元素放在右侧.
pub fn two_way_selection_sort<T>(arr: &mut [T])
where
    T: PartialOrd + std::fmt::Debug,
{
    let len = arr.len();
    if arr.len() < 2 {
        return;
    }

    let mut start = 0;
    let mut end = len - 1;
    while start < end {
        // 找到最小元素的索引
        let mut min_index = start;
        let mut max_index = start;
        for i in start..=end {
            if arr[i] < arr[min_index] {
                min_index = i;
            }
            if arr[i] > arr[max_index] {
                max_index = i;
            }
        }

        // 交换最小元素
        if start != min_index {
            arr.swap(start, min_index);
        }

        // 交换最大元素
        if end != max_index {
            if start == min_index {
                // 如果没有交换最小元素, 说明数组中的元素还没有移动过, 可以直接交换
                arr.swap(end, max_index);
            } else {
                // 这时, 最小元素已经移到了最左侧, 我们需要判断这个移位操作给最大值带来的影响.
                if max_index == start {
                    // 此时, 最大值已经被移到了 `list[min_index]`.
                    if end != min_index {
                        arr.swap(end, min_index);
                    }
                } else {
                    arr.swap(end, max_index);
                }
            }
        }

        start += 1;
        if end > 1 {
            end -= 1;
        }
    }
}
}

选择排序支持稳定排序

默认实现的选择排序算法, 是将最小元素交换到它的目标位置, 这样的话移动元素的次数很少, 但是是不稳定排序. 为了实现稳定排序, 我们可以插入排序的方式, 将最小元素插入到目标位置, 然后将其它元素向右移动一个位置, 尽管这样一来性能比较差.

#![allow(unused)]
fn main() {
/// 选择排序的一个小优化.
///
/// 将最小的元素放在左侧的同时, 将最大的元素放在右侧.
pub fn two_way_selection_sort<T>(arr: &mut [T])
where
    T: PartialOrd + std::fmt::Debug,
{
    let len = arr.len();
    if arr.len() < 2 {
        return;
    }

    let mut start = 0;
    let mut end = len - 1;
    while start < end {
        // 找到最小元素的索引
        let mut min_index = start;
        let mut max_index = start;
        for i in start..=end {
            if arr[i] < arr[min_index] {
                min_index = i;
            }
            if arr[i] > arr[max_index] {
                max_index = i;
            }
        }

        // 交换最小元素
        if start != min_index {
            arr.swap(start, min_index);
        }

        // 交换最大元素
        if end != max_index {
            if start == min_index {
                // 如果没有交换最小元素, 说明数组中的元素还没有移动过, 可以直接交换
                arr.swap(end, max_index);
            } else {
                // 这时, 最小元素已经移到了最左侧, 我们需要判断这个移位操作给最大值带来的影响.
                if max_index == start {
                    // 此时, 最大值已经被移到了 `list[min_index]`.
                    if end != min_index {
                        arr.swap(end, min_index);
                    }
                } else {
                    arr.swap(end, max_index);
                }
            }
        }

        start += 1;
        if end > 1 {
            end -= 1;
        }
    }
}
}

选择排序的特点

即使数组中的元素基本排序好, 也需要遍历所有元素并比较大小, 这种情况下效率较低, 依然需要 n^2 / 2 次比较操作以及 n 次交换, 平均时间复杂度是 O(n log(n)), 空间复杂度是 O(1)
在所有排序算法中, 选择排序移动元素的次数最少, 每个元素最多只移动一次, 就可以移到最终位置; 这个算法比较适合那种比较元素时的成本低, 但移动元素成本比较高的情况 (比如, 移动文件中的内容)
选择排序是原地排序 (in-place sort)
选择排序是 in-adaptive sort
默认实现的选择排序算法是不稳定排序 (unstable), 但优化后的算法可以实现稳定排序 (stable sort)

归并排序 Merge sort

归并排序是分治算法的经典实现. 它将数组分成较小的数组并排序, 然后再将它们合并在一起, 得到的数组就是有序的了.

归并排序的步骤

默认实现的递归排序是自顶向下(top-down merge sort)的, 即将整个数组递归分隔.

分隔 divide: 将数组递归分成两部分子数组, 直到每部分只剩下一个元素为止
攻克 conquer: 使用分治算法排序每个子数组
合并 merge: 将排序好的子数组有序合并在一起

第一阶段: 将数组递归分隔 (partition) 成左右两部分:

merge sort partition pass

第二阶段, 将子数组合并在一起:

merge sort merge pass

归并排序的实现

#![allow(unused)]

fn main() {
/// 对于元素个数为 `N` 的数组, 自顶向下的归并排序 (top-down merge sort)
/// 最多使用 `N log(N)` 次比较以及 `6N log(N)` 次元素访问操作.
#[inline]
pub fn topdown_merge_sort<T>(arr: &mut [T])
where
    T: PartialOrd + Clone,
{
    if arr.is_empty() {
        return;
    }
    sort(arr, 0, arr.len() - 1);
}

/// 排序 `arr[low..=high]` 部分.
fn sort<T>(arr: &mut [T], low: usize, high: usize)
where
    T: PartialOrd + Clone,
{
    if low >= high {
        return;
    }

    let middle = low + (high - low) / 2;

    // 递归排序左侧部分数组
    sort(arr, low, middle);
    // 递归排序右侧部分数组
    sort(arr, middle + 1, high);

    // 合并左右两侧部分数组
    if arr[middle] > arr[middle + 1] {
        merge(arr, low, middle, high);
    }
}

/// 合并 `arr[low..=middle]` 以及 `arr[middle+1..=high]` 两个子数组.
///
/// 它不是原地合并.
#[allow(clippy::needless_range_loop)]
fn merge<T>(arr: &mut [T], low: usize, middle: usize, high: usize)
where
    T: PartialOrd + Clone,
{
    // 辅助数组, 先将数组复制一份.
    let aux = arr[low..=high].to_vec();

    // 再合并回原数组.
    let mut i = low;
    let mut j = middle + 1;

    for k in low..=high {
        if i > middle {
            arr[k] = aux[j - low].clone();
            j += 1;
        } else if j > high {
            arr[k] = aux[i - low].clone();
            i += 1;
        } else if aux[j - low] < aux[i - low] {
            arr[k] = aux[j - low].clone();
            j += 1;
        } else {
}

归并排序的特点

归并排序的时间复杂度是 O(n log(n)), 空间复杂度是 O(N)

元素较少时, 使用插入排序

在排序阶段, 如果数组元素较少时仍然使用递归的归并排序的话, 并不划算, 因为会有大量的递归分支被调用, 还可能导致栈溢出. 为此我们设置一个常量, CUTOFF=24, 当数组元素个数小于它时, 直接使用插入排序.

另外, 我们还在递归调用之前, 创建了辅助数组 aux, 这样就可以在合并时重用这个数组, 以减少内存的分配.

#![allow(unused)]
fn main() {
            i += 1;
        }
    }
}

/// 对于元素数较少的数组, 使用插入排序
pub fn insertion_merge_sort<T>(arr: &mut [T])
where
    T: PartialOrd + Clone,
{
    if arr.is_empty() {
        return;
    }
    let cutoff: usize = 24;
    let mut aux = arr.to_vec();
    sort_cutoff_with_insertion(arr, 0, arr.len() - 1, cutoff, &mut aux);
}

/// 排序 `arr[low..=high]` 部分, 如果元数较少, 就使用插入排序.
fn sort_cutoff_with_insertion<T>(
    arr: &mut [T],
    low: usize,
    high: usize,
    cutoff: usize,
    aux: &mut Vec<T>,
) where
    T: PartialOrd + Clone,
{
    if low >= high {
        return;
    }

    if high - low <= cutoff {
        insertion_sort(&mut arr[low..=high]);
        return;
    }

    let middle = low + (high - low) / 2;

    // 递归排序左侧部分数组
    sort_cutoff_with_insertion(arr, low, middle, cutoff, aux);
    // 递归排序右侧部分数组
    sort_cutoff_with_insertion(arr, middle + 1, high, cutoff, aux);

    // 合并左右两侧部分数组
    if arr[middle] > arr[middle + 1] {
        merge_with_aux(arr, low, middle, high, aux);
    }
}

/// 合并 `arr[low..=middle]` 以及 `arr[middle+1..=high]` 两个子数组.
///
/// 它不是原地合并.
#[allow(clippy::needless_range_loop)]
fn merge_with_aux<T>(arr: &mut [T], low: usize, middle: usize, high: usize, aux: &mut [T])
where
    T: PartialOrd + Clone,
{
    // 辅助数组, 先将数组复制一份.
    for index in low..=high {
        aux[index].clone_from(&arr[index]);
    }

    // 再合并回原数组.
    let mut i = low;
    let mut j = middle + 1;

    for k in low..=high {
        if i > middle {
            arr[k] = aux[j].clone();
            j += 1;

/// 其思路是, 先将前 i 个元素调整为增序的, 随着 i 从 0 增大到 n, 整个序列就变得是增序了.
pub fn insertion_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    for i in 1..len {
        for j in (1..=i).rev() {
            if arr[j - 1] > arr[j] {
                arr.swap(j - 1, j);
            } else {
                break;
            }
        }
    }
}
}

元素较少时, 使用希尔排序

这个方法是基于以上方法, 用希尔排序来代替插入排序, 可以得到更好的性能. 而且 CUTOFF 值也可以更大一些. 经过几轮测试发现, 对于希尔排序来说, CUTOFF 的取值位于 [64..92] 之间时, 性能较好.

#![allow(unused)]
fn main() {
            arr[k] = aux[i].clone();
            i += 1;
        } else if aux[j] < aux[i] {
            arr[k] = aux[j].clone();
            j += 1;
        } else {
            arr[k] = aux[i].clone();
            i += 1;
        }
    }
}

/// 对于元素数较少的数组, 使用希尔排序
pub fn shell_merge_sort<T>(arr: &mut [T])
where
    T: PartialOrd + Clone,
{
    if arr.is_empty() {
        return;
    }

    let cutoff: usize = 72;
    let mut aux = arr.to_vec();
    sort_cutoff_with_shell(arr, 0, arr.len() - 1, cutoff, &mut aux);
}

/// 排序 `arr[low..=high]` 部分, 如果元数较少, 就使用希尔排序.
fn sort_cutoff_with_shell<T>(
    arr: &mut [T],
    low: usize,
    high: usize,
    cutoff: usize,
    aux: &mut Vec<T>,
) where
    T: PartialOrd + Clone,
{

    let middle = low + (high - low) / 2;

    // 递归排序左侧部分数组
    sort_cutoff_with_insertion(arr, low, middle, cutoff, aux);
    // 递归排序右侧部分数组
    sort_cutoff_with_insertion(arr, middle + 1, high, cutoff, aux);

    // 合并左右两侧部分数组
    if arr[middle] > arr[middle + 1] {
        merge_with_aux(arr, low, middle, high, aux);
    }
}

/// 合并 `arr[low..=middle]` 以及 `arr[middle+1..=high]` 两个子数组.
///
/// 它不是原地合并.
#[allow(clippy::needless_range_loop)]
fn merge_with_aux<T>(arr: &mut [T], low: usize, middle: usize, high: usize, aux: &mut [T])
where
    T: PartialOrd + Clone,
{
    // 辅助数组, 先将数组复制一份.
    for index in low..=high {
        aux[index].clone_from(&arr[index]);
    }

    // 再合并回原数组.
    let mut i = low;
    let mut j = middle + 1;

    for k in low..=high {
        if i > middle {
            arr[k] = aux[j].clone();
            j += 1;

/// Shell sort is a simple extension to insertion sort that allows exchanging
/// elements that far apart.
///
/// It produces partially sorted array (h-sorted array).
pub fn shell_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    const FACTOR: usize = 3;
    let len = arr.len();

    // 计算第一个 gap 的值, 大概是 len/3
    let mut h = 1;
    while h < len / FACTOR {
        h = FACTOR * h + 1;
    }

    while h >= 1 {
        // 使用插入排序, 将 `arr[0..h]` 排序好
        for i in h..len {
            let mut j = i;
            while j >= h && arr[j - h] > arr[j] {
                arr.swap(j - h, j);
                j -= h;
            }
        }

        h /= FACTOR;
    }
}
}

迭代形式实现的归并排序

迭代形式的归并排序, 又称为自下而上的归并排序 (bottom-up merge sort). 它的步骤如下:

将连续的 2 个元素比较并合并在一起
将连续的 4 个元素比较并合并在一起
重复以上过程, 直到所有元素合并在一起

下面的流程图展示了一个简单的操作示例:

bottom-up merge sort

对应的代码实现如下:

#![allow(unused)]
fn main() {
    // 递归排序左侧部分数组
    sort_cutoff_with_shell(arr, low, middle, cutoff, aux);
    // 递归排序右侧部分数组
    sort_cutoff_with_shell(arr, middle + 1, high, cutoff, aux);

    // 合并左右两侧部分数组
    if arr[middle] > arr[middle + 1] {
        merge_with_aux(arr, low, middle, high, aux);
    }
}

/// 迭代形式的归并排序, 自底向上 bottom-up merge sort
pub fn bottom_up_merge_sort<T>(arr: &mut [T])
where
    T: PartialOrd + Clone,
{
    let len = arr.len();
    if len < 2 {
        return;
    }

    let mut aux = arr.to_vec();

    // 开始排序的数组大小, 从 1 到 len / 2
    // current_size 的取值是 1, 2, 4, 8, ...
    let mut current_size = 1;

    while current_size < len {
        // 归并排序的数组左侧索引
        let mut left_start = 0;

        // 子数组的起始点不同, 这样就可以遍历整个数组.
        // left_start 的取值是 0, 2 * current_size, 4 * current_size, ...
        // right_end 的取值是 2 * current_size, 4 * current_size, 6 * current_size, ...
        while left_start < len - 1 {
            let middle = (left_start + current_size - 1).min(len - 1);

    sort_cutoff_with_insertion(arr, middle + 1, high, cutoff, aux);

    // 合并左右两侧部分数组
    if arr[middle] > arr[middle + 1] {
        merge_with_aux(arr, low, middle, high, aux);
    }
}

/// 合并 `arr[low..=middle]` 以及 `arr[middle+1..=high]` 两个子数组.
///
/// 它不是原地合并.
#[allow(clippy::needless_range_loop)]
fn merge_with_aux<T>(arr: &mut [T], low: usize, middle: usize, high: usize, aux: &mut [T])
where
    T: PartialOrd + Clone,
{
    // 辅助数组, 先将数组复制一份.
    for index in low..=high {
        aux[index].clone_from(&arr[index]);
    }

    // 再合并回原数组.
    let mut i = low;
    let mut j = middle + 1;

    for k in low..=high {
        if i > middle {
            arr[k] = aux[j].clone();
            j += 1;
        } else if j > high {
            arr[k] = aux[i].clone();
            i += 1;
        } else if aux[j] < aux[i] {
            arr[k] = aux[j].clone();
}

三路归并排序 3-way merge sort

默认实现的归并排序, 是将数组分成左右两部分分别排序. 三路归并排序, 是将数组分成左中右三部分分别排序.

#![allow(unused)]
fn main() {
/// 三路归并排序
pub fn three_way_merge_sort<T>(arr: &mut [T])
where
    T: PartialOrd + Clone,
{
    if arr.is_empty() {
        return;
    }
    let mut aux = arr.to_vec();
    three_way_sort(arr, 0, arr.len() - 1, &mut aux);
}

/// 三路排序 `arr[low..=high]`
fn three_way_sort<T>(arr: &mut [T], low: usize, high: usize, aux: &mut Vec<T>)
where
    T: PartialOrd + Clone,
{
    // 如果数组长度小于2, 就返回.
    if low + 1 > high {
        return;
    }

    // 将数组分成三部分
    let middle1 = low + (high - low) / 3;
    let middle2 = low + 2 * ((high - low) / 3);

    // 递归排序各部分数组
    three_way_sort(arr, low, middle1, aux);
    three_way_sort(arr, middle1 + 1, middle2, aux);
    three_way_sort(arr, middle2 + 1, high, aux);

    // 合并三部分数组
    three_way_merge(arr, low, middle1, middle2, high, aux);
}

/// 合并 `arr[low..=middle1]`, `arr[middle1+1..=middle2]` 以及 `arr[middle2+1..=high]` 三个子数组.
///
/// 它不是原地合并.
#[allow(clippy::needless_range_loop)]
fn three_way_merge<T>(
    arr: &mut [T],
    low: usize,
    middle1: usize,
    middle2: usize,
    high: usize,
    aux: &mut [T],
) where
    T: PartialOrd + Clone,
{
    // 辅助数组, 先将数组复制一份.
    for index in low..=high {
        aux[index].clone_from(&arr[index]);
    }

    // 再合并回原数组.
    let mut i = low;
    let mut j = middle1 + 1;
    let mut k = middle2 + 1;
    let mut l = low;

    // 首先合并较小的子数组
    while i <= middle1 && j <= middle2 && k <= high {
        let curr_index = if aux[i] < aux[j] && aux[i] < aux[k] {
            &mut i
        } else if aux[j] < aux[k] {
            &mut j
        } else {
            &mut k
        };
        arr[l].clone_from(&aux[*curr_index]);
        *curr_index += 1;
        l += 1;
    }

    // 然后合并剩余部分的子数组
    while i <= middle1 && j <= middle2 {
        let curr_index = if aux[i] < aux[j] {
            &mut i
        } else {
            &mut j
        };
        arr[l].clone_from(&aux[*curr_index]);
        *curr_index += 1;
        l += 1;
    }

    while j <= middle2 && k <= high {
        let curr_index = if aux[j] < aux[k] {
            &mut j
        } else {
            &mut k
        };
        arr[l].clone_from(&aux[*curr_index]);
        *curr_index += 1;
        l += 1;
    }

    while i <= middle1 && k <= high {
        let curr_index = if aux[i] < aux[k] {
            &mut i
        } else {
            &mut k
        };
        arr[l].clone_from(&aux[*curr_index]);
        *curr_index += 1;
        l += 1;
    }

    while i <= middle1 {
        arr[l].clone_from(&aux[i]);
        i += 1;
        l += 1;
    }
    while j <= middle2 {
        arr[l].clone_from(&aux[j]);
        j += 1;
        l += 1;
    }
    while k <= high {
        arr[l].clone_from(&aux[k]);
        k += 1;
        l += 1;
    }
}
}

三路归并排序的特点:

时间复杂度是 O(n log_3(n)), 空间复杂度是 O(n)
但因为在 merge_xx() 函数中引入了更多的比较操作, 其性能可能更差

原地归并排序

原地归并排序, 是替代了辅助数组, 它使用类似插入排序的方式, 将后面较大的元素交换到前面合适的位置. 尽管省去了辅助数组, 但是因为移动元素的次数显著境多了, 其性能表现并不好.

下面的流程图展示了一个原地归并排序的示例:

in place merge sort merge pass

#![allow(unused)]
fn main() {
/// 原地归并排序
///
/// 尽管它不需要辅助数组, 但它的性能差得多, 时间复杂度是 `O(N^2 Log(N))`, 而默认实现的归并排序的
/// 时间复杂度是 `O(N Log(N))`.
pub fn in_place_merge_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    if arr.is_empty() {
        return;
    }
    sort_in_place(arr, 0, arr.len() - 1);
}

/// 原地排序 `arr[low..=high]`
fn sort_in_place<T>(arr: &mut [T], low: usize, high: usize)
where
    T: PartialOrd,
{
    if low >= high {
        return;
    }

    let middle = low + (high - low) / 2;
    sort_in_place(arr, low, middle);
    sort_in_place(arr, middle + 1, high);

    if arr[middle] > arr[middle + 1] {
        merge_in_place(arr, low, middle, high);
    }
}

/// 原地合并 `arr[low..=middle]` 以及 `arr[middle+1..=high]` 两个子数组.
fn merge_in_place<T>(arr: &mut [T], mut low: usize, mut middle: usize, high: usize)
where
    T: PartialOrd,
{
    let mut low2 = middle + 1;
    debug_assert!(arr[middle] > arr[low2]);

    while low <= middle && low2 <= high {
        if arr[low] <= arr[low2] {
            low += 1;
        } else {
            // 将所有元素右移, 并将 arr[low2] 插入到 arr[low] 所在位置. 这一步很慢.
            for index in (low..low2).rev() {
                arr.swap(index, index + 1);
            }

            // 更新所有的索引
            low += 1;
            middle += 1;
            low2 += 1;
        }
    }
}

}

原地归并排序的特点:

时间复杂度度是 O(N^2 Log(N)), 空间复杂度是 O(1)
c++ 的标准库里有实现类似的算法, 参考 inplace_merge

优化原地归并排序

上面的原地归并排序, 每次只移动一个元素间隔. 类似于希尔排序, 我们可以增大移动元素的间隔 (gap), 来减少移动元素的次数.

#![allow(unused)]
fn main() {
/// 对原地归并排序的优化
///
/// 它不需要辅助数组, 它参考了希尔排序, 通过调整元素间隔 gap 减少元素移动次数.
pub fn in_place_shell_merge_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    if arr.is_empty() {
        return;
    }
    sort_in_place_with_shell(arr, 0, arr.len() - 1);
}

/// 原地排序 `arr[low..=high]`
fn sort_in_place_with_shell<T>(arr: &mut [T], low: usize, high: usize)
where
    T: PartialOrd,
{
    if low >= high {
        return;
    }

    let middle = low + (high - low) / 2;
    sort_in_place_with_shell(arr, low, middle);
    sort_in_place_with_shell(arr, middle + 1, high);

    merge_in_place_with_shell(arr, low, high);
}

/// 使用希尔排序的方式原地合并 `arr[low..=middle]` 以及 `arr[middle+1..=high]` 两个子数组.
///
/// 时间复杂度 `O(N Log(N))`, 空间复杂度 `O(1)`
fn merge_in_place_with_shell<T>(arr: &mut [T], low: usize, high: usize)
where
    T: PartialOrd,
{
    #[must_use]
    #[inline]
    const fn next_gap(gap: usize) -> usize {
        const FACTOR: usize = 2;
        if gap == 1 {
            0
        } else {
            gap.div_ceil(FACTOR)
        }
    }
    let len = high - low + 1;
    let mut gap = next_gap(len);

    while gap > 0 {
        for i in low..=(high - gap) {
            let j = i + gap;
            // 每次间隔多个元素进行比较和交换.
            if arr[i] > arr[j] {
                arr.swap(i, j);
            }
        }
        gap = next_gap(gap);
    }
}
}

时间复杂度度是 O(n log(n) log(n)), 空间复杂度是 O(1)

Timsort

Timsort 在 Python, Java 等编程语言的标准库中都有使用, 综合性能比较好.

Timsort 是对归并排序(merge sort)的优化.

Timsort 的步骤

它的优化思路是:

先将数组分成相同间隔的子数组, 常用的间隔值是 32 或者 24
然后用插入排序(或者考虑用希尔排序) 对这些子数组进行排序, 因为这些子数组比较短小, 插入排序的效率比较高
排序后, 依次将子数组合并在一起形成有序的大数组, 直到整个数组变得有序
合并子数组的方法与归并排序里一致, 不再详述
如果数组中的元素较少, 就只会使用插入排序

下图展示了 timsort 的一个示例:

timsort

Timsort 的实现

#![allow(unused)]
fn main() {
use crate::insertion_sort::insertion_sort;
use crate::shell_sort::shell_sort;

/// Timsort 是对归并排序 (merge sort) 的优化.
pub fn timsort<T>(arr: &mut [T])
where
    T: PartialOrd + Clone,
{
    const RUN: usize = 32;

    let len = arr.len();
    if len < 2 {
        return;
    }

    // 先将数组分隔成大小相同的子数组, 并利用插入排序进行排序.
    // 插入排序比较善于处理已基本有序的较小的数组.
    for i in (0..len).step_by(RUN) {
        let end = (i + RUN).min(len);
        insertion_sort(&mut arr[i..end]);
    }

    // 然后将各个子数组合并在一起
    // 数组间隔依次是 RUN, RUN * 2, RUN * 4, ...
    let mut size = RUN;
    while size < len {
        // 合并子数组
        for left in (0..len).step_by(2 * size) {
            // 两个子数组分别是 `arr[left..=middle]` 和 `arr[middle+1..=right]`.
            let middle = left + size - 1;
            let right = (left + 2 * size - 1).min(len - 1);

            if middle < right {
                merge(arr, left, middle, right);
            }
        }

        size *= 2;
    }
}

/// 合并子数组 `arr[left..=middle]` 和 `arr[middle+1..=right]`
fn merge<T>(arr: &mut [T], left: usize, middle: usize, right: usize)
where
    T: PartialOrd + Clone,
{
    // 先创建辅助数组
    let aux_left = arr[left..=middle].to_vec();
    let aux_right = arr[middle + 1..=right].to_vec();
    let left_len = middle - left + 1;
    let right_len = right - middle;

    // 合并子数组
    let mut i = 0;
    let mut j = 0;
    let mut k = left;
    while i < left_len && j < right_len {
        if aux_left[i] < aux_right[j] {
            arr[k].clone_from(&aux_left[i]);
            i += 1;
        } else {
            arr[k].clone_from(&aux_right[j]);
            j += 1;
        }
        k += 1;
    }

    // 最后复制剩下的元素
    while i < left_len {
        arr[k].clone_from(&aux_left[i]);
        i += 1;
        k += 1;
    }

    while j < right_len {
        arr[k].clone_from(&aux_right[j]);
        j += 1;
        k += 1;
    }
}

/// 其思路是, 先将前 i 个元素调整为增序的, 随着 i 从 0 增大到 n, 整个序列就变得是增序了.
pub fn insertion_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    for i in 1..len {
        for j in (1..=i).rev() {
            if arr[j - 1] > arr[j] {
                arr.swap(j - 1, j);
            } else {
                break;
            }
        }
    }
}
}

使用希尔排序代替插入排序

上面提到了, 可以用希尔排序来代替插入排序, 可以将子数组的间隔设置得更大些, 我们选取 RUN = 64;

#![allow(unused)]
fn main() {
/// 使用希尔排序代替插入排序
///
/// 只创建一次辅助数组
pub fn shell_timsort<T>(arr: &mut [T])
where
    T: PartialOrd + Clone,
{
    const RUN: usize = 64;

    let len = arr.len();
    if len < 2 {
        return;
    }

    // 先将数组分隔成大小相同的子数组, 并利用插入排序进行排序.
    // 插入排序比较善于处理已基本有序的较小的数组.
    for i in (0..len).step_by(RUN) {
        let end = (i + RUN).min(len);
        shell_sort(&mut arr[i..end]);
    }

    // 然后将各个子数组合并在一起
    // 数组间隔依次是 RUN, RUN * 2, RUN * 4, ...
    let mut size = RUN;
    let mut aux = arr.to_vec();

    while size < len {
        // 合并子数组
        for left in (0..len).step_by(2 * size) {
            // 两个子数组分别是 `arr[left..=middle]` 和 `arr[middle+1..=right]`.
            let middle = left + size - 1;
            let right = (left + 2 * size - 1).min(len - 1);

            if middle < right {
                merge_with_aux(arr, left, middle, right, &mut aux);
            }
        }

        size *= 2;
    }
}

/// 合并子数组 `arr[left..=middle]` 和 `arr[middle+1..=right]`
fn merge_with_aux<T>(arr: &mut [T], left: usize, middle: usize, right: usize, aux: &mut [T])
where
    T: PartialOrd + Clone,
{
    // 先初始化辅助数组
    for i in left..=right {
        aux[i].clone_from(&arr[i]);
    }

    // 合并子数组
    let mut i = left;
    let mut j = middle + 1;
    let mut k = left;
    while i <= middle && j <= right {
        if aux[i] < aux[j] {
            arr[k].clone_from(&aux[i]);
            i += 1;
        } else {
            arr[k].clone_from(&aux[j]);
            j += 1;
        }
        k += 1;
    }

    while i <= middle {
        arr[k].clone_from(&aux[i]);
        i += 1;
        k += 1;
    }
    while j <= right {
        arr[k].clone_from(&aux[j]);
        j += 1;
        k += 1;
    }
}

#[cfg(test)]
mod tests {
    use crate::timsort::{shell_timsort, timsort};

    #[test]
    fn test_timsort() {

/// Shell sort is a simple extension to insertion sort that allows exchanging
/// elements that far apart.
///
/// It produces partially sorted array (h-sorted array).
pub fn shell_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    const FACTOR: usize = 3;
    let len = arr.len();

    // 计算第一个 gap 的值, 大概是 len/3
    let mut h = 1;
    while h < len / FACTOR {
        h = FACTOR * h + 1;
    }

    while h >= 1 {
        // 使用插入排序, 将 `arr[0..h]` 排序好
        for i in h..len {
            let mut j = i;
            while j >= h && arr[j - h] > arr[j] {
                arr.swap(j - h, j);
                j -= h;
            }
        }

        h /= FACTOR;
    }
}
}

Timsort 的特点

最差情况下的时间复杂度是: O(n log(n)), 最间复杂度是 O(n)
如果数组已基本有序, 最好情况下的时间复杂度是 O(n)
是稳定排序, 不是原地排序 (in-place sort)
与归并排序不同的是, 它不需要递归调用自身将数组分成左右子数组
timsort 与插入归并排序的区别较大

参考

快速排序 Quicksort

与归并排序类似, 快速排序也是分治算法的经典实践.

选择基准值 pivot 的方法有多种, 比如:

总是选择第一个元素
总是选择最后一个元素
从数组中随机选择一个元素
选择数组中的中值 median

快速排序的步骤

快速排序的关键在于基准值 pivot 的选择.

我们选取数组的最后一个元素作为基准值 pivot, 分隔数组为左右两部分
1. 使用变量 i 标记当前比基准值大的元素位置
2. 遍历数组, 把比基准值小的元素交换到 i 的左侧, 比基准值大的元素留在元素 i 的右侧
3. 最后, 把元素 i 与数组最右侧的基准值元素交换位置, 这样就把基准值放在了它的最终位置
将数组分成两部分, 左侧部分的元素值都比基准值小, 右侧部分比基准值大
然后递归调用快速排序算法, 对左右两侧子数组进行排序

下面以 arr = [1, 8, 3, 9, 4]; 为例子展示如何对数组分区.

首先选择最后一个元素 4 作为基准值 pivot. 将第一个元素 1 与基准值比较, 它比基准值小, 就需要交换元素 swap(i, j), 并将索引 i 右移一位:

quicksort partition pass1

将第二个元素 8 与基准值比较, 它比基准值大, 就什么都不做:

quicksort partition pass2

将第三个元素 3 与基准值比较, 它比基准值小, 就需要交换元素 swap(i, j), 并将索引 i 右移一位:

quicksort partition pass3

将第四个元素 9 与基准值比较, 它比基准值大, 就什么都不做:

quicksort partition pass4

最后一步, 将基准值 pivot 元素与当前的元素 i 进行交换, 这样的话 pivot 就被移动到了它的最终位置:

quicksort partition pass5

快速排序的实现

默认使用最后一个元素作为基准值 pivot. 如果是已排序好的数组, 这种算法是最差情况, 时间复杂度是 O(n^2).

#![allow(unused)]
fn main() {
/// 使用最后一个元素作为基准值 pivot
///
/// 如果是已排序好的数组, 这种算法是最差情况
#[inline]
pub fn quicksort<T: PartialOrd>(arr: &mut [T]) {
    if arr.len() < 2 {
        return;
    }
    tail_quicksort_helper(arr, 0, arr.len() - 1);
}

fn tail_quicksort_helper<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) {
    if low >= high {
        return;
    }

    // 按照基数的位置, 将数组划分成左右两个子数组.
    let pivot_index = partition_pivot_at_right(arr, low, high);
    // 对左右两个子数组分别执行快速排序
    if pivot_index > low + 1 {
        tail_quicksort_helper(arr, low, pivot_index - 1);
    }
    if pivot_index + 1 < high {
        tail_quicksort_helper(arr, pivot_index + 1, high);
    }
}

// 选择最右侧的元素作为基准值
fn partition_pivot_at_right<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) -> usize {
    let pivot_index = high;

    // 以 pivot 为基准, 把数组划分成三部分: 小于 pivot, pivot, 大于等于 pivot
    // i 用于标记比 pivot 大的元素
    let mut i = low;
    // j 用于遍历整个数组
    for j in low..high {
        if arr[j] < arr[pivot_index] {
            arr.swap(i, j);
            i += 1;
        }
    }

    // 最后把基准值 pivot 移到合适的位置.
    // 此时, 数组中元素的顺序满足以下条件: 小于 pivot, pivot, 大于等于 pivot
    arr.swap(i, pivot_index);
    // 返回的是 pivot 所在的位置
    i
}
}

快速排序的特点

最好情况的时间复杂度是 O(n log(n)), 平均情况下的时间复杂度是 O(n log(n))
最差情况的时间复杂度是 O(n^2), 因为选择的基准值 pivot 很不合适
如果不考虑递归调用的栈空间, 快速排序的空间复要度是 O(1)
如果考虑递归调用的栈空间, 最好情况下的空间复杂度是 O(log(n)), 最差情况下的空间复杂度是 O(n)
不是稳定排序 (stable sort). 如果所需的排序算法不要求是稳定排序的, 那么我们应该优先考虑快速排序及其变体
是原地排序 (in-place sort), 不需要辅助数组
比归并排序 (merge sort) 要快, 不需要一个额外的数组来保存中间值
它适对对大数据集做排序, 效率高; 不适合排序小的数据集
快速排序是缓存友好型的 (cache-friendly), 能充分发挥缓存的局部性优势, 因为它是顺序遍历数组的

使用第一个元素作为基准值

上面我实现的分区算法, 使用最后一个元素作为基准值 pivot. 我们也可以选取数组的第一个元素作为基准值, 但如果数组已经是逆序排序的, 这种算法是最差情况, 时间复杂度是 O(n^2).

算法实现如下:

#![allow(unused)]
fn main() {
/// 总是选择第一个元素作为基准值
///
/// 果数组已经是逆序排序的, 这种算法是最差情况, 时间复杂度是 `O(n^2)`
#[inline]
pub fn head_quicksort<T: PartialOrd>(arr: &mut [T]) {
    if arr.len() < 2 {
        return;
    }
    head_quicksort_helper(arr, 0, arr.len() - 1);
}

fn head_quicksort_helper<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) {
    if low >= high {
        return;
    }

    // 按照基数的位置, 将数组划分成左右两个子数组.
    let pivot_index = partition_pivot_at_left(arr, low, high);
    // 对左右两个子数组分别执行快速排序
    if pivot_index > low + 1 {
        head_quicksort_helper(arr, low, pivot_index - 1);
    }
    if pivot_index + 1 < high {
        head_quicksort_helper(arr, pivot_index + 1, high);
    }
}

/// 选择最左侧的元素作为基准值
fn partition_pivot_at_left<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) -> usize {
    let pivot_index = low;

    // 以 pivot 为基准, 把数组划分成三部分: 小于等于 pivot, pivot, 大于 pivot
    // i 用于标记比 pivot 大的元素
    let mut i = high;
    // j 用于遍历整个数组
    for j in ((low + 1)..=high).rev() {
        if arr[j] > arr[pivot_index] {
            arr.swap(i, j);
            i -= 1;
        }
    }

    // 最后把基准值 pivot 移到合适的位置.
    // 此时, 数组中元素的顺序满足以下条件: 小于等于 pivot, pivot, 大于 pivot
    arr.swap(i, pivot_index);
    // 返回的是 pivot 所在的位置
    i
}
}

双指针风格的分区算法

上面的代码中, 我们都使用变量 j 来遍历数组, 这里我们也可以使用靠拢型双指针的写法遍历数组.

#![allow(unused)]
fn main() {
/// 总是选择第一个元素作为基准值, 并使用双指针法进行数组分区.
#[inline]
pub fn two_pointer_quicksort<T: PartialOrd>(arr: &mut [T]) {
    if arr.len() < 2 {
        return;
    }
    two_pointer_quicksort_helper(arr, 0, arr.len() - 1);
}

fn two_pointer_quicksort_helper<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) {
    if low >= high {
        return;
    }

    // 按照基数的位置, 将数组划分成左右两个子数组.
    let pivot_index = partition_with_two_pointers(arr, low, high);
    // 对左右两个子数组分别执行快速排序
    if pivot_index > low + 1 {
        two_pointer_quicksort_helper(arr, low, pivot_index - 1);
    }
    if pivot_index + 1 < high {
        two_pointer_quicksort_helper(arr, pivot_index + 1, high);
    }
}

/// 使用双指针法选择最左侧的元素作为基准值
fn partition_with_two_pointers<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) -> usize {
    let pivot_index = low;

    // 使用双指针法遍历数组, 以 pivot 为基准, 把数组划分成三部分:
    // 小于等于 pivot, pivot, 大于 pivot
    let mut left: usize = low;
    let mut right: usize = high;
    while left < right {
        // right 的位置左移, 直到 arr[right] 小于等于 pivot
        while left < right && arr[right] > arr[pivot_index] {
            right -= 1;
        }

        // left 的位置右移, 直到 arr[left] 大于 pivot
        while left < right && arr[left] <= arr[pivot_index] {
            left += 1;
        }

        // 交换元素
        arr.swap(left, right);
    }

    // 最后把基准值 pivot 移到合适的位置.
    // 此时, 数组中元素的顺序满足以下条件: 小于等于 pivot, pivot, 大于 pivot
    arr.swap(left, pivot_index);
    // 返回的是 pivot 所在的位置
    left
}
}

当元素较少时, 使用插入排序

当元素较少时, 递归调用快速排序算法会产生非常多的调用分支, 效率很低. 跟之前的优化方法类似, 当元素个数较少时, 我们直接调用插入排序.

#![allow(unused)]
fn main() {
/// 如果元素较少, 就使用插入排序
#[inline]
pub fn insertion_quicksort<T: PartialOrd>(arr: &mut [T]) {
    if arr.len() < 2 {
        return;
    }
    insertion_quicksort_helper(arr, 0, arr.len() - 1);
}

fn insertion_quicksort_helper<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) {
    const CUTOFF: usize = 24;

    if low >= high {
        return;
    }

    // 数组中的元数个数低于一个阈值时, 使用插入排序
    if high - low + 1 < CUTOFF {
        insertion_sort(&mut arr[low..=high]);
        return;
    }

    // 按照基数的位置, 将数组划分成左右两个子数组.
    let pivot_index = partition_pivot_at_right(arr, low, high);
    // 对左右两个子数组分别执行快速排序
    if pivot_index > low + 1 {
        insertion_quicksort_helper(arr, low, pivot_index - 1);
    }
    if pivot_index + 1 < high {
        insertion_quicksort_helper(arr, pivot_index + 1, high);
    }
}

// 选择最右侧的元素作为基准值
fn partition_pivot_at_right<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) -> usize {
    let pivot_index = high;

    // 以 pivot 为基准, 把数组划分成三部分: 小于 pivot, pivot, 大于等于 pivot
    // i 用于标记比 pivot 大的元素
    let mut i = low;
    // j 用于遍历整个数组
    for j in low..high {
        if arr[j] < arr[pivot_index] {
            arr.swap(i, j);
            i += 1;
        }
    }

    // 最后把基准值 pivot 移到合适的位置.
    // 此时, 数组中元素的顺序满足以下条件: 小于 pivot, pivot, 大于等于 pivot
    arr.swap(i, pivot_index);
    // 返回的是 pivot 所在的位置
    i
}

/// 其思路是, 先将前 i 个元素调整为增序的, 随着 i 从 0 增大到 n, 整个序列就变得是增序了.
pub fn insertion_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    for i in 1..len {
        for j in (1..=i).rev() {
            if arr[j - 1] > arr[j] {
                arr.swap(j - 1, j);
            } else {
                break;
            }
        }
    }
}
}

迭代形式的快速排序

默认情况下实现的快速排序使用了递归形式, 它用了尾递归调用来保存数组的左右边界值. 我们也可以显式地使用一个栈结构来手动保存它们, 就可以将快速排序改写成迭代形式:

#![allow(unused)]
fn main() {
/// 迭代形式的快速排序
///
/// 空间复杂度是 `O(n)`
#[inline]
pub fn iterative_quicksort<T: PartialOrd>(arr: &mut [T]) {
    if arr.len() < 2 {
        return;
    }
    iterative_quicksort_helper(arr, 0, arr.len() - 1);
}

fn iterative_quicksort_helper<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) {
    if low >= high {
        return;
    }

    let len = high - low + 1;
    let mut stack = vec![0; len];

    // 入栈顺序是 (low, high)
    stack.push(low);
    stack.push(high);

    // 出栈顺序是 (high, low)
    while let (Some(high), Some(low)) = (stack.pop(), stack.pop()) {
        // 按照基数的位置, 将数组划分成左右两个子数组.
        let pivot_index = partition_pivot_at_right(arr, low, high);
        // 对左右两个子数组分别执行快速排序
        // 如果左侧子数组还有元素, 就入栈
        if pivot_index > low + 1 {
            stack.push(low);
            stack.push(pivot_index - 1);
        }
        // 如果 pivot 的右侧还有元素, 就入栈
        if pivot_index + 1 < high {
            stack.push(pivot_index + 1);
            stack.push(high);
        }
    }
}

// 选择最右侧的元素作为基准值
fn partition_pivot_at_right<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) -> usize {
    let pivot_index = high;

    // 以 pivot 为基准, 把数组划分成三部分: 小于 pivot, pivot, 大于等于 pivot
    // i 用于标记比 pivot 大的元素
    let mut i = low;
    // j 用于遍历整个数组
    for j in low..high {
        if arr[j] < arr[pivot_index] {
            arr.swap(i, j);
            i += 1;
        }
    }

    // 最后把基准值 pivot 移到合适的位置.
    // 此时, 数组中元素的顺序满足以下条件: 小于 pivot, pivot, 大于等于 pivot
    arr.swap(i, pivot_index);
    // 返回的是 pivot 所在的位置
    i
}

/// 其思路是, 先将前 i 个元素调整为增序的, 随着 i 从 0 增大到 n, 整个序列就变得是增序了.
pub fn insertion_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    for i in 1..len {
        for j in (1..=i).rev() {
            if arr[j - 1] > arr[j] {
                arr.swap(j - 1, j);
            } else {
                break;
            }
        }
    }
}
}

随机选择一个元素作为基准值 pivot

尾递归优化 Tail call optimization

稳定快速排序 Stable Quicksort

双轴快速排序 Dual pivot Quicksort

三路快速排序 3-way Quicksort

参考

Quicksort

堆排序 Heap Sort

IntroSort

参考

Introsort

pdqsort

Pattern-defeating quicksort 简称为 pdqsort.

参考

pdqsort

希尔排序 Shell Sort

接下面的几节介绍几个不常用的排序算法.

本节介绍的希尔排序 (shell sort) 是插入排序的 (insertion sort) 的变体.

插入排序的一个问题是, 将元素 k 移动到左侧排序好的数组中的位置时, 通常还要移动元素 k 左侧的元素, 而移动元素的成本比较高. 希尔排序对这个过程做了优化, 以减少移动元素的次数.

希尔排序将数组拆解成由 h 个元素组成的小数组, 依次降低h间隔的值, 直到其为1, 这样就减少了元素交换的次数.

希尔排序的步骤

初始化间隔值 h = len / 3
使用插入排序法, 将 arr[h..] 与 arr[..h] 间的元素进行排序, 使用插入排序法, 但两个待比较的元素的间隔是 h, 而不是默认的 1, 这一步很重要, 它有助于减少元素的移动次数
减少间隔值, h /= 3, 重复上面的步骤, 直到最后一个循环 h = 1

这里的 h 值是由大到小变化的, 就是说, 每次移动的步长是h, 就是为了减少元素被移动的次数. 当 h = 1 时, 整个序列就完成排序了.

希尔排序的实现

#![allow(unused)]
fn main() {
/// Shell sort is a simple extension to insertion sort that allows exchanging
/// elements that far apart.
///
/// It produces partially sorted array (h-sorted array).
pub fn shell_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    const FACTOR: usize = 3;
    let len = arr.len();

    // 计算第一个 gap 的值, 大概是 len/3
    let mut h = 1;
    while h < len / FACTOR {
        h = FACTOR * h + 1;
    }

    while h >= 1 {
        // 使用插入排序, 将 `arr[0..h]` 排序好
        for i in h..len {
            let mut j = i;
            while j >= h && arr[j - h] > arr[j] {
                arr.swap(j - h, j);
                j -= h;
            }
        }

        h /= FACTOR;
    }
}
}

希尔排序的特点

最差情况下的时间复杂度 O(n^2), 空间复杂度是 O(1)
最好情竞下的时间复杂度是 Ω(n log(n))
比插入排序快
与插入排序不同的时, 希尔排序适合大中型的数组, 对于任意顺序的数组也有效

侏儒排序 Gnome Sort

侏儒排序又称为愚人排序 (Stupid Sort), 它类似于插入排序, 在移动元素时用到了的方法类似于冒泡排序, 它不需要使用多层循环嵌套.

侏儒排序的步骤

侏儒排序将数组分成两部分, 左侧部分是有序的, 右侧部分是无序的. 它只需要一层循环, 用于遍历数组中的所有元素. 将目标元素 k 与左侧的有序数组进行比较, 如果它更小, 就与左侧的元素交换位置, 并将循环体中的索引值向左移. 这样的话下次进入循环体时, 仍然访问的是元素 k, 然后重复上面的比较操作和交换操作, 直到元素 k 被放置在了合适的位置.

第一阶段, 找到第二个元素 4, 将它与第一个元素进行比较并交换位置:

gnome sort pass 1

第二阶段, 找到第三个元素1, 将它与左侧的元素进行比较并换换位置:

gnome sort pass 2

第三阶段, 找到第三个元素7, 将它与左侧的元素进行比较并换换位置:

gnome sort pass 3

侏儒排序的实现

#![allow(unused)]
fn main() {
/// Gnome sort is a variation of the insertion sort sorting algorithm
/// that does not use nested loops.
///
/// [Gnome sort](https://en.wikipedia.org/wiki/Gnome_sort)
pub fn gnome_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let mut index = 0;
    while index < arr.len() {
        // 当前元素比左侧元素大, 是有序的
        if index == 0 || arr[index] >= arr[index - 1] {
            index += 1;
        } else {
            // 当前元素比左侧元素小, 交换它们
            arr.swap(index, index - 1);
            index -= 1;
        }
    }
}
}

侏儒排序的特点

它的时间复杂度是 O(n^2), 空间复杂度是 O(1)
对于排序好的数组来说, 时间复杂度是 O(n)

桶排序 Bucket Sort

前文介绍的几种排序算法都是基于比较元素之间的关系 (comparison based), 这对于像字符串或者其它自定义数据类型也是有效的, 只需要实现 PartialOrd 即可, 具有通用性.

桶排序是基于元素的数值大小, 而不是比较关系 (non-comparison based), 这类算法只适合整数和定长的字符串.

桶排序也是一种线性排序方法. 它将元素分配到多个桶中, 然后对每个桶单独进行排序.

桶排序的步骤

根据原数组中元素的数值范围, 将数组分成 m 个桶, 每个桶将存放一定数值区间的元素, 而且这些数值区间有序不重叠
按顺序遍历数组, 将元素按数值大小放到目标桶中, 每个桶会存放相近或者相同的元素
使用插入排序等算法对每个桶排序
按照桶的顺序, 将每个桶中的元素依次存储到原数组

bucket sort

桶排序的实现

#![allow(unused)]
fn main() {
use crate::shell_sort::shell_sort;

/// 桶排序, 使用插入排序来处理每个桶.
#[allow(clippy::cast_sign_loss)]
pub fn bucket_sort(arr: &mut [i32]) {
    if arr.is_empty() {
        return;
    }

    // 对于插入排序来说, 元素的个数在这个范围内的效率比较高.
    let bucket_elements: usize = 72;
    let min_num: i32 = arr.iter().min().copied().unwrap_or_default();
    let max_num: i32 = arr.iter().max().copied().unwrap_or_default();
    // 计算数值范围.
    let range: i32 = max_num - min_num;
    // 计算桶的个数, 我们假设元素的数值是均匀分布的.
    // 这样的话就可以确定每个桶要存储的数值范围.
    // 尽可能把数值相近的元素放在一起.
    let bucket_count: usize = range as usize / bucket_elements + 1;
    // 创建一系列的桶.
    let mut buckets: Vec<Vec<i32>> = vec![vec![]; bucket_count];

    // 遍历数组, 将元素分配到每个桶中.
    // 这里是按数组的原有顺序插入到桶中的, 有相同数值的元素也会依照原先的顺序放置到同一个桶.
    for &num in arr.iter() {
        // 计算这个元素值处于哪个数值段, 并确定该放到哪个桶.
        let bucket_index: usize = (num - min_num) as usize / bucket_elements;
        buckets[bucket_index].push(num);
    }

    // 对每一个桶单独排序, 按照假设, 每个桶中的元素个数都比较少,
    // 使用插入排序可以发挥它的优势.
    // 并且插入排序是稳定排序, 所以该桶排序算法也是稳定排序.
    let mut index: usize = 0;
    for mut bucket in buckets {
        insertion_sort(&mut bucket);
        // 将这个桶中的元素合并到原先的数组中.
        arr[index..(index + bucket.len())].copy_from_slice(&bucket);
        index += bucket.len();

/// 其思路是, 先将前 i 个元素调整为增序的, 随着 i 从 0 增大到 n, 整个序列就变得是增序了.
pub fn insertion_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    for i in 1..len {
        for j in (1..=i).rev() {
            if arr[j - 1] > arr[j] {
                arr.swap(j - 1, j);
            } else {
                break;
            }
        }
    }
}
}

桶排序的特点

如果给每个桶做排序是的算法是稳定排序的, 那么桶排序算法就是稳定排序
时间复杂度是 O(n), 空间复杂度是 O(n + m)
比快速排序还要快

使用希尔排序

上面的代码中, 我们使用插入排序来给每个桶排序, 这次我们换成希尔排序. 后者可以支持排序更多的元素, 依然保持较好的性能.

#![allow(unused)]
fn main() {
}

/// 桶排序的另一种实现, 使用希尔排序来处理每个桶.
#[allow(clippy::cast_sign_loss)]
pub fn shell_bucket_sort(arr: &mut [i32]) {
    if arr.is_empty() {
        return;
    }

    // 对于希尔排序来说, 元素的个数在这个范围内的效率比较高.
    let bucket_elements: usize = 72 * 2;

    let min_num: i32 = arr.iter().min().copied().unwrap_or_default();
    let max_num: i32 = arr.iter().max().copied().unwrap_or_default();
    let range: i32 = max_num - min_num;
    let bucket_count: usize = range as usize / bucket_elements + 1;
    let mut buckets: Vec<Vec<i32>> = vec![vec![]; bucket_count];

    for &num in arr.iter() {
        let bucket_index: usize = (num - min_num) as usize / bucket_elements;
        buckets[bucket_index].push(num);
    }
    let mut index: usize = 0;
    for mut bucket in buckets {
        shell_sort(&mut bucket);
        arr[index..(index + bucket.len())].copy_from_slice(&bucket);
        index += bucket.len();

/// Shell sort is a simple extension to insertion sort that allows exchanging
/// elements that far apart.
///
/// It produces partially sorted array (h-sorted array).
pub fn shell_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    const FACTOR: usize = 3;
    let len = arr.len();

    // 计算第一个 gap 的值, 大概是 len/3
    let mut h = 1;
    while h < len / FACTOR {
        h = FACTOR * h + 1;
    }

    while h >= 1 {
        // 使用插入排序, 将 `arr[0..h]` 排序好
        for i in h..len {
            let mut j = i;
            while j >= h && arr[j - h] > arr[j] {
                arr.swap(j - h, j);
                j -= h;
            }
        }

        h /= FACTOR;
    }
}
}

基数排序 Radix Sort

基数排序是基于数值的每一个整数位或字符串中的每个字符来排序, 直到整个数组变得有序.

基数排序基于上文介绍的桶排序的思想.

根据排序的方向可以划分为最低位基数排序 (Least Significant Digit, LSD) 和是高位基数排序 (Most Significant Digit, MSD).

基数排序的步骤

基数排序的实现

#![allow(unused)]
fn main() {
#[allow(clippy::cast_possible_truncation)]
pub fn radix_sort(arr: &mut [u32]) {
    const fn num_digits(mut num: u32) -> usize {
        let mut count: usize = 0;
        while num != 0 {
            count += 1;
            num /= 10;
        }
        count
    }

    if arr.is_empty() {
        return;
    }
    // 获取最大的位数
    let max_digits: usize = arr
        .iter()
        .map(|num| num_digits(*num))
        .max()
        .unwrap_or_default();

    for i in 0..max_digits {
        // bucket 长度为10, 代表了数字 0~9.
        let mut buckets = vec![vec![]; 10];

        for num in arr.iter() {
            // 这个 index 是关键, 它是每个元素在当前位上的数字
            let index: u32 = *num / 10_u32.pow(i as u32) % 10;
            buckets[index as usize].push(*num);
        }

        let mut index = 0;
        for bucket in buckets {
            for num in bucket {
                // 取出对应的元素, 更新到原始数组中
                arr[index] = num;
                index += 1;
            }
        }
    }
}
}

基数排序的特点

基数排序是一种线性排序算法
时间复杂度是 O(n * m), 空间复杂度是 O(n + m), 其中 n 是数组中的个数, m 是元数的最大位数
可以对数值或者字符串排序
基数排序是稳定排序

计数排序 Counting Sort

计数排序不是基于比较值的排序算法.

计数排序的步骤

计数排序的实现分几个阶段:

首先遍历输入数组, 计算元素的取值范围
生成计数数组, 其元素个数基于元素的取值范围确定
遍历输入数组, 根据每个元素与最小元素的差值作为索引, 更新计数数组
更新计数数组, 使之成为前缀和数组
初始化输出数组
从最后一个元素开始遍历输入数组, 每个元素都存放 num
- 计算当前元素与最小元素的差值 delta_index
- 从计数数组中取得该元素的索引值 let num_index = count_arr[delta_index]
- 更新输出数组, 将 num 放到相应的位置, arr[num_index - 1] = num
- 并更新计数数组, 将里面的索引值减1, count_arr[delta_index] -= 1

计数排序的实现

下面的算法限制了输入元素是 i32:

#![allow(unused)]
fn main() {
}

#[allow(clippy::cast_sign_loss)]
pub fn counting_sort(arr: &mut [i32]) {
    if arr.is_empty() {
        return;
    }
    let min_num: i32 = arr.iter().min().copied().unwrap_or_default();
    let max_num: i32 = arr.iter().max().copied().unwrap_or_default();
    // 计算数值范围
    let range: i32 = max_num - min_num;
    let size: usize = range as usize + 1;

    // 构造计数数组
    let mut count_arr = vec![0_usize; size];

    // 遍历输入数组, 更新计数数组
    for &num in arr.iter() {
        let delta: i32 = num - min_num;
        let index: usize = delta as usize;
        count_arr[index] += 1;
    }

    // 生成累积数组, prefix sum array
    for i in 1..size {
        count_arr[i] += count_arr[i - 1];
    }

    // 构造输入数组, 只读的
    let input_arr: Vec<i32> = arr.to_vec();

    // 从输入数组的右侧向左侧遍历, 这样实现的是稳定排序.
    for &num in input_arr.iter().rev() {
        // 计算当前值与最小值的差.
        let delta: i32 = num - min_num;
        let delta_index = delta as usize;
        // 从 count_arr 里取出该数值的相对位置
        let num_index: usize = count_arr[delta_index];
        // 把 num 放在对应的位置
        arr[num_index - 1] = num;

        // 同时更新 count_arr, 使之计数减1, 这样的话下一个相同数值的元素的索引值就被左移了一位.
        count_arr[delta_index] -= 1;
}

下面的代码对计数排序加入了泛型的支持, 注意它的类型 T 有很多限制:

#![allow(unused)]
fn main() {
use std::collections::BTreeMap;
use std::ops::Sub;

pub fn counting_sort_generic<T>(arr: &mut [T])
where
    T: Copy + Default + Ord + Sub<Output=T> + TryInto<usize>,
{
    if arr.is_empty() {
        return;
    }
    let min_num: T = arr.iter().min().copied().unwrap_or_default();
    let max_num: T = arr.iter().max().copied().unwrap_or_default();
    // 计算数值范围
    let range: T = max_num - min_num;
    let size: usize = range.try_into().unwrap_or_default() + 1;

    // 构造计数数组
    let mut count_arr = vec![0_usize; size];

    // 遍历数组, 更新计数数组
    for num in arr.iter() {
        let delta: T = *num - min_num;
        let index: usize = delta.try_into().unwrap_or_default();
        count_arr[index] += 1;
    }

    // 生成累积数组, prefix sum array
    for i in 1..size {
        count_arr[i] += count_arr[i - 1];
    }

    // 构造输入数组, 只读的
    let input_arr = arr.to_vec();

    for &num in input_arr.iter().rev() {
        let delta: T = num - min_num;
        let delta_index: usize = delta.try_into().unwrap_or_default();
        // 从 count_arr 里取出该数值的相对位置
        let num_index: usize = count_arr[delta_index];
        // 把 num 放在对应的位置
        arr[num_index - 1] = num;

        // 同时更新 count_arr, 使之计数减1, 这样的话下一个相同数值的元素的索引值就被左移了一位.
        count_arr[delta_index] -= 1;
    }
}

计数排序的特点

空间复杂度是 O(n + m), n 是输入数组的大小, m 是计数数组的大小, 也就是元素的数值范围
时间复杂度是 O(n + m)
计数排序是稳定排序, 但不是原地排序 (in-place sorting)
如果数组中的元素值所处的范围比较大的话, 计数排序的效率就比较低
它需要较多的额外空间来存储中间值
计数排序要比归并排序和快速排序等基于比较元素值的排序算法都要快
计数排序不惧怕有重复的元素, 但是如果元素的取值范围比较大的话, 其效率就很低

使用 map 作为计数数组的容器

上面实现的计数排序, 其计数数组对于元素的取值范围很敏感, 甚至计数数组中可能有很多的值都是0, 它们都被浪费掉了.

对此, 我们可以做一些优化, 使用 map 来存储计数数组中的值.

#![allow(unused)]
fn main() {
use std::collections::BTreeMap;
use std::ops::Sub;

pub fn counting_sort_generic<T>(arr: &mut [T])
where
    T: Copy + Default + Ord + Sub<Output=T> + TryInto<usize>,
{
    if arr.is_empty() {
        return;
    }
    let min_num: T = arr.iter().min().copied().unwrap_or_default();
    let max_num: T = arr.iter().max().copied().unwrap_or_default();
    // 计算数值范围
    let range: T = max_num - min_num;
    let size: usize = range.try_into().unwrap_or_default() + 1;

    // 构造计数数组
    let mut count_arr = vec![0_usize; size];

    // 遍历数组, 更新计数数组
    for num in arr.iter() {
        let delta: T = *num - min_num;
        let index: usize = delta.try_into().unwrap_or_default();
        count_arr[index] += 1;
    }

    // 生成累积数组, prefix sum array
    for i in 1..size {
        count_arr[i] += count_arr[i - 1];
    }

    // 构造输入数组, 只读的
    let input_arr = arr.to_vec();

    for &num in input_arr.iter().rev() {
        let delta: T = num - min_num;
        let delta_index: usize = delta.try_into().unwrap_or_default();
        // 从 count_arr 里取出该数值的相对位置
        let num_index: usize = count_arr[delta_index];
        // 把 num 放在对应的位置
        arr[num_index - 1] = num;

        // 同时更新 count_arr, 使之计数减1, 这样的话下一个相同数值的元素的索引值就被左移了一位.
        count_arr[delta_index] -= 1;
    }
}

#[allow(clippy::cast_sign_loss)]
pub fn counting_sort(arr: &mut [i32]) {
    if arr.is_empty() {
        return;
    }
    let min_num: i32 = arr.iter().min().copied().unwrap_or_default();
    let max_num: i32 = arr.iter().max().copied().unwrap_or_default();
    // 计算数值范围
    let range: i32 = max_num - min_num;
    let size: usize = range as usize + 1;

    // 构造计数数组
    let mut count_arr = vec![0_usize; size];

    // 遍历输入数组, 更新计数数组
    for &num in arr.iter() {
        let delta: i32 = num - min_num;
        let index: usize = delta as usize;
        count_arr[index] += 1;
    }

    // 生成累积数组, prefix sum array
    for i in 1..size {
        count_arr[i] += count_arr[i - 1];
    }

    // 构造输入数组, 只读的
    let input_arr: Vec<i32> = arr.to_vec();

    // 从输入数组的右侧向左侧遍历, 这样实现的是稳定排序.
    for &num in input_arr.iter().rev() {
        // 计算当前值与最小值的差.
        let delta: i32 = num - min_num;
        let delta_index = delta as usize;
        // 从 count_arr 里取出该数值的相对位置
        let num_index: usize = count_arr[delta_index];
        // 把 num 放在对应的位置
        arr[num_index - 1] = num;

        // 同时更新 count_arr, 使之计数减1, 这样的话下一个相同数值的元素的索引值就被左移了一位.
        count_arr[delta_index] -= 1;
    }
}

#[allow(clippy::cast_sign_loss)]
pub fn counting_sort_with_map(arr: &mut [i32]) {
    if arr.is_empty() {
        return;
    }

    // 构造字典, 存储元素的频率
    let mut freq_map: BTreeMap<i32, usize> = BTreeMap::new();
    // 遍历输入数组, 更新计数数组
    for &num in arr.iter() {
        *freq_map.entry(num).or_default() += 1;
    }

    // 遍历字典
    let mut i = 0;
    for (num, freq) in freq_map {
        for _j in 0..freq {
            arr[i] = num;
            i += 1;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::{counting_sort, counting_sort_generic, counting_sort_with_map};

    #[test]
    fn test_counting_sort() {
        let mut list = [0, 5, 3, 2, 2];
        counting_sort(&mut list);
        assert_eq!(list, [0, 2, 2, 3, 5]);

        let mut list = [-2, -5, -45];
        counting_sort(&mut list);
        assert_eq!(list, [-45, -5, -2]);

        let mut list = [
            -998_166, -996_360, -995_703, -995_238, -995_066, -994_740, -992_987, -983_833,
            -987_905, -980_069, -977_640,
        ];
        counting_sort(&mut list);
        assert_eq!(
            list,
            [
                -998_166, -996_360, -995_703, -995_238, -995_066, -994_740, -992_987, -987_905,
                -983_833, -980_069, -977_640,
            ]
        );
    }

    #[test]
    fn test_counting_sort_generic() {
        let mut list = [0, 5, 3, 2, 2];
        counting_sort_generic(&mut list);
        assert_eq!(list, [0, 2, 2, 3, 5]);

        let mut list = [-2, -5, -45];
        counting_sort_generic(&mut list);
        assert_eq!(list, [-45, -5, -2]);

        let mut list = [
            -998_166, -996_360, -995_703, -995_238, -995_066, -994_740, -992_987, -983_833,
            -987_905, -980_069, -977_640,
        ];
        counting_sort_generic(&mut list);
        assert_eq!(
            list,
            [
                -998_166, -996_360, -995_703, -995_238, -995_066, -994_740, -992_987, -987_905,
                -983_833, -980_069, -977_640,
            ]
        );
    }

    #[test]
    fn test_counting_sort_with_map() {
        let mut list = [0, 5, 3, 2, 2];
        counting_sort_with_map(&mut list);
        assert_eq!(list, [0, 2, 2, 3, 5]);

        let mut list = [-2, -5, -45];
        counting_sort_with_map(&mut list);
        assert_eq!(list, [-45, -5, -2]);

        let mut list = [
            -998_166, -996_360, -995_703, -995_238, -995_066, -994_740, -992_987, -983_833,
            -987_905, -980_069, -977_640,
        ];
        counting_sort_with_map(&mut list);
        assert_eq!(
            list,
            [
                -998_166, -996_360, -995_703, -995_238, -995_066, -994_740, -992_987, -987_905,
                -983_833, -980_069, -977_640,
            ]
        );
    }
}
}

该算法的特点是

时间复杂度是 O(n log(n)), 空间复杂度是 O(n)
即使输入数组的取值范围较大, 也不成问题

标准库中排序算法的实现

链表排序 List Sort

上一章介绍了数组的多种排序方法. 与数组不同的是, 链表结构不支持随机索引.

对链表中的元素进行排序, 有它自己的特点.

冒泡排序 Bubble Sort

插入排序 Insertion Sort

Javascript Program For Insertion Sort In A Singly Linked List

选择排序 Selection Sort

Selection sort

归并排序 Merge Sort

Merge Sort for Linked Lists

快速排序 Quicksort

外部排序 External Sorting

Multiway Merge

Polyphase Merge

Distribution Sort

Cache-oblivious Distribution Sort

查找 Searching

查找 (searching) 是数组最常用的操作之一. 所谓的查找操作, 就是在一组元素中找到某个特定的元素.

常用的查找算法有:

线性查找 linear search
二分查找 binary search
三元查找/三叉查找 ternary search

在无序数组中查找

使用二分查找法进行有序数组的查找

线性查找 Linear Search

所谓的线性查找, 指的是从数组的一端开始, 依次遍历每一个元素, 找到目标元素后终止, 或者到达了数组的另一端才终止. 该算法还有一个别名, 叫顺序查找 sequential search.

线性查找的步骤

从数组的第一个元素开始遍历整个数组
将当前元素与目标元素进行比较
如果当前元素与相等, 就终止循环并返回当前元素的索引值
如果不相等, 就移到数组中的下一个元素
重复第2-4步, 直到数组的尾部
如果到达数组尾部后, 仍然没有找到想要的元素, 就返回没有找到(比如用 -1, 或者 None 表示)

线性查找的实现

#![allow(unused)]
fn main() {
#[must_use]
pub fn linear_search<T: PartialOrd>(slice: &[T], target: &T) -> Option<usize> {
    for (index, item) in slice.iter().enumerate() {
        if item == target {
            return Some(index);
        }
    }
    None
}
}

线性查找算法的特性

该算法的时间复杂度是 O(N), 空间复杂度是 O(1).
这个算法适合没有排序过的数组
比较适合元素较少的数组
不需要使用额外的内存
因为是依次遍历元素, CPU 缓存命中率较高

二分查找 Binary Search

二分查找的步骤

实现二分查找法

二分查找法的特点

递归实现二分查找法

没有找到元素时, 返回期望的位置

二分查找法的边界值

二分查找相关的问题列表

容易

TODO:

中等

TODO:

困难

0154. 寻找旋转排序数组中的最小值 II Find Minimum in Rotated Sorted Array II

TODO:

0004. 寻找两个正序数组的中位数 Median of Two Sorted Arrays

三元查找 Ternary Search

Jump Search

Jump Search

Interpolation Search

Interpolation Search

Exponential Search

Exponential Search

标准库中二分查找法的实现

位运算 Bitwise Algorithms

比特位操作函数表:

A	B	A OR B	A AND B	A XOR B	NOT A
1	1	1	1	0	0
1	0	1	0	1	0
0	1	1	0	1	1
0	0	0	0	0	1

BitOr, |
BitAnd, &
BitXor, ^
BitNot, ~
左移, <<
右移, >>

对自己异或操作结果为0

这个问题考察的是比特位异或操作中的一个重要特性: A XOR A == 0.

我们可以利用这个特性, 遍历数组中的每一项, 然后计算异或值, 最后的结果就是那个单值.

self-xor

Single Number

这个思路, 可以用于快速消除数组中出现偶数次的元素.

交换两个数值

或者, 不使用临时变量, 交换两个变量的值:

#![allow(unused)]
fn main() {
/// Swap two numbers without temporary variable.
///
/// ```rust
/// use bitwise::swap_number::swap_number;
///
/// let mut a = 3;
/// let mut b = 42;
/// swap_number(&mut a, &mut b);
/// assert_eq!(a, 42);
/// assert_eq!(b, 3);
/// ```
#[allow(clippy::manual_swap)]
pub fn swap_number(a: &mut i32, b: &mut i32) {
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}
}

递归 Recursion

排列与组合

矩阵 Matrix

质数

数独

任意精度算术运算

双指针 Two Pointers

双指针算法, 通常用于简化对数组(或者链表)的遍历, 可以只用一次遍历, 就能快速解决问题, 时间复杂度通常只有 O(n). 而无脑实现的暴力算法 (brute force), 通常需要内外两层遍历迭代, 其时间复杂度往往达到了 O(n^2).

可以说, 如果一个问题可以用双指针法解决的话, 其性能通常是很好的.

快慢型双指针

即访问数组(或者链表)时, 使用两个索引(或指针), 而不是通常的一个索引.

这两个指针, 分别称为快指针 (fast pointer) 和慢指针 (slow pointer).

快指针, 用于从0到n依次遍历整个数组, 即每次循环 fast += 1, 访问下一个元素

慢指针用于让数组中元素实现某个特定条件最高位索引, 比如件条可以是元素不重复. 当满足条件后, 要对数组做什么样的调整, 比如交换元素或者移除元素, 然后 slow += 1, 移动慢指针指向下一个元素. 当条件不满足时, 慢指针不动.

具体的过程看下图:

fast-slow

靠拢型双指针问题

靠拢型双指针是指使用两个指针从左右两端访问数组, 往中间靠拢直到重叠.

靠拢型指针的一般步骤:

初始化左右两个指针, 分别指向数组的左右两端 (left, right)
开始遍历数组, 循环中止的条件就是两个指针重叠 ( left == right)
根据题目要求, 选中左右两个指针中的一个, 往中间靠靠拢 (left += 1 或者 right -= 1, 另一个指针不动
直到循环中止

Dutch National Flag, DNF

这是上面方法的一个变形, 可以查看问题 0075. 颜色分类 Sort Colors, 这个方法用于实现三路分区 (three-way partition).

The Dutch national flag

TODO(Shaohua): Add more description

参考

Dutch national flag problem

并行双指针

这也是一类双指针问题. 用两个指针分别遍历两个数组(或者链表).

parallel

初始化两个指针, 分别指向两个数组的头部元素
如果条件成立, 就同时向右(高位)移动两个指针; 否则, 只移动其中一个, 比如 index1 += 1 或者 index2 += 1
终止条件是, 直到有一个数组被遍历完

这个方法可以用来处理两个有序数组或者链表的合并; 或者计算两个集合的交集和并集.

滑动窗口 Sliding Window

回溯法 Backtracking

分治法 Divide and Conquer

动态规划 Dynamic Programming

贪心算法 Greedy Algorithms

图算法

内存

缓存过期算法 Cache Management

倒计时 TTL

最近最少使用 LRU

最近最不频繁使用 LFU

限流算法 Rate limiter

令牌桶 Token bucket

漏桶算法 Leaking bucket

固定窗口计数 Fixed window counter

滑动窗口日志 Sliding window log

滑动窗口计数 Sliding window counter

leetcode 问题分类

这一节, 分别基于问题所属的标签, 和问题编号, 列出问题, 方便索引.

目前采用的刷题顺序:

数学
比特位操作
双指针
数组
链表
哈稀表
字符串
栈
队列
树
回溯
贪心
动态规划
图

困难程度

难度	知识点
入门	数组, 字符串, 链表, 排序
简单	栈, 队列, 哈希表, 双指针
中等	二叉树, 堆, 单调栈, 滑动窗口, 二分, 位运算
困难	DP, DFS, BFS, 回溯, 贪心, 并查集, 前缀树

数组相关的问题列表

容易

TODO:

中级

0189. 轮转数组 Rotate Array

TODO:

矩阵 Matrix

简单

0463. 岛屿的周长 Island Perimeter

中等

困难

前缀和数组 (Prefix Sum Array) 相关的问题列表

简单

中等

0238. 除自身以外数组的乘积 Product of Array Except Self

困难

双指针相关的问题列表

容易

TODO:

中等

TODO:

滑动窗口相关的问题列表

简单

0485. 最大连续1的个数 Max Consecutive Ones

中等

TODO:

424. 替换后的最长重复字符

困难

220. Contains Duplicate III

二分查找相关的问题列表

容易

TODO:

中等

TODO:

困难

0154. 寻找旋转排序数组中的最小值 II Find Minimum in Rotated Sorted Array II

TODO:

0004. 寻找两个正序数组的中位数 Median of Two Sorted Arrays

排序

简单

中等

TODO:

0056. Merge Intervals

困难

链表相关的问题列表

容易

TODO:

中等

TODO:

困难

TODO:

参考

LeetCode算法题整理（链表篇）LinkedList

链表排序 Sorting

链表双指针 Two Pointers

队列 Queue

单调队列 Monotonic queue

栈相关的问题列表

容易

0020. 有效的括号 Valid Parentheses

TODO:

中等

TODO:

困难

单调栈 Monotonic

简单

0496. 下一个更大元素 I Next Greater Element I

中等

0739. 每日温度 Daily Temperatures

困难

0042. 接雨水 Trapping Rain Water

优先级队列 Priority Queue

简单

中等

0347. 前 K 个高频元素 Top K Frequent Elements

困难

哈稀表相关的问题列表

容易

TODO:

中等

TODO:

字符串相关的问题列表

容易

TODO:

中级

TODO:

字符串匹配 String Matching

字典树 Trie

树相关的问题列表

容易

中等

二叉树的遍历 Traversal

二叉树的还原 Restore

二叉搜索树 Binary Search Tree

二叉索引树 Binary Indexed Tree

二叉索引树又称为树状数组.

线段树 Segment Tree

并查集 Union-Find Data Structure

图相关的问题列表

TODO(Shaohua): Update problems list

容易

中等

TODO:

最小生成树 Minimum Spanning Tree

递归相关的问题列表 Recursion

简单

中等

困难

0060. Permutation Sequence

位运算相关的问题列表

简单

TODO:

中等

1780. 判断一个数字是否可以表示成三的幂的和 Check if Number is a Sum of Powers of Three

TODO:

29. Divide Two Integers

困难

数学问题的问题列表

简单

TODO:

9. Palindrome Number

中等

TODO:

3100. Water Bottles II

回溯法相关的问题列表 Backtracking

简单

TODO:

401. Binary Watch

中等

TODO:

面试题08.08.有重复字符串的排列组合

困难

0679. 24 点游戏 24 Game

分治法相关的问题列表 Divide and Conquer

简单

中等

324. Wiggle Sort II

困难

深度优先搜索 Depth First Search, DFS

简单

中等

困难

广度优先搜索 Bridth First Search, BFS

简单

中等

0322. 零钱兑换 Coin Change

困难

动态规划相关的问题列表 Dynamic Programming

容易

0338. 比特位计数 Counting Bits

TODO:

中等

TODO:

困难

TODO:

贪心算法相关的问题列表

容易

中等

leetcode 问题分类

这一节, 分别基于问题所属的标签, 和问题编号, 列出问题, 方便索引.

目前采用的刷题顺序:

数学
比特位操作
双指针
数组
链表
哈稀表
字符串
栈
队列
树
回溯
贪心
动态规划
图

困难程度

难度	知识点
入门	数组, 字符串, 链表, 排序
简单	栈, 队列, 哈希表, 双指针
中等	二叉树, 堆, 单调栈, 滑动窗口, 二分, 位运算
困难	DP, DFS, BFS, 回溯, 贪心, 并查集, 前缀树