第 5 章　字符串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int N = a.length;
String[] aux = new String[N];
int[] count = new int[R+1];
// 计算出现频率
for (int i = 0; i < N; i++)
    count[a[i].key() + 1]++;
// 将频率转换为索引
for (int r = 0; r < R; r++)
    count[r+1] += count[r];//键的起始索引为所有较小键频率之和
// 将元素分类
for (int i = 0; i < N; i++)
    aux[count[a[i].key()]++] = a[i];//每个元素在 aux[] 中的位置是由它的键（组别）对应的 count[] 值决定，在移动之后将 count[] 中对应元素的值加 1，以保证 count[r] 总是下一个键为 r 的元素在 aux[] 中的索引位置
// 回写
for (int i = 0; i < N; i++)
    a[i] = aux[i];

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public class LSD{
    public static void sort(String[] a, int W){ // 通过前W个字符将a[]排序
        int N = a.length;
        int R = 256;
        String[] aux = new String[N];
        for (int d = W-1; d >= 0; d--){ // 根据第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];
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class MSD{
    private static int R = 256; // 基数
    private static final int M = 15; // 小数组的切换阈值
    private static String[] aux; // 数据分类的辅助数组
    private 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);
    }
    private static void sort(String[] a, int lo, int hi, int d){ // 以第d个字符为键将a[lo]至a[hi]排序
        if (hi <= lo + M){ Insertion.sort(a, lo, hi, d); 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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public class Quick3string{
    private static int charAt(String s,int d){
        if(d<s.length()) return s.charAt(d); else return -1;
    }
    public static void sort(String[] a){sort(a,0,a.length-1,0);}
    private static void sort(String[] a,int lo,int hi,int d){
        if(hi<=lo)return;
        int lt=lo,gt=hi;
        int v=charAt(a[lo],d);
        int i=lo+1;
        while(i<=gt){
            int t=charAt(a[i],d);
            if(t<v)exch(a,lt++,i++);
            else if(t>v)exch(a,i,gt--);
            else i++;
        }
        sort(a,lo,lt-1,d);
        if(v>=0)sort(a,lt,gt,d+1);
        sort(a,gt+1,hi,d);
    }
}