对字符串的排序可以使用前面的通用排序算法,但有些专用的字符串排序算法将比通用排序算法效率更高,它们突破了NlogN的时间下界。
算法
是否稳定
原地排序
运行时间
额外空间
优势领域
低位优先的字符串排序
是
否
NW
N
较短的定长字符串
高位优先的字符串排序
N到Nw之间
N+WR
随机字符串
三向字符串快速排序
W+logN
通用排序算法,特别适用于 含有较长公共前缀的字符串
字母表的长度为R,字符串的长度为N,字符串平均长度为w,最大长度为W。