加密算法、排序算法、字符串处理及搜索算法详解

一、加密算法

1. 加密算法分类及常见类型：加密算法主要分为对称加密、非对称加密、哈希摘要、电子签名和密码存储几类。对称加密有 DES、AES（国家标准 SM4）；非对称加密有 RSA、ECDSA（国家标准 SM2）；哈希摘要有 MD5、SHA-2、SHA-3（国家标准 SM3）；电子签名常结合 RSA、ECDSA 和哈希摘要，或用 HMAC；密码存储可采用哈希摘要加盐、多次迭代哈希、BCrypt 等。
   
2. 对称加密、非对称加密、哈希摘要的区别：

• 对称加密：加密和解密用同一个密钥，需妥善保管，加解密速度快。
• 非对称加密：密钥分公钥（加密）和私钥（解密），私钥保管，公钥可公开；双向通信需双方各有一对密钥（用对方公钥加密，自己私钥解密），加解密速度较慢。
• 哈希摘要：提取原始数据特征，可用于完整性校验（如不同数据的摘要不同），比如用 “张三，男，30 岁” 等特征描述张三，特征不符则数据不同。

3. 签名算法：电子签名用于防止数据篡改。单纯摘要易被篡改（坏人可重新计算摘要），解决方法是发送者用自己的私钥对摘要签名，接收者用发送者的公钥验签。验签和加密用对方公钥，签名和解密用自己私钥，确保只有发送者能签名，接收者可验证。
   
4. 项目中密码存储方式：明文和单纯 MD5、SHA-2 存储不可行（简单密码易被彩虹表攻击）。通常采用：提示用户设置强密码；或对简单密码加盐（增加复杂度）、多次迭代哈希，或用 BCrypt（自动加盐和多次哈希），增加破解难度。
   

二、排序算法

1. 排序算法分类及特点：排序算法分基于比较的排序（如快排、归并、堆排序、插入排序等）和非比较排序（如计数、桶、基数排序）。比较排序中，快排、归并、堆排序平均时间复杂度为 O (n・log n)，插入排序在数据量小或有序度高时适用；非比较排序（计数、桶、基数）可达到 O (n)，但受数据范围、位数影响。工业级排序多为混合算法（如 Java 的排序结合插入、归并、快排）。
   
2. 常见排序算法的时间复杂度及特性：

• 比较排序：冒泡、选择、插入排序平均 O (n²)；归并、快排、堆排序平均 O (n・log n)。其中，冒泡、插入稳定，选择、快排、堆排序不稳定；归并空间复杂度 O (n)，快排递归栈空间 O (log n)。
• 非比较排序：计数排序 O (n+r)（r 为数据范围），桶排序 O (n)（桶数接近 n 时），基数排序 O (n・w)（w 为数字位数）。

3. 具体排序算法实现思路：

• 冒泡排序：分已排序和未排序区，每轮从左到右比较相邻元素，逆序则交换，最大元素移至已排序区，优化可记录最后交换位置减少轮数。
• 选择排序：分已排序和未排序区，每轮选未排序区最大元素交换至已排序区，交换次数少但不稳定。
• 插入排序：分已排序和未排序区，每次取未排序区最左元素，与已排序区元素从右向左比较，插入合适位置，适合小数据或有序数据。
• 归并排序：分治思想，将数组不断二分至小数组，排序后两两合并，稳定且时间复杂度稳定 O (n・log n)。
• 快速排序：分治思想，选基准点，将比基准点小的放左、大的放右，递归分区，平均效率高但分区不均时退化至 O (n²)。
• 堆排序：建大顶堆，将堆顶（最大元素）交换至数组尾部，调整堆后重复，时间复杂度 O (n・log n)，但可能因缓存未命中影响效率。

三、字符串类

1. 字符串反转：基于双指针，i 指向起始，j 指向结束，交换 i、j 元素后 i 后移、j 前移，直至相遇（如 LeetCode 344 题），可扩展至反转单词（LeetCode 151 题）。
   
2. 项目中字符串匹配技术的应用：常用正则表达式，如：

• 表单校验：手机号校验用/^1\d{10}$/（1 开头，后 10 位数字）。
• 网页爬取：提取图片链接，正则/<img src=(['"])(.+?)\1(.*?)>/g匹配 src 属性值。
• 日志处理：提取请求方法日志处理：提取请求方法、路径等，正则/\[.*?\] - (\w+) (\/\S+) (\d{3}) (\w+)/g分组匹配。

四、搜索类

1. 二分查找：在有序数组中，用双指针 i（起始）、j（结束），计算中间索引 m，比较目标与 a [m]，调整 i 或 j，直至找到目标（时间复杂度 O (log n)）。
   
2. 回溯算法：记录每步状态，尝试失败时回溯至之前状态换方法尝试，常结合递归（递归