AI 助理
备案控制台
开发者社区 人工智能 文章 正文

sort-08-counting sort 计数排序

2024-04-27 28
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 这是一个关于排序算法的系列文章摘要。文章详细介绍了多种排序算法，包括冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、计数排序、桶排序以及大文件外部排序。计数排序是一种线性时间复杂度的稳定排序算法，由 Harold H. Seward 在1954年提出。基础版计数排序通过创建一个与最大元素等长的新数组来统计每个元素出现的次数，然后填充排序结果。改良版则考虑了空间浪费问题，通过找出最小值来减少数组长度。此外，还提出了使用 TreeMap 来扩展排序算法以适应非数字元素的情况。

排序系列

sort-00-排序算法汇总

sort-01-bubble sort 冒泡排序算法详解

sort-02-QuickSort 快速排序到底快在哪里？

sort-03-SelectSort 选择排序算法详解

sort-04-heap sort 堆排序算法详解

sort-05-insert sort 插入排序算法详解

sort-06-shell sort 希尔排序算法详解

sort-07-merge sort 归并排序

sort-08-counting sort 计数排序

sort-09-bucket sort 桶排序

sort-10-bigfile 大文件外部排序

counting sort 计数排序

计数排序（Counting sort）是一种稳定的线性时间排序算法。

该算法于1954年由 Harold H. Seward 提出。

通过计数将时间复杂度降到了 O(N)。

基础版

算法步骤

  1. 找出原数组中元素值最大的，记为max。

  2. 创建一个新数组count，其长度是max加1，其元素默认值都为0。

  3. 遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。

  4. 创建结果数组result，起始索引index。

  5. 遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素。

  6. 返回结果数组 result。

java 实现

package com.github.houbb.sort.core.api;

import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 计数排序
 *
 * @author binbin.hou
 * @since 0.0.8
 */
@ThreadSafe
public class CountingSortBasic extends AbstractSort {
   

    private static final Log log = LogFactory.getLog(CountingSortBasic.class);

    @Override
    @SuppressWarnings("all")
    public void doSort(List original) {
   
        //1. 获取最大的元素
        int max = Integer.MIN_VALUE;
        for (Object object : original) {
   
            Integer integer = (Integer) object;
            max = Math.max(max, integer);
        }

        //2. 构建 count 列表
        int[] counts = new int[max + 1];
        //3.遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。
        for (Object object : original) {
   
            Integer integer = (Integer) object;
            counts[integer]++;
        }

        //4. 结果构建
        int index = 0;
        // 遍历计数数组，将计数数组的索引填充到结果数组中
        for (int i = 0; i < counts.length; i++) {
   
            while (counts[i] > 0) {
   
                // i 实际上就是元素的值
                // 从左到右遍历，元素自然也就排序好了。
                // 相同的元素会出现多次，所以才需要循环。
                original.set(index++, i);
                counts[i]--;

                if(log.isDebugEnabled()) {
   
                    log.debug("结果数组：{}", original);
                }
            }
        }
    }

}

测试

List<Integer> list = RandomUtil.randomList(10);
System.out.println("开始排序：" + list);
SortHelper.countingSortBasic(list);
System.out.println("完成排序：" + list);

测试日志如下：

开始排序：[67, 63, 78, 15, 2, 47, 88, 68, 71, 86]
结果数组：[2, 63, 78, 15, 2, 47, 88, 68, 71, 86]
结果数组：[2, 15, 78, 15, 2, 47, 88, 68, 71, 86]
结果数组：[2, 15, 47, 15, 2, 47, 88, 68, 71, 86]
结果数组：[2, 15, 47, 63, 2, 47, 88, 68, 71, 86]
结果数组：[2, 15, 47, 63, 67, 47, 88, 68, 71, 86]
结果数组：[2, 15, 47, 63, 67, 68, 88, 68, 71, 86]
结果数组：[2, 15, 47, 63, 67, 68, 71, 68, 71, 86]
结果数组：[2, 15, 47, 63, 67, 68, 71, 78, 71, 86]
结果数组：[2, 15, 47, 63, 67, 68, 71, 78, 86, 86]
结果数组：[2, 15, 47, 63, 67, 68, 71, 78, 86, 88]
完成排序：[2, 15, 47, 63, 67, 68, 71, 78, 86, 88]

作为一个开场，还是很不错的。

改良版

空间浪费

实际上我们创建一个比最大元素还要大1的数组，只是为了放下所有的元素而已。

但是它有一个缺陷，那就是存在空间浪费的问题。

比如一组数据{101,109,102,110}，其中最大值为110，按照基础版的思路，我们需要创建一个长度为111的计数数组，但是我们可以发现，它前面的[0,100]的空间完全浪费了，那怎样优化呢？

将数组长度定为 max-min+1，即不仅要找出最大值，还要找出最小值，根据两者的差来确定计数数组的长度。

改良版本实现

import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;

import java.util.Arrays;
import java.util.List;

/**
 * 计数排序
 *
 * @author binbin.hou
 * @since 0.0.8
 */
@ThreadSafe
public class CountingSort extends AbstractSort {
   

    private static final Log log = LogFactory.getLog(CountingSort.class);

    @Override
    @SuppressWarnings("all")
    public void doSort(List original) {
   
        //1. 获取最大、最小的元素
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (Object object : original) {
   
            Integer integer = (Integer) object;
            max = Math.max(max, integer);
            min = Math.min(min, integer);
        }

        //2. 构建 count 列表
        int[] counts = new int[max-min + 1];
        //3.遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。
        for (Object object : original) {
   
            Integer integer = (Integer) object;
            // 元素要减去最小值，再作为新索引
            counts[integer-min]++;
        }

        if(log.isDebugEnabled()) {
   
            log.debug("counts.length: {}", counts.length);
        }
        //4. 结果构建
        int index = 0;
        // 遍历计数数组，将计数数组的索引填充到结果数组中
        for (int i = 0; i < counts.length; i++) {
   
            while (counts[i] > 0) {
   
                // i 实际上就是元素的值
                // 从左到右遍历，元素自然也就排序好了。
                // 相同的元素会出现多次，所以才需要循环。
                // 这里将减去的最小值统一加上
                original.set(index++, i+min);
                counts[i]--;

                if(log.isDebugEnabled()) {
   
                    log.debug("结果数组：{}", original);
                }
            }
        }
    }

}

测试

日志如下：

开始排序：[27, 59, 25, 73, 30, 82, 80, 65, 72, 43]
counts.length: 58
结果数组：[25, 59, 25, 73, 30, 82, 80, 65, 72, 43]
结果数组：[25, 27, 25, 73, 30, 82, 80, 65, 72, 43]
结果数组：[25, 27, 30, 73, 30, 82, 80, 65, 72, 43]
结果数组：[25, 27, 30, 43, 30, 82, 80, 65, 72, 43]
结果数组：[25, 27, 30, 43, 59, 82, 80, 65, 72, 43]
结果数组：[25, 27, 30, 43, 59, 65, 80, 65, 72, 43]
结果数组：[25, 27, 30, 43, 59, 65, 72, 65, 72, 43]
结果数组：[25, 27, 30, 43, 59, 65, 72, 73, 72, 43]
结果数组：[25, 27, 30, 43, 59, 65, 72, 73, 80, 43]
结果数组：[25, 27, 30, 43, 59, 65, 72, 73, 80, 82]
完成排序：[25, 27, 30, 43, 59, 65, 72, 73, 80, 82]

这次的 counts 长度为：58，而不是 81。

自己的思考

算法的本质

这个算法的本质是什么呢？

个人理解只需要保证两点：

（1）每一个元素，都有自己的一个元素位置

（2）相同的元素，次数会增加。

算法的巧妙之处在于直接利用数值本身所谓索引，直接跳过了排序比较；利用技数，解决了重复数值的问题。

算法的不足

这个算法的巧妙之处，同时也是对应的限制：那就是只能直接比较数字。如果是字符串呢？

一点想法

我最初的想法就是可以使用类似于 HashMap 的数据结构。这样可以解决元素过滤，次数统计的问题。

但是无法解决排序问题。

当然了，如果使用 TreeMap 就太赖皮了，因为本身就是利用了树进行排序。

TreeMap 版本

我们这里使用 TreeMap 主要有下面的目的：

（1）让排序不局限于数字。

（2）大幅度降低内存的浪费，不多一个元素，也不少一个元素。

思想实际上依然是技术排序的思想。

package com.github.houbb.sort.core.api;

import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;

