Rust

2025年10月07日更新 8 人订阅
原价: ¥ 6 限时优惠
专栏简介 Rust编程语言之错误处理 Rust 语言之 flod Rust编程语言之Cargo、Crates.io详解 Rust编程语言之枚举与模式匹配 Rust语言 - 接口设计的建议之受约束(Constrained) Rust编程语言之无畏并发 Rust语言 - 接口设计的建议之灵活(flexible) Rust语言 - 接口设计的建议之显而易见(Obvious) Rust语言 - 接口设计的建议之不意外(unsurprising) Rust 实战:构建实用的 CLI 工具 HTTPie Rust编程语言学习之高级特性 Rust内存管理揭秘:深度剖析指针与智能指针 解决Rust中数组和切片的编译时大小问题 《Rust编程之道》学习笔记一 Rust Async 异步编程 简易教程 使用 Async Rust 构建简单的 P2P 节点 Rust编程语言入门之模式匹配 Rust async 编程 Rust编程语言之编写自动化测试 Rust编程语言之函数式语言特性:迭代器和闭包 《Rust编程之道》学习笔记二 Rust Tips 比较数值 使用 Rust 开发一个微型游戏 Rust编程初探:深入理解Struct结构体 深入理解Rust中的内存管理:栈、堆与静态内存详解 深入理解 Rust 结构体:经典结构体、元组结构体和单元结构体的实现 深入掌握 Rust 结构体:从模板到实例化的完整指南 深入理解Rust中的结构体:逻辑与数据结合的实战示例 深入理解 Rust 枚举:从基础到实践 掌握Rust字符串的精髓:String与&str的最佳实践 全面解析 Rust 模块系统:实战案例与应用技巧 Rust 中的 HashMap 实战指南:理解与优化技巧 掌握Rust模式匹配:从基础语法到实际应用 Rust 中的面向对象编程:特性与实现指南 深入理解 Rust 的 Pin 和 Unpin:理论与实践解析 Rust Trait 与 Go Interface:从设计到实战的深度对比 从零开始:用 Rust 和 Axum 打造高效 Web 应用 Rust 错误处理详解:掌握 anyhow、thiserror 和 snafu Rust 如何优雅实现冒泡排序 链表倒数 K 节点怎么删?Python/Go/Rust 实战 用 Rust 玩转数据存储:JSON 文件持久化实战 Rust实战:打造高效字符串分割函数 如何高效学习一门技术:从知到行的飞轮效应 Rust 编程入门:Struct 让代码更优雅 Rust 编程:零基础入门高性能开发 用 Rust 写个猜数游戏,编程小白也能上手! Rust 入门教程:变量到数据类型,轻松掌握! 深入浅出 Rust:函数、控制流与所有权核心特性解析 从零开始:用 Rust 和 Axum 打造高效 Web 服务 Rust 集合类型解析:Vector、String、HashMap 深入浅出Rust:泛型、Trait与生命周期的硬核指南 Rust实战:博物馆门票限流系统设计与实现 用 Rust 打造高性能图片处理服务器:从零开始实现类似 Thumbor 的功能 Rust 编程入门实战:从零开始抓取网页并转换为 Markdown 深入浅出 Rust:高效处理二进制数据的 Bytes 与 BytesMut 实战 Rust智能指针:解锁内存管理的进阶之道 用 Rust 打造命令行利器:从零到一实现 mini-grep 解锁Rust代码组织:轻松掌握Package、Crate与Module Rust 所有权:从内存管理到生产力释放 深入解析 Rust 的面向对象编程:特性、实现与设计模式 Rust + Protobuf:从零打造高效键值存储项目 bacon 点燃 Rust:比 cargo-watch 更爽的开发体验 用 Rust 打造微型游戏:从零开始的 Flappy Dragon 开发之旅 函数式编程的Rust之旅:闭包与迭代器的深入解析与实践 探索Rust编程之道:从设计哲学到内存安全的学习笔记 精读《Rust编程之道》:吃透语言精要,彻底搞懂所有权与借用 Rust 避坑指南:搞定数值比较,别再让 0.1 + 0.2 != 0.3 困扰你! 告别 Vec!掌握 Rust bytes 库,解锁零拷贝的真正威力 告别竞态条件:基于 Axum 和 Serde 的 Rust 并发状态管理最佳实践 Rust 异步编程实践:从 Tokio 基础到阻塞任务处理模式 Rust 网络编程实战:用 Tokio 手写一个迷你 TCP 反向代理 (minginx) 保姆级教程:Zsh + Oh My Zsh 终极配置,让你的 Ubuntu 终端效率倍增 不止于后端:Rust 在 Web 开发中的崛起之路 (2024数据解读) Rust核心利器:枚举(Enum)与模式匹配(Match),告别空指针,写出优雅健壮的代码 Rust 错误处理终极指南:从 panic! 到 Result 的优雅之道 想用 Rust 开发游戏?这份超详细的入门教程请收好! 用 Rust 实现 HTTPie:一个现代 CLI 工具的构建过程 Rust 异步实战:从0到1,用 Tokio 打造一个高性能并发聊天室 深入 Rust 核心:彻底搞懂指针、引用与智能指针 Rust 生产级后端实战:用 Axum + sqlx 打造高性能短链接服务 深入 Rust 内存模型:栈、堆、所有权与底层原理 Rust 核心概念解析:引用、借用与内部可变性 掌握 Rust 核心:生命周期与借用检查全解析 Rust 内存布局深度解析:从对齐、填充到 repr 属性 Rust Trait 分派机制:静态与动态的抉择与权衡 Rust Thread::Builder 用法详解:线程命名与栈大小设置 Rust 泛型 Trait:关联类型与泛型参数的核心区别 Rust Scoped Threads 实战:更安全、更简洁的并发编程 Rust 核心设计:孤儿规则与代码一致性解析 Rust 实战:从零构建一个多线程 Web 服务器 Rust Web 开发实战:构建教师管理 API 硬核实战:从零到一,用 Rust 和 Axum 构建高性能聊天服务后端 Rust Web 开发实战:使用 SQLx 连接 PostgreSQL 数据库 硬核入门:从零开始,用 Actix Web 构建你的第一个 Rust REST API (推荐 🔥) Rust 并发编程:详解线程间数据共享的几种核心方法 Rust并发安全基石:Mutex与RwLock深度解析 Rust Web实战:构建优雅的 Actix Web 统一错误处理 煮咖啡里的大学问:用 Rust Async/Await 告诉你如何边烧水边磨豆 深入浅出:Rust 原子类型与多线程编程实践 Rust 并发编程利器:OnceCell 与 OnceLock 深度解析 Rust 懒人编程:LazyCell 与 LazyLock 的惰性哲学 Rust 入门精髓:详解 Enum 的三种魔法,从模式匹配到状态管理 Rust 字符串魔法:String 与 &str 的深度解析与实践 Rust 模块化编程:驾驭代码结构与可见性的三大法则 Rust 实用进阶:深度剖析 Rust 生命周期的奥秘 Rust 智能指针大揭秘:Box、Rc、Arc、Cow 深度剖析与应用实践 Rust 并发编程三步曲:Join、Arc<Mutex> 与 mpsc 通道同步实战 Rust 声明宏实战进阶:从基础定义到 #[macro_export] 与多规则重载 Rust 类型转换实战:利用 From/Into Trait 实现带 Default 容错的安全转换 Rust 实战:实现 FromStr Trait,定制化字符串 parse() 与精确错误报告 Rust 实战:TryFrom Trait——如何在类型转换中强制执行业务逻辑检查 Rust 泛型编程基石:AsRef 和 AsMut 的核心作用与实战应用 揭秘 Rust Unsafe 编程:程序员接管内存安全的契约与实践 Rust FFI 入门:extern、ABI 与底层符号链接解析 Rust性能优化:零内存拷贝的链表合并技术实战 Rust 进阶:用 NonNull 裸指针实现高性能双向链表 O(N) 反转实战 Rust实战:如何用泛型和特性实现一个高性能、通用的插入排序

Rust实战:如何用泛型和特性实现一个高性能、通用的插入排序

Rust实战:如何用泛型和特性实现一个高性能、通用的插入排序你好,Rust开发者!虽然Rust的标准库已经内置了高性能的排序方法,但手写经典算法是理解Rust语言特性和掌握底层原理的最佳途径之一。今天,我们聚焦于最简单、最直观的排序算法之一——插入排序(InsertionSort)。

Rust实战:如何用泛型和特性实现一个高性能、通用的插入排序

你好,Rust 开发者!

虽然 Rust 的标准库已经内置了高性能的排序方法,但手写经典算法是理解 Rust 语言特性和掌握底层原理的最佳途径之一。今天,我们聚焦于最简单、最直观的排序算法之一——插入排序(Insertion Sort)

这段代码看似简单,却巧妙地利用了 Rust 的 泛型(Generics)特性(Traits) 机制,创建了一个通用且安全的排序函数。本文将带你一行行剖析这段代码:它如何在保证效率的同时,确保能对任何可比较的类型进行排序?它的内层循环是如何实现元素的“插入”?让我们一起揭开这段优雅 Rust 代码的内部工作机制。

实操

一个经典的插入排序(Insertion Sort) 算法

/*
    sort
*/

fn sort&lt;T: PartialOrd>(array: &mut [T]) {
    let n = array.len();
    // 插入排序:从第二个元素开始(索引 i=1)
    for i in 1..n {
        let mut j = i;
        // 将 array[i] 插入到已排序序列 array[0..i-1] 的正确位置
        // 循环条件:j 必须大于 0,并且前一个元素 array[j-1] 大于当前元素 array[j]
        while j > 0 && array[j - 1] > array[j] {
            // 如果前一个元素更大,就交换它们
            array.swap(j - 1, j);
            // 继续向左检查
            j -= 1;
        }
    }
}
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_sort_1() {
        let mut vec = vec![37, 73, 57, 75, 91, 19, 46, 64];
        sort(&mut vec);
        assert_eq!(vec, vec![19, 37, 46, 57, 64, 73, 75, 91]);
    }
    #[test]
    fn test_sort_2() {
        let mut vec = vec![1];
        sort(&mut vec);
        assert_eq!(vec, vec![1]);
    }
    #[test]
    fn test_sort_3() {
        let mut vec = vec![99, 88, 77, 66, 55, 44, 33, 22, 11];
        sort(&mut vec);
        assert_eq!(vec, vec![11, 22, 33, 44, 55, 66, 77, 88, 99]);
    }
}

