计数排序

计数排序：优点：快
缺点：数据范围大，比较稀疏，会导致辅助空间很大，也稀疏，造成空间的浪费

计数排序：

• 一句话：用辅助数组对数组中出现的数字计数，元素转下标，下标转元素
• 假设元素均大于等于0，依次扫描原数组，将元素值k记录在辅助数组的k位上
• 依次扫描辅助数组，如果为1，将其插入目标数组的空白处
• 问题
  • 重复元素
  • 有负数

我的思路： 先利用Util.maxOf开辟一个最大的辅助空间。然后让辅助空间根据source的数进行++，然后遍历helper[]，将helper[i]>0的值转到source['current++]中，同时helper[i]–消除可能重复的例子

具体思路：

1. int[] helper = new int[Util.maxOf(source) + 1];开辟辅助数组

2. 将辅助数组根据source[]的值进行++for(int e : source){
   helper[e]++;
   }

3. for (int i = 1; i < helper.length; i++)遍历helper[i]

4. 如果helper[i]有>0，则将helper[i]的值放入source[current++]=i中，同时也要helper[i]–，

package onetwo;

public class 计数排序 {
    public static void sort(int[] source){
        int[] helper = new int[Util.maxOf(source) + 1];
        for(int e : source){
            helper[e]++;
        }
        int current = 0; //数据回填的位置
        for (int i = 1; i < helper.length; i++){
            while (helper[i]>0){
                //下标转元素
                source[current++] = i;
                //可能会有重复的例子所以--
                helper[i]--;
            }
        }
    }

    public static void main(String[] args){
        int[] arr = {1,5,3,6,2,68,3,4};
        sort(arr);
        Util.print(arr);
    }


 public static int maxOf(int[] source) {
        int nmax = source[0];
        int num=source.length;
        for(int i=0;i<num;i++)
        {
            if(source[i]>=nmax)
                nmax=source[i];
        }
        return nmax;

    }

}