import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * 计数排序-TreeMap
 *
 * @author binbin.hou
 * @since 0.0.8
 */
@ThreadSafe
public class CountingSortTreeMap extends AbstractSort {
   

    private static final Log log = LogFactory.getLog(CountingSortTreeMap.class);

    @Override
    @SuppressWarnings("all")
    public void doSort(List original) {
   
        TreeMap<Comparable, Integer> countMap = new TreeMap<>();

        // 初始化次数
        for (Object object : original) {
   
            Comparable comparable = (Comparable) object;

            Integer count = countMap.get(comparable);
            if(count == null) {
   
                count = 0;
            }
            count++;
            countMap.put(comparable, count);
        }

        //4. 结果构建
        int index = 0;
        // 遍历计数数组，将计数数组的索引填充到结果数组中
        for (Map.Entry<Comparable, Integer> entry : countMap.entrySet()) {
   
            int count = entry.getValue();
            Comparable key = entry.getKey();
            while (count > 0) {
   
                // i 实际上就是元素的值
                // 从左到右遍历，元素自然也就排序好了。
                // 相同的元素会出现多次，所以才需要循环。
                original.set(index++, key);
                count--;
            }
        }
    }

}

测试

List<Integer> list = RandomUtil.randomList(10);
System.out.println("开始排序：" + list);
SortHelper.countingSortTreeMap(list);
System.out.println("完成排序：" + list);

日志如下：

开始排序：[92, 50, 9, 17, 89, 31, 17, 65, 39, 94]
完成排序：[9, 17, 17, 31, 39, 50, 65, 89, 92, 94]

开源地址

为了便于大家学习，上面的排序已经开源，开源地址：

https://github.com/houbb/sort

欢迎大家 fork/star，鼓励一下作者~~

小结

希望本文对你有帮助，如果有其他想法的话，也可以评论区和大家分享哦。

各位极客的点赞收藏转发，是老马持续写作的最大动力！

