字符串排序：键索引计数法

字符串排序有很多应用，比如车牌的排序，基因编码等。今天介绍一种低位优先的字符串排序算法，在介绍它之前先介绍另一种算法--键索引计数法，它是前者的基础。

键索引计数法

适用性：用于小整数键的算法

比如数组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]+" ");
        }
    }
}