草庐IT

【算法】基数排序算法的讲解和代码实践

晓晓先生 2023-09-24 原文

思路

基数排序也是三个桶排序算法之一，排序过程也是不需要进行比较。
基数排序的主要思路是：
1、先按个位数不同，把数组中所有元素放到0~9这10个不同的桶中；
2、从桶中按先入先出的顺序取出数据，此时数组个位数已经有序，再按照十位，放入桶中；
3、再取出，直到所有位数到进过桶，就完成了整个数组的排序。
另外说明一下计数排序的适用场景：
1、因为是按位数进行排序的，所以只能排正整数；
2、数组中的元素间隔越小越好。比如如果有一个数组是[1, 2, 111111111]，这样虽然只有一个数有9位，但是所有数都要跟着入桶。

讲解

有数组如下：


image.png

我们先按各位给所有数字入桶，入桶后如下：


image.png

第一次按个位数入桶后，从桶中把数取出得到如下数组：
image.png

然后按照十位数进行第二次入桶：


image.png

再次取出，得到数组如下：
image.png

下面进行百位数的最后一次入桶操作：
image.png

最后取出，排序完成：
image.png

实现

    @Test
    public void sortTest() {
        int[] nums = new int[]{2, 0, 31, 248, 243, 36, 46, 55};
        radixSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    private void radixSort(int[] nums) {
        if (nums.length < 2) {
            return;
        }
        // 找到最大值，确定需要入几次桶
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
            }
        }
        // 遍历入桶和取出，次数为最大数的位数
        for (int i = 0, divideNum = 10; i < String.valueOf(maxValue).length(); i++, divideNum *= 10) {
            // 初始化10个桶
            int[][] bucketArray = new int[10][0];
            // 遍历数组元素，按当前的数位入桶
            for (int j = 0; j < nums.length; j++) {
                int remainder = nums[j] % divideNum;
                if (divideNum > 10) {
                    remainder = remainder / (divideNum / 10);
                }
                bucketArray[remainder] = arrayAppend(bucketArray[remainder], nums[j]);
            }
            // 从桶中取出数据并放回数组
            for (int j = 0, l = 0; j < 10; j++) {
                for (int k = 0; k < bucketArray[j].length; k++) {
                    nums[l++] = bucketArray[j][k];
                }
            }
        }
    }

    private int[] arrayAppend(int[] array, int num) {
        int[] ints = Arrays.copyOf(array, array.length + 1);
        ints[ints.length - 1] = num;
        return ints;
    }

看下运行结果：


image.png
算法基数排序sectionimagesupload

有关【算法】基数排序算法的讲解和代码实践的更多相关文章

  1. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

    很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

  2. ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2

    如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby​​

  3. ruby-on-rails - Rails 源代码 : initialize hash in a weird way? - 2

    在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案 查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has

  4. ruby-on-rails - 浏览 Ruby 源代码 - 2

    我的主要目标是能够完全理解我正在使用的库/gem。我尝试在Github上从头到尾阅读源代码，但这真的很难。我认为更有趣、更温和的踏脚石就是在使用时阅读每个库/gem方法的源代码。例如，我想知道RubyonRails中的redirect_to方法是如何工作的:如何查找redirect_to方法的源代码？我知道在pry中我可以执行类似show-methodmethod的操作，但我如何才能对Rails框架中的方法执行此操作？您对我如何更好地理解Gem及其API有什么建议吗？仅仅阅读源代码似乎真的很难，尤其是对于框架。谢谢! 最佳答案 Ru

  5. ruby - 模块嵌套代码风格偏好 - 2

    我的假设是moduleAmoduleBendend和moduleA::Bend是一样的。我能够从thisblog找到解决方案,thisSOthread和andthisSOthread.为什么以及什么时候应该更喜欢紧凑语法A::B而不是另一个，因为它显然有一个缺点？我有一种直觉，它可能与性能有关，因为在更多命名空间中查找常量需要更多计算。但是我无法通过对普通类进行基准测试来验证这一点。 最佳答案 这两种写作方法经常被混淆。首先要说的是，据我所知，没有可衡量的性能差异。(在下面的书面示例中不断查找)最明显的区别，可能也是最著名的，是你的

  6. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  7. ruby - Net::HTTP 获取源代码和状态 - 2

    我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。 最佳答案 在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur

  8. 世界前沿3D开发引擎HOOPS全面讲解——集3D数据读取、3D图形渲染、3D数据发布于一体的全新3D应用开发工具 - 2

    无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD

  9. 程序员如何提高代码能力？ - 2

    前言作为一名程序员，自己的本质工作就是做程序开发，那么程序开发的时候最直接的体现就是代码，检验一个程序员技术水平的一个核心环节就是开发时候的代码能力。众所周知，程序开发的水平提升是一个循序渐进的过程，每一位程序员都是从“菜鸟”变成“大神”的，所以程序员在程序开发过程中的代码能力也是根据平时开发中的业务实践来积累和提升的。提高代码能力核心要素程序员要想提高自身代码能力，尤其是新晋程序员的代码能力有很大的提升空间的时候，需要针对性的去提高自己的代码能力。提高代码能力其实有几个比较关键的点，只要把握住这些方面，就能很好的、快速的提高自己的一部分代码能力。1、多去阅读开源项目，如有机会可以亲自参与开源

  10. 叮咚买菜基于 Apache Doris 统一 OLAP 引擎的应用实践 - 2

    导读：随着叮咚买菜业务的发展，不同的业务场景对数据分析提出了不同的需求，他们希望引入一款实时OLAP数据库，构建一个灵活的多维实时查询和分析的平台，统一数据的接入和查询方案，解决各业务线对数据高效实时查询和精细化运营的需求。经过调研选型，最终引入ApacheDoris作为最终的OLAP分析引擎，Doris作为核心的OLAP引擎支持复杂地分析操作、提供多维的数据视图，在叮咚买菜数十个业务场景中广泛应用。作者｜叮咚买菜资深数据工程师韩青叮咚买菜创立于2017年5月，是一家专注美好食物的创业公司。叮咚买菜专注吃的事业，为满足更多人“想吃什么”而努力，通过美好食材的供应、美好滋味的开发以及美食品牌的孵

随机推荐