RustInPractice（26）：排序与字符串搜索
排序 demo 用 &mut [i32] 直接操作切片，搜索 demo 用字节序列实现朴素匹配与 KMP。它们适合理解复杂度，生产代码仍应优先标准库。
对应
sorting、string_search。下一篇：动态规划与系列收官。
冒泡和插入排序是 O(n²)，快速排序平均 O(n log n)，但最后元素 pivot 对已排序输入会退化并导致深递归。默认应使用 sort_unstable()，除非需要稳定排序。
KMP 的 LPS 表让失配后不必回退 haystack，因此复杂度为 O(m+n)。当前实现按 UTF-8 字节搜索，返回字节偏移；非 ASCII 文本不能把该值当字符索引或随意切片。
测试必须覆盖空 slice、单元素、重复值、空 pattern 和 Unicode 边界。
下一篇：动态规划与 RustInPractice 主线回顾。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 WALL-E's Blog！
相关推荐
2026-07-23
RustInPractice（27）：动态规划与系列回顾
动态规划把重叠子问题保存为状态表：先定义状态，再写转移，再决定初始化和遍历顺序。它也是 RustInPractice 主线的收官篇。 对应 dynamic_programming。TUI 番外将另行发布。 Fibonacci 只保留前两个状态，将空间从 O(n) 降至 O(1)。0/1 背包一维表必须逆序遍历容量，防止同一物品被重复选择。LCS demo 按 UTF-8 bytes 计算，非 ASCII 的“字符级 LCS”需要不同表示。 当前背包 demo 假设容量非负、weights/values 等长且权重有效；真实 API 应先验证这些输入，避免负数转 usize 或数组越界。 主线至此完成：基础与 Cargo，所有权类型系统，工程并发，最后落到服务、存储和算法。下一步可以继续 TUI 番外，或以一个带测试、配置、数据库和 HTTP 的 capstone 收束实践。 RustInPractice 主线第 27 篇完结。
2026-07-06
现代 C++ 实战（23）：字符串搜索与动态规划
第 22 篇 的图算法处理「关系」；本篇进入算法面试的两大支柱：字符串搜索（在文本中找模式）和动态规划（把大问题拆成重叠子问题）。KMP 和 Boyer-Moore 解决搜索，背包和 LCS 解决 DP——掌握这些，LeetCode 中等题大半有思路。 demo：ref/cpp_demo/algorithms/string_search/ + ref/cpp_demo/algorithms/dynamic_programming/。 这是「现代 C++ 实战」系列的第 23 篇。建议先读 第 22 篇：图算法。 一、字符串搜索全景在文本 text（长度 n）中查找模式 pattern（长度 m）： 算法 时间 思路 适用 暴力 O(nm) 每个位置逐字符比 短模式、教学 KMP O(n+m) 前缀函数，失配不回退 text 通用、面试必考 Boyer-Moore 最好 O(n/m) 从右向左，坏字符跳跃 长模式、实际文本搜索 Rabin-Karp 平均 O(n+m) 滚动哈希，先比哈希再验证 多模式匹配 1234text: A ...
2026-07-01
现代 C++ 实战（18）：排序算法与 std::sort
第二季讲完语言与工程，第三季进入算法与数据结构。排序是第一课：手写七种经典算法理解原理，再和 std::sort 做性能对比——感受工业级实现为何快一个数量级。 demo：ref/cpp_demo/algorithms/sorting/（含 7 种手写排序 + benchmark）。 这是「现代 C++ 实战」系列的第 18 篇，第三季开篇。建议先读 第 17 篇：C++23 新特性。 一、排序算法全景 算法 平均时间 最坏 空间 稳定 比较？ 冒泡 O(n²) O(n²) O(1) ✅ 是 选择 O(n²) O(n²) O(1) ❌ 是 插入 O(n²) O(n²) O(1) ✅ 是 归并 O(n log n) O(n log n) O(n) ✅ 是 快速 O(n log n) O(n²) O(log n) ❌ 是 堆 O(n log n) O(n log n) O(1) ❌ 是 计数 O(n + k) O(n + k) O(n + k) ✅ 否 std::sort O(n log n) — O(log n) ❌ 是（IntroSo...
2026-07-23
RustInPractice（24）：SQLite 与 rusqlite
rusqlite 用 Rust 类型包装 SQLite 的连接、参数绑定、查询和事务。核心规则是：SQL 值永远通过参数绑定传递，不用字符串拼接。 对应 database/sqlite3。下一篇：数据结构。 1234conn.execute( "INSERT INTO students (class_id, name, score) VALUES (?1, ?2, ?3)", params![1, name, score],)?; query_map 将行映射为 struct，? 将数据库失败传播到调用边界。事务应使用 checked transaction，并同时演示 commit 与 rollback；当前 demo 使用内存数据库和 unchecked_transaction()，只适合作为 API 导览。 真实项目还应启用 foreign keys、维护 migration、测试约束、使用持久路径，并决定连接是否只能在同步线程中使用。 下一篇：数据结构在 Rust 中的所有权边界。
2026-07-09
现代 C++ 实战（26）：LRU 缓存与 JSON 解析器
第 25 篇 给服务加了持久化；本篇是两个经典练手项目：LRU 缓存练数据结构设计，JSON 解析器练递归下降与 std::variant——都是面试高频、又能深入理解 C++ 现代特性。 demo：ref/cpp_demo/projects/learning_guide/（lru_cache/ + json_parser/）。 这是「现代 C++ 实战」系列的第 26 篇。建议先读 第 20 篇：栈、队列与链表（LRU 底层）和 第 24 篇：HTTP 服务与 JSON（nlohmann/json）。 一、LRU 缓存：设计思路LRU（Least Recently Used）——缓存满时淘汰最久未使用的项。要求 get 和 put 均 O(1)。 123456unordered_map<K, iterator> list<pair<K,V>>┌─────────────────┐ ┌──────────────────────┐│ key1 → iter1 ───┼─────────>│ (k...
2026-07-21
RustInPractice（14）：泛型、Trait 与静态/动态分发
Rust 不以 class 继承为核心。它把数据放进 struct 或 enum，把可替换行为写成 trait，再根据场景选择泛型的静态分发或 trait object 的动态分发。结果是组合关系清楚，抽象成本也更可见。 这是 RustInPractice 第二季收官篇。对应 demo：oop_demo、pimpl_demo、design_patterns。下一季进入集合、测试与并发工程实践。 一、泛型消除重复123fn swap<T, U>(pair: (T, U)) -> (U, T) { (pair.1, pair.0)} T、U 是类型参数。编译器会为实际使用的具体类型生成对应实现，这通常称为单态化。泛型函数不必事先知道具体类型，只需声明它需要的能力。 二、trait 定义能力而非继承层级1234567891011trait Compress { fn compress(&self, data: &str) -> String;}struct Plain;impl Com...
