字符串排序有很多应用，比如车牌的排序，基因编码等。今天介绍一种低位优先的字符串排序算法，在介绍它之前先介绍另一种算法--键索引计数法，它是前者的基础。
键索引计数法
适用性：用于小整数键的算法
比如数组a={1,2,3,4,2,3,4,2,1,3,4,2,3,4}，它里面重复的数字比较多，不重复的只有1，2，3，4，这时就可以用此方法
步骤
-
1、频率统计
统计各个数字出现的此时，这里1出现了2次，2出现了4次，3出现了4次
4出现了4次，并记录下来，我们用一个5位的数组记录。为什么5而不是4呢？接下来你就会知道
-
2将频率转化为索引
前面我们记录了各自数字的次数，并用数组保存，假设保存的数组为a[0]=0，a[1]=2,a[2]=4，a[3]=4，a[4]=4 这里从1开始计数，而不是从0，并不是为了与排序的数字对应，而是为了计算索引的方便，任意键的起始索引均为所有较小键的频率之和，我们就可以a[i+1]+=a[i]递推得到，这样a[0]=0，a[1]=2，a[2]=6，a[3]=10，a[4]=14，这样第一个数字（即1）的起始位置为 0，第2个数字（即 2）的起始位置为2......多一个位置的好处就已经体现出来了，第一个就是用来标记最开始的起始位置的
数据分类
得到各个数字的起始索引，接下来就是将原数组进行归类，将相同的数字放在一起，这里我们用一个临时的数组进行记录回写回原数组
最后是将临时数组中的值写会原数组
代码实现:
public class countSort {
public static void main(String[] args){
int[] nums={2,3,4,1,2,4,3,1,2,2,1};
countSort sort=new countSort();
sort.indecCountIndex(nums);
}
public void indecCountIndex(int[] nums){
int[] count=new int[6];
//计算频率
for(int i=0;i<nums.length;i++){
count[nums[i]+1]++;
}
//将频率转化为索引
for(int i=1;i<count.length;i++){
count[i]=count[i]+count[i-1];
}
//数据分类
int[] aux=new int[nums.length];
for(int i=0;i<nums.length;i++){
aux[count[nums[i]]++]=nums[i];
}
//回写数据（我这里是打印）
for(int i=0;i<nums.length;i++){
System.out.print(aux[i]+" ");
}
}
}