文章标签：
搜索推荐
算法
索引
Java
老马啸西风2024
目录
相关文章
GuGuStudy
|
1月前
|
搜索推荐
冒泡排序（Bubble Sort）以及选择排序（Selection Sort）和快速排序（Quick Sort）详细解析
冒泡排序（Bubble Sort）以及选择排序（Selection Sort）和快速排序（Quick Sort）详细解析
GuGuStudy
17 1
老马啸西风2024
|
6月前
|
搜索推荐 算法 Java
sort-01-bubble sort 冒泡排序算法详解
这是一个关于排序算法的系列文章摘要。作者整理了10种不同的排序算法，包括冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、计数排序、桶排序和大文件外部排序。文章详细介绍了冒泡排序的工作原理、流程，并提供了代码实现，强调了在实现中考虑的改进点，如统一接口、实用性增强和日志输出。此外，还提供了一个排序接口和工具类以方便使用，并通过测试代码和日志展示了排序过程。整个系列旨在帮助读者理解和掌握排序算法。相关代码已开源在GitHub。
老马啸西风2024
53 0
老马啸西风2024
|
6月前
|
人工智能 搜索推荐 算法
sort-04-heap sort 堆排序算法详解
这是一个关于排序算法的系列文章摘要，包括了10篇关于不同排序算法的链接，如冒泡排序、快速排序、选择排序、堆排序等。堆排序是一种基于比较的排序算法，利用了近似完全二叉树的结构并满足最大堆或最小堆的性质。最大堆中，每个节点的值都大于或等于其子节点。文章详细解释了最大堆的概念、节点访问方式以及堆的操作，包括堆调整和堆排序的过程，并通过图解展示了堆排序的具体步骤。此外，还提供了一个Java实现的堆排序代码示例。整个排序系列来源于一个开源项目，读者可以通过链接查看完整内容。
老马啸西风2024
62 0
sort-04-heap sort 堆排序算法详解
老马啸西风2024
|
6月前
|
搜索推荐 算法 Java
sort-03-SelectSort 选择排序算法详解
这是一个关于排序算法的系列文章摘要，包括了各种排序算法的介绍和Java实现。文章列举了冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、计数排序、桶排序以及大文件外部排序的链接和简要说明。其中，选择排序算法被详细解释，它是通过找到未排序序列中的最小元素并将其放到正确位置来逐步构建有序序列的。Java实现中，选择排序的`doSort`方法通过两层循环实现，时间复杂度为`O(N^2)`，是稳定的排序算法。整个排序项目已开源在GitHub。
老马啸西风2024
33 0
Mr.anla
|
6月前
|
存储
归并排序 merge_sort
归并排序 merge_sort
Mr.anla
28 0
老马啸西风2024
|
6月前
|
搜索推荐 算法 Java
sort-07-merge sort 归并排序
这是一个关于排序算法的系列文章摘要。文章涵盖了多种排序算法的详细解释，包括冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、计数排序、桶排序以及大文件外部排序。归并排序是一种效率为O(nlogn)的排序算法，基于分治法，将序列分成两半，分别排序后再合并。文章提供了Java实现的递归和迭代版本。在归并排序的递归实现中，代码通过不断拆分和合并子序列完成排序，而迭代实现则是通过逐步增大子序列长度并进行两两归并来排序。整个系列可在GitHub找到相关源码。
老马啸西风2024
29 0
老马啸西风2024
|
6月前
|
存储 搜索推荐 算法
sort-09-bucket sort 桶排序
这是一个关于排序算法的系列文章总结，包括冒泡、快速、选择、堆、插入、希尔、归并、计数、桶和大文件外部排序。桶排序是一种将元素分配到有限数量的桶中，然后对每个桶分别排序的算法。在元素均匀分布的情况下，桶排序的时间复杂度为线性`O(n)`。文章还提供了一个Java实现示例及复杂度分析。完整代码可在GitHub的开源项目中找到。
老马啸西风2024
35 0
修己xj
|
存储 搜索推荐 算法
计数排序（Counting Sort）详解
计数排序（Counting Sort）是一种非比较排序算法，其核心思想是通过计数每个元素的出现次数来进行排序，适用于整数或有限范围内的非负整数排序。这个算法的特点是速度快且稳定，适用于某些特定场景。在本文中，我们将深入探讨计数排序的原理、步骤以及性能分析。
修己xj
262 1
计数排序（Counting Sort）详解
武梓龙_Wzill
|
算法
直接插入排序(Straight Insertion Sort)
直接插入排序
武梓龙_Wzill
76 0
游客q7aiz7vku45zk
|
算法
2-路插入排序(Two-Way Insertion Sort)
算法介绍 算法描述 算法分析 代码实现 参考
游客q7aiz7vku45zk
292 0

热门文章

最新文章

  • 1
    Java 生成 UUID
  • 2
    一文读懂 Serverless 的起源、发展和落地实践
  • 3
    Fiddler抓包：下载、安装及使用
  • 4
    用CodeViz绘制函数调用关系图(call graph)
  • 5
    阿里AI上岗双11服装车间，能识别头发丝直径十分之一的瑕疵
  • 6
    SpringBoot开发案例之整合Dubbo提供者(一)
  • 7
    Dubbo架构介绍
  • 8
    警惕垃圾邮件借加沙新闻进行钓鱼攻击
  • 9
    美国博客刊文发布NetApp StoreVault停产通知
  • 10
    IntelliJ IDEA 12 创建Web项目 教程 超详细版
  • 1
    通义灵码与云计算平台的融合：基础与概述
    37
  • 2
    《深度解析：死锁的“前世今生”与防范之道》
    31
  • 3
    《探秘程序崩溃：核心转储（Core Dump）分析全攻略》
    34
  • 4
    今日 AI 开源｜共 12 项｜开源的DIY健康追踪项目，基于低成本的智能戒指构建私人的健康监测应用
    38
  • 5
    Open Interpreter：AI 赋能终端！在终端中对话AI模型进行编程，通过运行代码来完成各种计算机操作任务
    31
  • 6
    「Mac畅玩鸿蒙与硬件15」鸿蒙UI组件篇5 - Slider 和 Progress 组件
    40
  • 7
    ai断点怎么做?
    16
  • 8
    AI Shell：在命令行里“对话” AI ，微软推出将 AI 助手引入命令行的 CLI 工具，打造对话式交互命令行
    19
  • 9
    ai怎么设计迷宫字体效果?
    15
  • 10
    「Mac畅玩鸿蒙与硬件14」鸿蒙UI组件篇4 - Toggle 和 Checkbox 组件
    29

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云OSS设置跨域访问