5.1 键索引计数法

た入场券 2022-06-09 10:19 43阅读 0赞

一、思想  
适用于小整数键的简单排序方法；假设数组a\[\]中的每个元素都保存了一个名字和一个组号，其中组号在0到R-1之间，以组号为键进行分组排序；

二、步骤  
频率统计：使用int数组计算每个键出现的频率；  
将频率转换成索引：使用count\[\]来计算每个键在排序结果中的起始位置；  
数据分类：将count\[\]数组转换成一张索引表后，将所有元素移动到一个辅助数组aux\[\]中以进行排序；  
回写：将排序数组aux\[\]结果复制回原数组;

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

三、代码

/** * 建索引计数法 * * @author pengcx * */ 
    public class KeyIndex {  
        /** * 使用键索引计数法对学生数组a，以键key进行分组排序 * * @param a * 学生数组a * @param R * 分组个数R */ 
        public static void sort(Student[] a, int R) { 
             int N = a.length; 
             Student[] aux = new Student[N]; 
             int[] count = new int[R + 1]; 
    
             // 第一步，计算出现的频率 
            for (int i = 0; i < N; i++) { 
                count[a[i].key() + 1]++; 
            } 
    
            //第二步，将频率转换成索引 
            for (int r = 0; r < R; r++) { 
                count[r + 1] += count[r]; 
            } 
    
            //第三步， 将元素分类 
            for (int i = 0; i < N; i++) { 
                aux[count[a[i].key()]++] = a[i]; 
            } 
    
             // 第四步，回写 
            for (int i = 0; i < N; i++) { 
                a[i] = aux[i]; 
            } 
        } 
    
        public static void main(String[] args) {  
            Student stu1 = new Student("cac", 2); 
            Student stu2 = new Student("fnc", 2); 
            Student stu3 = new Student("edb", 4); 
            Student stu4 = new Student("oel", 0); 
            Student stu5 = new Student("akf", 2); 
            Student stu6 = new Student("erk", 1); 
    
            Student[] stus = { stu1, stu2, stu3, stu4, stu5, stu6 }; 
            sort(stus, 5); 
    
            for (int i = 0; i < stus.length; i++) { 
                System.out.println(stus[i].toString()); 
            } 
        } 
    } 
    
    class Student { 
        private String name; 
        private int key; 
    
        public Student(String name, int key) { 
            super(); 
            this.name = name; 
            this.key = key; 
        } 
    
        public int key() { 
            return key; 
        } 
    
        @Override 
        public String toString() { 
            return name + ":" + key; 
        } 
    }

参考：  
[http://lib.csdn.net/article/datastructure/30328][http_lib.csdn.net_article_datastructure_30328]

[http_lib.csdn.net_article_datastructure_30328]: http://lib.csdn.net/article/datastructure/30328