字符串排序----高位优先的字符串排序
高位优先字符串排序是一种递归算法，它从左到右遍历字符串的字符进行排序。和快速排序一样，高位优先字符串排序算法会将数组切分为能够独立进行排序的子数组进行排序，但它的切分会为每个首字母得到一个子数组，而非像快排那样产生固定的两个或三个数组。
本算法也是基于键索引记数法来实现的。该算法的核心思想是先使用键索引记数法根据首字符划分成不同的子数组，然后递归地处理子数组，用下一个字符作为键索引记数法的键处理子数组。
因为是不同长度的字符串，所以要关注字符串末尾的处理情况。合理的做法是将所有字符都已经被检查过的字符串所在的数组排在所有子数组的前面，这样就不需要递归地将该数组排序。
使用一个接收两个参数的方法chatAt()来替换系统的chatAt()（将字符串中的字符索引转换为数组索引），当指定的位置超出字符串的长度，则返回-1，其他情况返回指定索引处的字符。因为数组下标非负，所以需要将所有返回值+1得到非负int值作为count[]的下标。这种转换意味着字符串中每个字符都有可能产生R+1个不同的值：0表示字符串末尾，1表示字符串第一个字符，2表示字符串第二个字符......由于键索引记数法本来就需要一个额外的位置，所以count[]数组应该定义为new intR+2。
知道了算法的核心思想，理解下面的算法代码不难，它相对于低位优先算法改动和增加的代码并不多。增加了一个条件语句方便在子数组规模较小时切换为插入排序（提高效率），最后增加了一个循环完成递归调用。
public class MSD {
private static int R = 256; //字符串中最多可能出现的字符的数量
private static final int M = 15; //当子字符串长度小于M时，用直接插入排序
private static String[] aux; //辅助数组
//实现自己的chatAt()方法
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) {
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[a[i].charAt(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、额外空间
高位优先算法使用了两个辅助数组。aux[]的大小为N可以在sort()方法外创建，如果牺牲稳定性，则可以去掉aux[]数组。但count[]所需要的空间才是最需要关注的（因为它无法在sort()外创建）。
要将基于R个字母表的N个字符串排序，平均需要检查N(logR)N个字符。