字符串排序（一）

键索引计数法
键索引计数法是一种适用于整数键的简单排序方法。为了说明这种方法，假设数组a[]中的每个元素都保存了一个名字和一个键值，其中键值在0~R-1之间，代码a[i].key()会返回指定的键值。方法可简单分为4个步骤：
1.频率统计
第一步通过int数组count[]计算每个键出现的频率。对于数组中的每个元素，都使用它的键访问count[]中的相应元素并将其加1.如果键为r，则将count[r+1]加1.

for(i=0; i<N; i++)
    count[a[i].key() + 1]++;

2.将频率转换为索引
使用count[]来计算每个键在排序结果中的起始索引位置。一般来说，任意给定的键的起始索引均为所有较小的键的对应的频率之和。对于每个键值r，小于r+1的键的频率之和为小于r的频率之和再加上count[r]。

for(int r=0; r<R; r++)
    count[r+1] += count[r];

3.在将count[]数组转换为一张索引表之后，将所有的元素移动到一个辅助数组aux[]中以进行排序。每个元素在aux[]中的位置由它的键的count[]值决定，在移动之和将count中对应的元素加1，以保证count[r]总是下一个键r的元素在aux中的索引。

for( int i=0; i<N; i++)
    aux[count[a[i].key()]++] = a[i];

4.回写
我们在将元素移动到辅助数组的过程中完成了排序，所以最后一步就是将排序的结果复制回原数组中。

键值索引法排序N个键为0到R-1之间的整数的元素需要访问数组11N+4R+1次。

低位优先的字符串排序
如果字符串的长度均为W，那就从右向左以每个位置的字符作为键，用建索引计数的方法将字符串排序W遍。

public class LSD{
    public static void sort(String[] a, int 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];
        }
    }
}

对于基于R个字符的字母表的N个以长为W的字符串为键的元素，低位优先的字符串排序需要访问~7WN+3WR次数组，使用的e'a