各种字符串排序算法的性能特点 算法 是否稳定 原地排序 运行时间 额外空间 优势领域 字符串的插入排序 是 是 N到N*N之间 1 小数组或是已经有序的数组 快速排序 否 是 NlgN lgN 通用排序算法，特别适合于空间不足情况 归并排序 是 否 NlgN N 稳定的通用排序算法 三向快速排序 否 是 N到NlgN之间 lgN 大量重复键 低位优先的字符串排序 是 否 NW N 较短的定长字符串 高位优先的字符串排序 是 否 N到NW之间 N+WR 随机字符串 三向字符串快速排序 否 是 N到NW之间 W+lgN 通用排序算法，特别适合用于含有较长公共前缀的字符串 各种字符串查找算法的性能特点 算法 未命中查找检查的字符数量 内存使用 优点 二叉查找树（BST） c(lgN)**2 64N 适用于随机排列的键 2-3树查找（红黑树） c(lgN)**2 64N 有性能保证 线性探测法（并行数组） w 32N-128N 内置类型，缓存散列值 字典树查找（R向单词查找树） lgN (8R+56)N-(8R+56)Nw 适用于较短的键和较小的字母表 字典树查找（三向单词查找树） 1.39lgN 64N-64Nw 适用于非随机的键 各种字符串查找算法的实现的成本总结 算法 版本 最坏情况 一般情况 在文本中回退 正确性 额外的空间需求 暴力算法 - MN 1.1N 是 是 1 KMP 完整的DFA 2N 1.1N 否 是 MR KMP 仅构造不匹配的状态转换 3N 1.1N 否 是 M KMP 完整版本 3N N/M 是 是 R Boyer-Moore算法 启发式的查找不匹配的字符 MN N/M 是 是 R Rabin-Karp算法 蒙特卡洛 7N 7N 否 是 1 Rabin-Karp算法 拉斯维加斯 7N 7N 是 是 1