计数排序《算法很美》

  • 时间:
  • 浏览:
  • 来源:互联网

计数排序

在这里插入图片描述

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

计数排序:

  • 一句话:用辅助数组对数组中出现的数字计数,元素转下标,下标转元素
  • 假设元素均大于等于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;

    }

}

本文链接http://www.hatan.cn/news/show-69563.html