排序9-计数排序

       计数排序是一种非基于比较的排序算法，我们之前介绍的各种排序算法几乎都是基于元素之间的比较来进行排序的，计数排序的时间复杂度为O(n+m)，m指的是数据量，说的简单点，计数排序算法的时间复杂度约等于O(n)，快于任何比较型的排序算法.   

         其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

1. 算法描述:

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

2. 动图演示. 

    以[3,5,8,2,5,4]这组数字来演示。

    首先，我们找到这组数字中最大的数，也就是8，创建一个最大下标为8的空数组arr。 

   遍历数据，将数据的出现次数填入arr中对应的下标位置中。

   遍历arr，将数据依次取出即可。

3. 代码实现: 

public static void sort(int[] arr) {

        //找出数组中的最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //初始化计数数组
        int[] countArr = new int[max + 1];

        //计数
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;
            arr[i] = 0;
        }
        
        //排序
        int index = 0;
        for (int i = 0; i < countArr.length; i++) {
            if (countArr[i] > 0) {
                arr[index++] = i;
            }
        }
    }

4. 分析: 

    计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

5. 应用案例: 

    需求描述:  对学生的成绩进行排序输出。  (注意: 计数排序是稳定的排序,原来排前面的人，排序后还是处于相同成绩的人的前面)

//定义学生类
public class Student {
    public String sname;
    public int score;

    public Student(String sname, int score) {
        this.sname = sname;
        this.score = score;
    }

    @Override
    public String toString() {
        return "Student{" +
                "sname='" + sname + '\'' +
                ", score=" + score +
                "}";
    }
}

public class Main {

    public static void main(String[] args) {
        Random r=new Random();

        Student[] ss=new Student[10];

        for( int i=0;i<ss.length;i++){
            ss[i]=new Student( "张"+i,  r.nextInt(  50)+50  );
        }

        System.out.println("原数组:");
        for(  Student s: ss){
            System.out.println(   s );
        }
        System.out.println("排序后");

        sort(   ss );

        for(  int i=ss.length-1;i>=0;i--){
            System.out.println(  ss[i] );
            
        }



    }

    public static void sort(Student[] arr) {
        //找出数组中的最大值
        Student max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i].score > max.score) {
                max = arr[i];
            }
        }
        //初始化计数数组
        int[] countArr = new int[max.score + 1];

        //计数
        for (int i = 0; i < arr.length; ++i) {
            countArr[arr[i].score]++;
        }
        //顺序累加
        for (int i = 1; i < max.score + 1; ++i) {
            countArr[i] = countArr[i-1] + countArr[i];
        }
        //排序后的数组
        Student[] sortedArr = new Student[arr.length];

        //排序
        for (int i = arr.length - 1; i >= 0; --i) {
            sortedArr[countArr[arr[i].score]-1] = arr[i];
            countArr[arr[i].score]--;
        }

        //将排序后的数据拷贝到原数组
        for (int i = 0; i < arr.length; ++i) {
            arr[i] = sortedArr[i];
        }


    }
}