键索引计数法

键索引计数法 是LSD MSD算法的基础

背景

比如一个班级的学生成绩分为 1,2,3,4 4个等级
这样我们就得到一个键值关系（组号和姓名）

我们希望根据等级排序

想得到的结果就是 一个数组（按照 1等级的学生紧跟2等级的然后是3等级的最后是4等级），也就是每个等级的学生会连续在一起存到数组中

思路

计算每个组别的频率，然后转化为索引（后面的值是前面小键频率的和）
然后就可以知道各个组别的起始索引

注意

1. 频率统计的时候 count索引对应是 组别+1
2. 数据分类
   count数组中存的是起始索引
   aux数组中存的是全部的学生数据
   当取到组别的值为x, 则aux[x]的值需要是 x组别 的student对象 然后count中存的对应组别+1的值加1，这样下一个该组别的student就会放入下一个aux[]数组

    public class Student{
        private int group;//组号
        private String name;//名字
        public int getGroup() {
            return group;
        }
        public void setGroup(int group) {
            this.group = group;
        }
        public String getName() {
            return name;
        }
        public void setName(String name) {
            this.name = name;
        }
        public Student(int group, String name){
            this.name = name;
            this.group = group;
        }
        public Student(){}
    }
    @Test
    public void test(){
        sort();
    }
    public void sort(){
        Student[] a = new Student[5];
        a[0] = new Student(1, "sun1");
        a[1] = new Student(2, "sun2");
        a[2] = new Student(3, "sun3");
        a[3] = new Student(1, "sun1");
        a[4] = new Student(4, "sun4");
        int N = a.length;
        int R = 5;
        
        Student[] aux = new Student[N];
        int[] count = new int[R + 1];
        //计算频率
        for (int i = 0; i < N; i++) {
            count[a[i].getGroup() + 1]++;

        }
        //频率转索引  前面的小键相加
        for (int r = 0; r < R; r++) {
            count[r + 1] += count[r];
 
        }
        //元素分类  划分按组别（键）
        for (int i = 0; i < N; i++) {
            aux[count[a[i].getGroup()]++] = a[i];
//          aux[count[a[i].getGroup()]] = a[i];
//          count[a[i].getGroup()]++;
        }
        for (int i = 0; i < N; i++) {
            a[i] = aux[i];
        }
    }