💻 Rust 插入排序代码详解

这段代码定义了一个名为 sort 的泛型函数,用于对任何实现了偏序(PartialOrd 特性的数组进行原地排序。

sort 函数的核心逻辑是插入排序:

它从数组的第二个元素(索引 i = 1)开始,外层循环 (for i in 1..n) 依次取出当前未排序的元素。内层循环 (while j > 0 && array[j - 1] > array[j]) 负责将这个元素向左移动,插入到已排序序列(即它左边的部分)的正确位置。在内层循环中,只要当前元素 array[j] 小于其前一个元素 array[j-1],程序就会通过 array.swap(j - 1, j) 交换它们,并继续向左(即 j -= 1)检查,直到当前元素到达正确的位置(即它左边的元素不再比它大)。

通过这种方式,数组会从左到右逐步建立起一个有序的序列,直到整个数组排序完成。

泛型和约束:

函数签名 fn sort&lt;T: PartialOrd>(array: &mut [T]) 表明它可以接受任何类型 T 的切片(&mut [T],可变引用),但要求该类型 T 必须实现 PartialOrd 这个 Rust 特性,确保切片中的元素可以进行大小比较(如 > 运算符)。

测试用例 (#[cfg(test)]):

代码下方的 tests 模块提供了三个测试用例 (test_sort_1, test_sort_2, test_sort_3),分别验证了算法对乱序数组、单元素数组和逆序数组都能成功进行排序,保证了 sort 函数的健壮性。

总结

通过对这段插入排序代码的分析,我们不仅重温了经典的插入排序算法,更重要的是,我们看到了 Rust 语言的强大之处

  1. 泛型抽象: 通过 &lt;T: PartialOrd>,我们实现了类型无关的排序函数,无需关心数据是整数、浮点数还是其他可比较的对象。
  2. 特性约束(PartialOrd): 这是 Rust 安全性的体现。它强制要求传入的类型必须具备比较能力,从而避免了运行时的错误。
  3. 原地操作: 通过使用切片的可变引用 &mut [T]array.swap() 方法,我们在不创建额外内存副本的情况下完成了排序。
  4. 健壮性验证: 随代码提供的 #[test] 模块,展示了 Rust 社区推崇的测试驱动开发模式,确保算法在各种边缘情况(乱序、逆序、单元素)下都工作正常。

掌握这段代码,你便掌握了 Rust 算法实现中的核心设计模式

参考

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论