字符串排序算法
主要内容
假定给定一个字符串数字，要求将该字符串数组排序。
规定字符串中的字符全集基数为R，即字符串中的每个字符都是字母表中某一个字符，其索引为[0,R)。
键索引计数法
假定给定的字符串数组为单个字符数组，假定基数256即每个字符在字母表中的索引在0-255之间，类似于计数排序思想，使用count数组来统计字母表中每个字符出现的次数，将每个字符出现的次数进行加和，得到每个字符在字符总数中的索引，然后遍历待排序字符数组，找到每个字符所在的起始索引，将字符数组写入到aux临时数组中，然后将aux数组回写到a中，完成排序。
private static int R = 256; //基数
//键索引计数法
//排序小整数键
//假定待排序的字符串键值为0-R-1中的任意整数，每个字符串对应一个整数，现在按照字符串的键值来排序
//类似于计数排序
public static void keyIndexCount(char[] a){
int[] count = new int[R+1];
int N = a.length;
char[] aux = new char[N];
//count[0]=0 计算每个索引处字符串的个数
for(int i=0; i<N; i++){
count[a[i]+1]++;
}
//计算索引为r的字符串在全部数据中起始位置
for(int r=1; r<R+1; r++){
count[r] = count[r-1] + count[r];
}
//将字符串防止到aux合适位置中
for(int i=0; i<N; i++){
aux[count[a[i]]++] = a[i];
}
//将aux回写到a中 完成排序
for(int i=0; i<N; i++){
a[i] = aux[i];
}
}低位优先LSD
适用于长度相同的字符串数组进行排序。
从右往左依次进行比较，假定字符串程度为W，则从右往左进行W次键索引计数排序，最终得到有序的字符串数组。
//低位优先排序方式 从右往左开始依次利用键索引计数法来进行排序
//适用于所有字符串长度相等
public static void lsd(String[] ss){
int W = ss[0].length();
int N = ss.length;
String[] aux = new String[N];
System.out.println("origin = " + Arrays.toString(ss));
for(int i=W-1; i>=0; i--){
int[] count = new int[R+1];
for(int j=0; j<N; j++){
count[ss[j].charAt(i)+1]++;
}
for(int r=1; r<R+1; r++){
count[r] = count[r-1] + count[r];
}
for(int j=0; j<N; j++){
aux[count[ss[j].charAt(i)]++] = ss[j];
}
for(int j=0; j<N; j++){
ss[j] = aux[j];
}
System.out.println("i = " + i + " " + Arrays.toString(ss));
}
}高位优先MSD
高位优先提供对于变长字符串数组进行排序，从左边往右边进行比较，对于第一位首先使用键索引计数排序，将字符串数组按照第一位有序排列，由于第一位是有序的，因此按照第一位是否相同，可以划分为多个小数组，每个小数组第一位都是相同的，因此递归对于下一位进行排序，直到所有小数组都已有序。
由于字符串是变长的，长度不一，构造一个函数charAt（s,d）返回字符串s中索引d所在的索引位置，如果d大于字符串长度，则返回-1，将该值加一作为count数组索引，即此时count数组应该分配R+2个空间。
对于每一次递归调用都需要分配int[R+2]，当小数组较多时，会占用大量的空间，因此当数字较小时，不要再递归排序，而是改为插入排序，由于前d位此时已经相等，因此从字符串数组每个字符串的d位开始进行插入排序，比较规则使用String默认compareTo方法。
对于第d位键索引排序完毕后，按照第d+1位，此时会按照基数R来产生小数组递归调用，易得会产生大量的空数组；
当字符串数组相同或者有大量相同前缀时，此时递归深度与字符串长度相同，效率低下。
//高位优先 通用型排序
//大量小数组
//等值键 递归深度与键长度相同 效率低
//额外空间
public static void msd(String[] ss){
int N = ss.length;
aux = new String[N];
sort(ss, 0, N-1, 0);
}
//对于字符串数组从索引lo-hi利用字符串的第d位字符键值索引来排序
private static void sort(String[] ss, int lo, int hi, int d) {
//如果是小数组则执行插入排序
if(hi<=lo+M){
insertSort(ss, lo, hi, d);
return;
}
//利用第d位字符键索引排序
//由于每次递归调用都需要新建new int[R+2]，因此当切割成大量小数组时，耗费空间太大
//当字符串数组完全相同或者前缀相同太多时，该算法效率下降
int[] count = new int[R+2];
for(int i=lo; i<=hi; i++){
System.out.println(charAt(ss[i], d));
count[charAt(ss[i], d)+2]++;
}
for(int r=1; r<R+2; r++){
count[r] = count[r-1] + count[r];
}
for(int i=lo; i<=hi; i++){
aux[count[charAt(ss[i], d)+1]++] = ss[i];
}
for(int i=lo; i<=hi; i++){
ss[i] = aux[i-lo];
}
//对于第d+1位，根据分成的子数组进行递归排序
//这里会切分产生大量空数组
for(int i=0; i<R; i++){
sort(ss, lo+count[i], lo+count[i+1]-1, d+1);
}
}
//对于字符串数组从第d位开始插入排序
private static void insertSort(String[] ss, int lo, int hi, int d) {
for(int i=lo; i<=hi; i++){
for(int j=i; j>lo&&less(ss[j], ss[j-1], d); j--){
exch(ss, j, j-1);
}
}
}
private static void exch(String[] ss, int j, int i) {
String s = ss[i];
ss[i] = ss[j];
ss[j] = s;
}
private static boolean less(String s1, String s2, int d) {
return s1.substring(d).compareTo(s2.substring(d)) < 0;
}
//获取字符串s中第d位的索引，如果不存在则返回-1，然后将该值+1得到>=0值作为该字符在count数组中的索引
private static int charAt(String s, int d){
if(d<s.length())
return s.charAt(d);
return -1;
}三向字符串快速排序
由于MSD每次都会切换产生R个小数组，大量为空数组，切分效率不高，因此进行改进，使用三向字符串快速排序，即对于第d位比较，以第d位v作为基准，首先将字符串数组进行交换调整，分为三部分 小于v 等于v 大于v，即每次产生3向切分。
//三向字符串快速排序
public static void quick3String(String[] ss){
quick3Sort(ss, 0, ss.length-1, 0);
}
private static void quick3Sort(String[] ss, int lo, int hi, int d) {
if(hi<=lo) return;
int lt = lo;
int gt = hi;
int i = lo+1;
//以ss[lo]第d字符作为基准，将ss[lo,hi]进行交换调整，使得对于d位字符有ss[lo,lt-1]<v ss[lt,gt]=v ss[gt+1t,hi]>v
int v = charAt(ss[lo], d);
//System.out.println(lo + " " + hi);
while(i<=gt){
int t = charAt(ss[i], d);
if(t<v) exch(ss, lt++, i++);
else if(t>v) exch(ss, i, gt--);
else i++;
}
//对于小于v部分递归排序
quick3Sort(ss, lo, lt-1, d);
//对于等于v部分 由于第d位已经相等，从d+1位开始排序
if(v>=0)
quick3Sort(ss, lt, gt, d+1);
//对于大于v部分递归排序
quick3Sort(ss, gt+1, hi, d);
}字符串排序算法总结比较
参考 《算法第四版》