计数排序（Counting Sort）是一种非比较性排序算法，适用于对一定范围内的整数进行排序。它通过统计每个元素出现的次数，然后根据统计信息重新构建有序数组。计数排序是一种线性时间复杂度的排序算法，具有稳定性和适用性广泛的特点。本文将详细介绍计数排序的工作原理和Python实现。
计数排序(Counting Sort)是一种不比较数据大小的排序算法，是一种牺牲空间换取时间的排序算法。
2、计数排序要求输入的数据必须是有确定范围的整数，因此计数排序法适用于量大范围小的数据。
计数排序与桶排序都是以牺牲空间换时间，虽然很快，但由于可能产生大量的空位置导致内存增大，尤其是计数排序。
堆排序和计数排序是两种高效的排序算法，用于将一个无序列表按照特定顺序重新排列。本篇博客将介绍堆排序和计数排序的基本原理，并通过实例代码演示它们的应用。
排序算法是一种将一组数据按照特定的规则进行排列的方法。排序算法通常用于对数据的处理，使得数据能够更容易地被查找、比较和分析。
通常的排序算法是要进行元素之间的比较，而计数排序是记录下每个元素出现的个数，是一种空间换时间的排序方法。适合整数数组排序，并且不同元素个数不宜过多。
人到中年，容易变得油腻，思想懒惰，身体就容易发胖。为了摆脱中年油腻，不如和我一起学习算法来烧烧脑子，燃烧你的卡路里。
我简单的绘制了一下排序算法的分类，蓝色字体的排序算法是我们用python3实现的，也是比较常用的排序算法。
计数排序算法是一种典型的以空间换时间的一种算法。 这种算法主要是适合于正整数进行 排序。还是比较好理解的，而且在很多场合确实能提高效率。
由于LeetCode上的算法题很多涉及到一些基础的数据结构，为了更好的理解后续更新的一些复杂题目的动画，推出一个新系列 -----《图解数据结构》，主要使用动画来描述常见的数据结构和算法。本系列包括十大排序、堆、队列、树、并查集、图等等大概几十篇。
讲解计数排序之前我们先来看一个问题：对列表进行排序，已知列表中的数的范围都在0-500之内，设计一个时间复杂度为O(n)的算法。
哈喽各位铁汁们常用的八大排序我们都一起实现了，但是前面我们的实现过程大部分都是比较排序，不知道大家听说过计数排序这种非比较排序？它的性能再某些场景甚至能达到惊人的 O(N)
相对映射较好的解决了绝对映射的缺点,但当遇到待排数据分布较为分散且跨度较大时,就不太适合使用计数排序来进行排序了.
经典排序算法和python详解（三）：归并排序、快速排序、堆排序、计数排序、桶排序和基数排序
假设现有一组数据,最大的数据是1000,那么便会开一千个大小的空间,这种属于绝对映射,在极端的场景下,极易造成空间上的浪费，比如现在有5,99,88,1000,8888,452,635,82,777,555,只有10个数但是最大的数是8888因此要开8888大小的空间,剩余的空间全部都浪费了。
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
谈到排序该怎么算，直觉上应该都要元素之间进行比较才能排出顺序，比较是不可或缺的，但偏偏有的排序算法可以不用比较，比如传说中的“睡眠排序”（n个线程同时睡觉，按照醒来的顺序排序）。因此排序算法可以分成基于比较的排序和非比较的排序2大类。
与基于比较的排序算法（归并排序、堆排序、快速排序、冒泡排序、插入排序等等）相比，基于比较的排序算法的时间复杂度最好也就是
计数排序(CountSort)是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序） ————百度百科
一般排序算法最常考的：快速排序和归并排序。这两个算法体现了分治算法的核心观点，而且还有很多出题的可能。
计数排序（Counting Sort）是一种非比较排序算法，其核心思想是通过计数每个元素的出现次数来进行排序，适用于整数或有限范围内的非负整数排序。这个算法的特点是速度快且稳定，适用于某些特定场景。在本文中，我们将深入探讨计数排序的原理、步骤以及性能分析。
话不多数，先上两张图： 名词解释： n：数据规模 k：“桶”的个数 In-place：占用常数内存，不占用额外内存 Out-place：占用额外内存 稳定性：排序后2个相等键值的顺序和排序之前
来源：SteveWang http://www.cnblogs.com/eniac12/p/5332117.html 上一篇总结了常用的比较排序算法，主要有冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。 这篇文章中我们来探讨一下常用的非比较排序算法：计数排序，基数排序，桶排序。在一定条件下，它们的时间复杂度可以达到O(n)。 这里我们用到的唯一数据结构就是数组，当然我们也可以利用链表来实现下述算法。 计数排序(Counting Sort) 计数排序用到一个额外的计数数组C，根据数组C来将原数
排序算法是计算机程序设计中的基础算法之一，排序算法作用是将一个无序序列排序成有序序列。
这篇文章中再和小伙伴们来探讨一下常用的非比较排序算法：计数排序，基数排序，桶排序。在一定条件下，它们的时间复杂度可以达到O(n)。
计数排序（Counting Sort）是一种针对于特定范围之间的整数进行排序的算法。它通过统计给定数组中不同元素的数量（类似于哈希映射），然后对映射后的数组进行排序输出即可。
这里我是按自己的理解去实现的，时间复杂度和空间复杂度和算法导论上的可能不一样，感兴趣的话参考下就行，感觉最重要的还是算法思想。根据算法性能去实现算法以后再研究。
老读者可能比较熟悉，刚开始的时候写了一个排序算法系列，把常见的排序算法都写了，有兴趣的可以在公众号内的目录菜单栏中选择数据结构与算法查看。
综上，计数排序在特定场景下（如数据范围不大、整数类型）是一种快速且高效的排序选择，但其适用场景相对有限，且空间效率较低。
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。
我们这里利用malloc开辟一个数组来统计相同元素出现的次数，用该数字下标表示相同元素，下标对应的值来统计次数 图示如下：
计数排序是通过对待排序序列中的每种元素的个数进行计数，然后获得每个元素在排序后的位置的排序算法。即：对每一个输人元素 x，确定小于 x 的元素个数，然后就可以直接把 x 放到它在已排序数组中的位置上。
假设有这样子一个题：数组里有20个随机数，取值范围为从0到10，要求用最快的速度把这20个整数从小到大进行排序。
计数排序只适合使用在键的变化不大于元素总数的情况下。它通常用作另一种排序算法（基数排序）的子程序，这样可以有效地处理更大的键。
将要排序的数据分到几个有序的桶里， 每个桶里的数据再单独进行排序。 桶内排完序之后，再把每个桶里的数据按照顺序依次取出， 组成的序列就是有序的了。
之前写过一篇八种排序算法的博客，不过都是基于小数据量进行的排序，没有像这篇这样做大数据排序。文末会放出链接。
计数排序利用数组索引号的有序而对数据排序，所以，需要把原无序数组中的数据映射到排序数组的索引号上。于是，对排序数组的长度就会有一个最小值的约束，至少等于无序数组中的最大值加一。
第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
1、计数排序（Counting Sort） 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
（注：文章中的算法顺序是按照下面的图片中的分类进行，你可以不按照这个顺序。根据你的个人喜好、时间以及上面的侧重点分析，按照自己的需求学习即可。）
计数排序（Counting sort）是一种稳定的线性时间排序算法，其平均时间复杂度和空间复杂度为O(n+k)，其中n为数组元素的个数，k为待排序数组里面的最大值。同样具有线性时间排序的算法还有桶排序和基数排序，这一点不要搞混。
基数排序（Radix Sort）是一种非比较型的排序算法，它通过将待排序元素按照高位和低位的顺序依次进行排序，从而实现整体的排序效果。其基本步骤如下：
基数排序属于非比较排序算法类，故其时间复杂度不受比较排序算法时间复杂度下界的限制。基数排序对排序关键字的最低数位到最高数位中的每一数位采用其他排序算法进行排序。基数排序时间复杂度可以达到 （这中情况下对每一数位采用的排序算法为计数排序）。其中， 为待排序序列的排序关键字每一数位的最大范围，ddd 是排序关键字的数位数目。 计数排序要求每一数位排序所使用的排序算法都是稳定的，否则将影响计数排序的正确性。基数排序是稳定的，其原址性取决于对每一数位所使用的排序算法的原址性。
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。
Arrays.Sort方法所用的排序算法主要涉及以下三种：双轴快速排序（DualPivotQuicksort）、归并排序（MergeSort)、TimSort，也同时包含了一些非基于比较的排序算法：例如计数排序。其具体最终使用哪一种排序算法通常根据类型以及输入长度来动态抉择。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
对象存储
云直播
