字符串排序算法
如果单个字符 可以使用计数排序。因为字符的范围有限。
如果是多个字符的字符串 且长度相同，可以使用基数排序 LSD 低位优先排序。
如果是多个字符的字符串 且长度不同，可以使用基数排序 MSD 高位优先排序。
JDK中字符串数组排序使用的是归并排序 ComparableTimSort 和 LegacyMergeSort（传统归并） 两种。具体使用的是String类的重写的compareTo方法进行比较。
比对每一位，如果相同比较长度
以上排序算法都在数字排序算法中说明，这里不再赘述。
这里详细说明一下，后缀排序法。
后缀排序法
当我们面对搜索、寻找文章中最长的重复词等需求时，可以用后缀排序法来高效解决。
从例子入手，假设有一段语句
itisabigappleitisa
我们把这段语句看成一个字符数组S[] 则S[0]=i,S[1]=t,S[2]=i,S[4]=s ......
然后把这段语句变成一个字符串数组。具体转换规则为：
A[0] = S[0]~S[16]组成，A[1] = S[1]~S[16]组成，A[2] = S[2]~S[16]组成。
A数组
然后使用MSD给这个字符串数组排序（其他算法也可以，只要排序了就ok），排序完成后，后缀排序法就结束了。
排序后的A数组
下面根据不同场景，进行不同操作。
寻找关键字
假设我们检索itis这个词，首先检索i A[6]~A[10] (下标从0开始)都符合，然后继续检索第二个t，然后检索第三个，第四个。全部检索完毕后，A[9]和A[10]满足条件。那么就有两个。并且A[9]字符串长度为5 那么在原字符数组中，开始的下标是倒数第五个。
寻找文章中最长的重复词
其实当我们后缀排序完后，重复词已经紧挨在一起了。
遍历排好序的A数组
A[0]和A[1] 找出重复词a,长度为1
A[1]和A[2] 同样是a
A[2]和A[3]，没有重复词；
直到A[9]和A[10] ，找到重复词为itisa 长度为5
对比方法也很简单：把两个词相同的位置进行逐一对比，一旦出现不相同。则对比结束。返回相同的字符串。
网友评论