温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Java怎么实现count排序

发布时间:2022-01-15 10:35:25 来源:亿速云 阅读:180 作者:iii 栏目:大数据

这篇文章主要讲解了“Java怎么实现count排序”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Java怎么实现count排序”吧!

简介

count排序是一种空间换时间的算法,我们借助一个外部的count数组来统计各个元素出现的次数,从而最终完成排序。

count排序的例子

count排序有一定的限制,因为外部的count数组长度是和原数组的元素范围是一致的,所以count排序一般只适合数组中元素范围比较小的情况。

我们举一个0-9的元素的排序的例子:3,4,2,5,6,2,4,9,1,3,5。

先看一个动画,看看是怎么排序的:

Java怎么实现count排序

count数组里面存放的是从0到9这些元素出现的次数。

我们遍历原始数组,遇到相应的数字就给相应的count+1。

等所有的元素都count之后,再根据count数组中的值还原排序过后的数组。

count排序的java实现

count排序很简单,我们主要掌握下面两个大的步骤:

  1. 遍历原始数组,构建count数组。

  2. 根据count数组中的count值,重新构建排序数组。

public class CountingSort {

    public void doCountingSort(int[] array){
        int n = array.length;

        // 存储排序过后的数组
        int output[] = new int[n];

        // count数组,用来存储统计各个元素出现的次数
        int count[] = new int[10];
        for (int i=0; i<10; ++i) {
            count[i] = 0;
        }
        log.info("初始化count值:{}",count);

        // 将原始数组中数据出现次数存入count数组
        for (int i=0; i<n; ++i) {
            ++count[array[i]];
        }
        log.info("count之后count值:{}",count);

        //遍历count,将相应的数据插入output
        int j=0;
        for(int i=0; i<10; i++){
            while(count[i]-- > 0){
                output[j++]=i;
            }
        }
        log.info("构建output之后的output值:{}",output);

        //将排序后的数组写回原数组
        for (int i = 0; i<n; ++i)
            array[i] = output[i];
    }

    public static void main(String[] args) {
        int[] array= {3,4,2,5,6,2,4,9,1,3,5};
        CountingSort countingSort=new CountingSort();
        log.info("countingSort之前的数组为:{}",array);
        countingSort.doCountingSort(array);
    }
}

上面的注释应该很清楚了。

运行的结果如下:

Java怎么实现count排序

count排序的第二种方法

在我们获得count数组中每个元素的个数之后,其实我们还有另外一个生成结果数组的办法:

// 这里是一个小技巧,我们根据count中元素出现的次数计算对应元素第一次应该出现在output中的下标。
        //这里的下标是从右往左数的
        for (int i=1; i<10; i++) {
            count[i] += count[i - 1];
        }
        log.info("整理count对应的output下标:{}",count);
        // 根据count中的下标,构建排序后的数组
        //插入一个之后,相应的count下标要减一
        for (int i = n-1; i>=0; i--)
        {
            output[count[array[i]]-1] = array[i];
            --count[array[i]];
        }
        log.info("构建output之后的output值:{}",output);

主要分为两步:

第一步我们根据count中元素出现的次数计算对应元素第一次应该出现在output中的下标。这里的下标是从右往左数的。

第二步根据count中的下标,构建排序后的数组,插入一个之后,相应的count下标要减一。

Java怎么实现count排序

感谢各位的阅读,以上就是“Java怎么实现count排序”的内容了,经过本文的学习后,相信大家对Java怎么实现count排序这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI