5.1 字符串排序
Robert Sedgewick Kevin Wayne
对于许多排序应用,决定顺序的键都是字符串。本节中,我们将会考察能够利用字符串的特殊性质将字符串键排序的方法,它们将比第 2 章学过的通用排序方法效率更高。
我们将学习两类完全不同的字符串排序方法。它们都是为程序员服务了几十年的强大方法。
第一类方法会从右到左检查键中的字符。这种方法一般被称为低位优先(Least-Significant-Digit First,LSD)的字符串排序。使用数字(digit)代替字符(character)的原因要追溯到相同方法在各种数字类型中的应用。如果将一个字符串看作一个 256 进制的数字,那么从右向左检查字符串就等价于先检查数字的最低位。这种方法最适合用于键的长度都相同的字符串排序应用。
第二类方法会从左到右检查键中的字符,首先查看的是最高位的字符。这些方法通常称为高位优先(MSD)的字符串排序——本节将会学习两种此类算法。高位优先的字符串排序的吸引人之处在于,它们不一定需要检查所有的输入就能够完成排序。高位优先的字符串排序和快速排序类似,因为它们都会将需要排序的数组切分为独立的部分并递归地用相同的方法处理子数组来完成排序。它们的区别之处在于高位优先的字符串排序算法在切分时仅使用键的第一个字符,而快速排序的比较则会涉及键的全部。要学习的第一种方法会为每个字符创建一个切分,第二种方法则总会产生三个切分,分别对应被搜索键的第一个字符小于、等于或大于切分键的第一个字符的情况。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入介绍了字符串排序的两种不同方法:低位优先(LSD)的字符串排序和高位优先(MSD)的字符串排序。通过对这两种方法的详细讨论,读者可以快速了解它们的适用场景和特点。此外,文章还介绍了适用于小整数键的简单排序方法——键索引计数法,以及该方法的四个步骤:频率统计、将频率转换为索引、数据分类和回写。在分析字符串排序算法时,文章还讨论了字母表的大小对算法的影响,包括基于扩展的 ASCII 字符集的字符串、较小字母表的字符串(例如基因序列)和较大字母表的字符串(例如含有 65 536 个字符的 Unicode 字母表)。此外,文章还介绍了高位优先的字符串排序算法在处理长字符串时可能面临的挑战,以及针对这些挑战的改进算法。通过对高位优先的字符串排序算法的性能和特点进行深入讨论,读者可以更好地理解其在实际应用中的优势和局限性。整体而言,本文内容涵盖了基本的字符串排序算法和相关概念,对于对算法感兴趣的读者具有一定的参考价值。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
《算法(第 4 版)》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论