[Java]-字符串，字符串排序（MSD,LSD） 字符串
字符串处理算法在多个领域展现出其多样性与重要性。
– 信息处理：诸如根据给定关键字搜索⽹页等。
– 基因组学：根据密码⼦将DNA碱基转换为字符串并进⾏⽣物学研究
– 通信系统：短信，电⼦邮件的发送或者电⼦书下载，本质都是字符串的传送
– 编程系统：程序由字符串组成，编译器，解释器等都是通过强⼤复杂的字符串算法将它们转换为机器语⾔的
⼀些应⽤程序可能会对字符串的字母表(包含所有字符串的字符集)做出限制，这时我们就可能需要更换字母表或⾃定义字母表
⾃定义的字母表在功能上可能不能达到尽善尽美，但以其短⼩且适应问题⽽具有研究价值，如果⼀个问
题只需要四个字符组成的字母表，这时候再采⽤系统内置的标准字母表就显得得不偿失
字母表API
返回值函数名作⽤
构造⽅法Alphabet(String s)根据s中的字符创建⼀张新的字母表
char toChar(int index)获取字母表中索引位置的字符
int toIndex(char c)获取c的索引，在0-(R-1)之间
boolean contains(char c)c是否在字母表中
int R()基数（字母表中的字符数量）
int lgR()表⽰⼀个索引所需的⽐特数
水库网int[]toIndices(String s)将s转换为R进制整数
String toChars(int[] indices)将R进制整数转换为基于该字母表的字符串
代码实现：
package cn.ywrby.MyString;
import edu.princeton.cs.algs4.StdOut;
public class Alphabet {
/*
* 定义标准字母表
* */
//The binary alphabet { 0, 1 }. 01字符集
public static final Alphabet BINARY = new Alphabet("01");
//The octal alphabet { 0, 1, 2, 3, 4, 5, 6, 7 }. ⼋进制字符集
public static final Alphabet OCTAL = new Alphabet("01234567");
/
/The decimal alphabet { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }. ⼩数集
public static final Alphabet DECIMAL = new Alphabet("0123456789");
//The hexadecimal alphabet { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }. ⼗六进制字符集
public static final Alphabet HEXADECIMAL = new Alphabet("0123456789ABCDEF");
//The DNA alphabet { A, C, T, G }. DNA字符集
public static final Alphabet DNA = new Alphabet("ACGT");
//The lowercase alphabet { a, b, c, ..., z }. ⼩写字母字符集
public static final Alphabet LOWERCASE = new Alphabet("abcdefghijklmnopqrstuvwxyz");
//The uppercase alphabet { A, B, C, ..., Z }. ⼤写字母字符集
public static final Alphabet UPPERCASE = new Alphabet("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
蛋白质晶体//The protein alphabet { A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, Y }. 蛋⽩质字符集
public static final Alphabet PROTEIN = new Alphabet("ACDEFGHIKLMNPQRSTVWY");
//The base-64 alphabet (64 characters). base-64字符集
public static final Alphabet BASE64 = new Alphabet("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"); //The ASCII alphabet (0-127). ASCII码字符集
public static final Alphabet ASCII = new Alphabet(128);
//The extended ASCII alphabet (0-255). 扩展ASCII码字符集
public static final Alphabet EXTENDED_ASCII = new Alphabet(256);
//The Unicode 16 alphabet (0-65,535). Unicode16字符集
public static final Alphabet UNICODE16 = new Alphabet(65536);
private char[] alphabet; //⽤字符数组存储字母表 private int[] inverse; //存储字符的索引值的整数数组(利⽤字符获得字符的索引值)
private int R; //字母表⼤⼩
//构造函数(利⽤字符串)
public Alphabet(String alpha){
新华门事件
boolean[] unicode=new boolean[Character.MAX_VALUE];
for(int i=0;i<alpha.length();i++){
char c=alpha.charAt(i);
//避免重复字符
if(unicode[c]){
throw new IllegalArgumentException("Illegal alphabet: repeated character = '" + c + "'");
}
unicode[c]=true;春暖花开 亚洲
}
CharArray(); //将字符串转换为字符型数组并⽤作字母表
R=alpha.length();
inverse=new int[Character.MAX_VALUE];
//将索引值各项初始化为-1，然后再单独修改使⽤到的字符
//这样返回值为-1就表⽰该字符不在字母表中
for(int i=0;i<inverse.length;i++){
inverse[i]=-1;
}
for(int i=0;i<R;i++){
inverse[alphabet[i]]=i;
}
}
//构造函数(利⽤整数)
public Alphabet(int radix){
this.R=radix;
alphabet=new char[R];
inverse=new int[R];
for(int i=0;i<R;i++){
alphabet[i]=(char)i;
}
for(int i=0;i<R;i++){
inverse[i]=i;
}
}
//默认构造
public Alphabet(){this(256);}
//字符c是否存在字母表中
public boolean contains(char c){ return inverse[c]!=-1; }
//字母表⼤⼩
public int R(){return R;}
//⼀个索引所需的⽐特数
public int lgR(){
int lgR=0;
for(int t=R-1;t>=1;t/=2){
lgR++;
}
return lgR;
}
//获取字符的索引
public int toIndex(char c){
if(c>=inverse.length||inverse[c]==-1){
throw new IllegalArgumentException("Character " + c + " not in alphabet");
}
return inverse[c];
}
//将s转换为R进制整数
public int[] toIndices(String s){
char[] CharArray();
int[] target=new int[s.length()];
for(int i=0;i<s.length();i++){
target[i]=toIndex(source[i]);
}
return target;
}
/
/将R进制整数转换为字符
public char toChar(int index){
if(index>=R||index<0){
throw new IllegalArgumentException("index must be between 0 and " + R + ": " + index); }
return alphabet[index];
}
//将R进制整数数组转换为字符串
public String toChars(int[] indices){
StringBuilder s=new StringBuilder(indices.length);
for(int i=0;i<indices.length;i++){
s.append(toChar(indices[i]));
}
String();
}
public static void main(String[] args) {
int[] encoded1 = Indices("NowIsTheTimeForAllGoodMen");
String decoded1 = Chars(encoded1);
StdOut.println(decoded1);
int[] encoded2 = Indices("AACGAACGGTTTACCCCG");
String decoded2 = Chars(encoded2);
StdOut.println(decoded2);
int[] encoded3 = Indices("01234567890123456789");
String decoded3 = Chars(encoded3);
StdOut.println(decoded3);
}
}
字符串排序
键索引计数法
⼀种适⽤于⼩整数键的简单排序算法，这个算法依托于每个字符串对应于⼀个键，这个键是⼀个编号较⼩的整数。
整个算法在排序前是有序的，算法实现的是将各个字符串按键的顺序重新排列(不改变相同键形成的⼩组内部字符串仍然是相对有序的)
具体应⽤场景类似于学⽣统计问题，学⽣被分成若⼲⼩组(组号就是每个⼈的键值)，每组⼈数不定，现在⽼师⼿⾥有按照姓名排序(字符串有序)的表格，现在要将表格按照⼩组顺序重新排列，并且排列后⼩组内部姓名仍然是有序的(不改变相同键形成⼩组内部字符串相对有序)
算法执⾏过程：
通过⼀次遍历，统计各个键的频率(利⽤int[] count保存，如果访问键r则将count[r+1]加1(这样可以⽅便后续计算，并轻松的将频率转换为各组的起始索引))。
将频率转换为索引，上⼀步统计了各个⼩组的⼈数，所以只需逐项增加前⼀项⼤⼩就可以得到该组的起始索引位置（例如：第1组是第1项，由于0项=0，所以0+0=0，起始索引为0，第2组是第2项，0+count[2]=count[2]就是第⼆组的索引起始位置，以此类推得到各项的起始索引）
数据分类，创建辅助数组，然后遍历原数组，按照数组键值以及count数组提供的索引位置写⼊新数组（由于之前的字符串是有序的，所以遍历并将数据写⼊新数组的过程中没有打乱⼩组内部的有序性），每次写⼊后都要对count数组对应项+1，保证指向⼩组内下⼀个索引位置
回写数据，将排序后的数据再次遍历写⼊原数组中
简单代码实现
package cn.ywrby.MyString.KeyIndexCounting;
public class Student {
private String name; //姓名
private int group; //所在⼩组
public Student(String name,int group){
this.name=name;
}
public int group(){return group;}
}
package cn.ywrby.MyString.KeyIndexCounting;
import edu.princeton.cs.algs4.In;
//键索引计数法
public class KeyIndexCount {
public static void main(String[] args) {
Student[] stu=new Student[60];
int N=stu.length;
int[] count=new int[N];
int R=256;
Student[] aux=new Student[N];
/*
* 通过⼀次遍历，统计各个键的频率(利⽤int[] count保存，
* 如果访问键r则将count[r+1]加1(这样可以⽅便后续计算，
* 并轻松的将频率转换为各组的起始索引))。开明国语课本 pdf
* */
for(int i=0;i<N;i++){
count[stu[i].group()+1]+=1;
}
/*
* 将频率转换为索引，上⼀步统计了各个⼩组的⼈数，
* 所以只需逐项增加前⼀项⼤⼩就可以得到该组的起始索引位置
* （例如：第1组是第1项，由于0项=0，所以0+0=0，起始索引为0，
* 第2组是第2项，0+count[2]=count[2]就是第⼆组的索引起始位置，以此类推得到各项的起始索引）
* */
for(int r=0;r<R;r++){
count[r+1]+=count[r];
}
/*
支付体系春节大考* 数据分类，创建辅助数组，然后遍历原数组，
* 按照数组键值以及count数组提供的索引位置写⼊新数组
* （由于之前的字符串是有序的，所以遍历并将数据写⼊新数组的过程中没有打乱⼩组内部的有序性），
* 每次写⼊后都要对count数组对应项+1，保证指向⼩组内下⼀个索引位置
* */
for(int i=0;i<N;i++){
aux[count[stu[i].group()+1]++]=stu[i];
}
//回写数据，将排序后的数据再次遍历写⼊原数组中
for(int i=0;i<N;i++){
stu[i]=aux[i];
}
}
}
键索引计数法排序N个键为0-(R-1)之间的元素需要访问整个数组11N+4R+1次(突破了排序算法NlgN时间的下限，因为并不是通过⽐较进⾏排序的，⽽是利⽤键值进⾏排序)
低位优先的字符串排序(LSD)
低位优先的字符串排序适⽤于那些长度相同的字符串组进⾏排序
排序的过程
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议