最近有点空闲时间了，在啃 Sedgwick 的 Algorithm 这本经典算法书，前面的以前就会，最后一张字符串相关算法之前没接触过，特此整理笔记。跟随书籍，语言使用Java。
导图笔记
一、键索引计数法
在一般排序中，都要用里面的元素不断比较，而字符串这玩意儿大可不必比较，有另外一种思想。在键索引计数法中，可以突破NlongN的排序算法运行时间下限，它的时间级别是线性的！
引入字母表概念：
想要不对字符串里面的字符进行对比，我们需要引入字母表的概念，比如将‘a’看作1，‘b’看作2，‘c’看作3，这样下去，26个字母只需要一个长度为27的数组就能够表示（下标为0不用），而且按数字来看他们是有序的（从a到z对应1到26）。
所以“abcdefg..”这些字符转换为整型时（使用charAt（）函数），自然有一个对应的顺序，所以我们只需要找到一个合适大小的数组来保存每个将会用到的字符的信息即可。现在我们创建count[]数组，大小为256，用来保存对应字符出现的频率和排序时的索引。
键索引计数法共分为四步，下面进行说明并举例。(用R来表示字符的种类，r表示字符在R中的顺序）
1、计算频率:
for(int i=0;i<N;i++){//计算频率
count[a[i].charAt(d)+1]++;
}
遍历所有字符串，d为字符串的第d个字符（下面例子中字符串都为单个数字）。
出现什么字符，我们就将对应的count[r+1]加一（里面为什么是r+1，看到下一步你自然会明白）。
2、计算索引:
for(int r=0;r<R;r++){//将频率转换为索引
count[r+1]+=count[r];
}
需要在我们计算出频率的基础上进行:count[r+1]+=count[r]
将count数组中后一位总是加上前一位。
3、数据分类
for(int i=0;i<N;i++){//数据分类
aux[count[a[i].charAt(d)]++]=a[I];
}
进行数据分类我们需要一个辅助数组aux，用来暂时储存排序的数据。
把数据放入辅助字符串数组，全部放入时已经形成有序。
4、回写
for(int i=0;i<N;i++){//回写
a[i]=aux[i];
}
到此为止键索引计数法就完成了，接下来利用它来实现LSD/MSD。
二、低位优先排序（LSD）
第位优先排序与高位优先排序的主要区别在于排序的方向，核心思想算法都是通过键索引计数法。低位优先算法是从字符串的右到左来排序（这可能会出现一些问题，在高位优先排序的介绍中将会提到）。
下图为一个地位优先排序的完整过程：
image.png
for (int d=W-1;d>=0;d--){//从右到左对所有字符串的每位判断
int count[]=new int[R+1];
for(int i=0;i<N;i++){//计算频率
count[a[i].charAt(d)+1]++;
}
for(int r=0;r<R;r++){//将频率转换为索引
count[r+1]+=count[r];
}
for(int i=0;i<N;i++){//排序
aux[count[a[i].charAt(d)]++]=a[I];
}
for(int i=0;i<N;i++){//回写
a[i]=aux[i];
}
}
三、高位优先排序（MSD）
在低位优先排序中，可能会出现一点问题。比如字符串“ab”与“ba”，长度为2需要进行两次排序，第一次排序结果为“ba”、“ab”，第二次排序结果为“ab”、“ba”，第一次排序的结果对第二次毫无意义，这就造成了时间上的浪费。
而在高位优先排序中，只会进行一次排序。结果为“ab”、“ba”。
不同之处：
在高位排序中又引入了分组的概念，即用首字母来切分下一个排序组。
image.png
public static void sort(String[] a,int lo,int hi,int d){
if(lo>=hi){
return;
}
int[] count=new int[R+2];
for(int i=lo;i<=hi;i++){
count[charAt(a[i],d)+2]++;
}
for(int r=0;r<R+1;r++){
count[r+1]+=count[r];
}
for(int i=0;i<=hi;i++){
aux[count[charAt(a[i],d)+1]++]=a[I];
}
for(int i=0;i<=hi;i++){
a[i]=aux[i];
}
for(int r=0;r<R;r++){
sort(a,lo+count[r],lo+count[r+1]-1,d+1);
}
}
上面这段代码非常简洁，但其中有一些地方是复杂的，请研究下面例子的调用过程确保你理解了算法。
sort（a,0,9,0）的顶层调用
四、完整代码
public class LSD {
public static void sort(String[] a,int W){//W表示字符串的长度
int N=a.length;
int R=256;//依字符的种类数目而定
String aux[]=new String[N];
for (int d=W-1;d>=0;d--){//从右到左对所有字符串的每位判断
int count[]=new int[R+1];
for(int i=0;i<N;i++){//计算频率
count[a[i].charAt(d)+1]++;
}
for(int r=0;r<R;r++){//将频率转换为索引
count[r+1]+=count[r];
}
for(int i=0;i<N;i++){//排序
aux[count[a[i].charAt(d)]++]=a[I];
}
for(int i=0;i<N;i++){//回写
a[i]=aux[i];
}
}
}
}
public class 马上到！ {
private static int R=256;
private static String[] aux;
public static int charAt(String s,int d){
if(d<s.length()){
return s.charAt(d);
}else{
return -1;
}
}
public static void sort(String[] a){
int N=a.length;
aux=new String[N];
sort(a,0,N-1,0);
}
public static void sort(String[] a,int lo,int hi,int d){
if(lo>=hi){
return;
}
int[] count=new int[R+2];
for(int i=lo;i<=hi;i++){
count[charAt(a[i],d)+2]++;
}
for(int r=0;r<R+1;r++){
count[r+1]+=count[r];
}
for(int i=lo;i<=hi;i++){
aux[count[charAt(a[i],d)+1]++]=a[I];
}
for(int i=lo;i<=hi;i++){
a[i]=aux[i - lo];
}
for(int r=0;r<R;r++){
sort(a,lo+count[r],lo+count[r+1]-1,d+1);
}
}
}
）
网友评论