哈喽各位铁汁们常用的八大排序我们都一起实现了，但是前面我们的实现过程大部分都是比较排序，不知道大家听说过计数排序这种非比较排序？它的性能再某些场景甚至能达到惊人的 O(N)
相对映射较好的解决了绝对映射的缺点,但当遇到待排数据分布较为分散且跨度较大时,就不太适合使用计数排序来进行排序了.
计数排序（Counting Sort）是一种非比较性排序算法，适用于对一定范围内的整数进行排序。它通过统计每个元素出现的次数，然后根据统计信息重新构建有序数组。计数排序是一种线性时间复杂度的排序算法，具有稳定性和适用性广泛的特点。本文将详细介绍计数排序的工作原理和Python实现。
假设现有一组数据,最大的数据是1000,那么便会开一千个大小的空间,这种属于绝对映射,在极端的场景下,极易造成空间上的浪费，比如现在有5,99,88,1000,8888,452,635,82,777,555,只有10个数但是最大的数是8888因此要开8888大小的空间,剩余的空间全部都浪费了。
谈到排序该怎么算，直觉上应该都要元素之间进行比较才能排出顺序，比较是不可或缺的，但偏偏有的排序算法可以不用比较，比如传说中的“睡眠排序”（n个线程同时睡觉，按照醒来的顺序排序）。因此排序算法可以分成基于比较的排序和非比较的排序2大类。
与基于比较的排序算法（归并排序、堆排序、快速排序、冒泡排序、插入排序等等）相比，基于比较的排序算法的时间复杂度最好也就是
堆排序和计数排序是两种高效的排序算法，用于将一个无序列表按照特定顺序重新排列。本篇博客将介绍堆排序和计数排序的基本原理，并通过实例代码演示它们的应用。
计数排序(CountSort)是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序） ————百度百科
排序算法是一种将一组数据按照特定的规则进行排列的方法。排序算法通常用于对数据的处理，使得数据能够更容易地被查找、比较和分析。
计数排序(Counting Sort)是一种不比较数据大小的排序算法，是一种牺牲空间换取时间的排序算法。
计数排序（Counting Sort）是一种非比较排序算法，其核心思想是通过计数每个元素的出现次数来进行排序，适用于整数或有限范围内的非负整数排序。这个算法的特点是速度快且稳定，适用于某些特定场景。在本文中，我们将深入探讨计数排序的原理、步骤以及性能分析。
来源：SteveWang http://www.cnblogs.com/eniac12/p/5332117.html 上一篇总结了常用的比较排序算法，主要有冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。 这篇文章中我们来探讨一下常用的非比较排序算法：计数排序，基数排序，桶排序。在一定条件下，它们的时间复杂度可以达到O(n)。 这里我们用到的唯一数据结构就是数组，当然我们也可以利用链表来实现下述算法。 计数排序(Counting Sort) 计数排序用到一个额外的计数数组C，根据数组C来将原数
计数排序与桶排序都是以牺牲空间换时间，虽然很快，但由于可能产生大量的空位置导致内存增大，尤其是计数排序。
计数排序（Counting Sort）是一种针对于特定范围之间的整数进行排序的算法。它通过统计给定数组中不同元素的数量（类似于哈希映射），然后对映射后的数组进行排序输出即可。
这篇文章中再和小伙伴们来探讨一下常用的非比较排序算法：计数排序，基数排序，桶排序。在一定条件下，它们的时间复杂度可以达到O(n)。
老读者可能比较熟悉，刚开始的时候写了一个排序算法系列，把常见的排序算法都写了，有兴趣的可以在公众号内的目录菜单栏中选择数据结构与算法查看。
综上，计数排序在特定场景下（如数据范围不大、整数类型）是一种快速且高效的排序选择，但其适用场景相对有限，且空间效率较低。
2、计数排序要求输入的数据必须是有确定范围的整数，因此计数排序法适用于量大范围小的数据。
计数排序是通过对待排序序列中的每种元素的个数进行计数，然后获得每个元素在排序后的位置的排序算法。即：对每一个输人元素 x，确定小于 x 的元素个数，然后就可以直接把 x 放到它在已排序数组中的位置上。
我们这里利用malloc开辟一个数组来统计相同元素出现的次数，用该数字下标表示相同元素，下标对应的值来统计次数 图示如下：
假设有这样子一个题：数组里有20个随机数，取值范围为从0到10，要求用最快的速度把这20个整数从小到大进行排序。
计数排序只适合使用在键的变化不大于元素总数的情况下。它通常用作另一种排序算法（基数排序）的子程序，这样可以有效地处理更大的键。
计数排序利用数组索引号的有序而对数据排序，所以，需要把原无序数组中的数据映射到排序数组的索引号上。于是，对排序数组的长度就会有一个最小值的约束，至少等于无序数组中的最大值加一。
将要排序的数据分到几个有序的桶里， 每个桶里的数据再单独进行排序。 桶内排完序之后，再把每个桶里的数据按照顺序依次取出， 组成的序列就是有序的了。
1、计数排序（Counting Sort） 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
之前写过一篇八种排序算法的博客，不过都是基于小数据量进行的排序，没有像这篇这样做大数据排序。文末会放出链接。
计数排序（Counting sort）是一种稳定的线性时间排序算法，其平均时间复杂度和空间复杂度为O(n+k)，其中n为数组元素的个数，k为待排序数组里面的最大值。同样具有线性时间排序的算法还有桶排序和基数排序，这一点不要搞混。
基数排序（Radix Sort）是一种非比较型的排序算法，它通过将待排序元素按照高位和低位的顺序依次进行排序，从而实现整体的排序效果。其基本步骤如下：
基数排序属于非比较排序算法类，故其时间复杂度不受比较排序算法时间复杂度下界的限制。基数排序对排序关键字的最低数位到最高数位中的每一数位采用其他排序算法进行排序。基数排序时间复杂度可以达到 （这中情况下对每一数位采用的排序算法为计数排序）。其中， 为待排序序列的排序关键字每一数位的最大范围，ddd 是排序关键字的数位数目。 计数排序要求每一数位排序所使用的排序算法都是稳定的，否则将影响计数排序的正确性。基数排序是稳定的，其原址性取决于对每一数位所使用的排序算法的原址性。
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。
需要注意的是线性排序算法是非基于比较的排序算法，都有使用限制才能达到线性排序的效果
基数序和计数排序一样无需进行比较和交换，和桶排序一样利用分布和收集两种基本操作进行排序。基数排序是把每一个元素拆成多个关键字，一个关键字可以在每一个元素上同等的位置进行计数排序，一个元素拆成多个关键字可以看作是要进行几轮分桶，以一个元素最长的长度为准。
计算机课上，老师给一串数字6 1 6 9 9 1 4 2 1 5 8 8,问道：这一串数字，你们写个程序给我看，要求效率较高。学不出来的别下课了。
✅作者简介：人工智能专业本科在读，喜欢计算机与编程，写博客记录自己的学习历程。 🍎个人主页：小嗷犬的博客 🍊个人信条：为天地立心，为生民立命，为往圣继绝学，为万世开太平。 🥭本文内容：C/C++ 计数排序 ---- C/C++ 计数排序 1.什么是计数排序 2.动图演示 3.C/C++代码实现 ---- 1.什么是计数排序 计数排序（Counting Sort）是一种非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。 计数排序的步骤如下： 找出待排
排序算法算是比较简单面试过程中遇到最多的算法，一般我们所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。
其实计数排序是桶排序的一种特殊情况。 桶排序的核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
首先，让我们先明确 COUNTING-SORT 算法的基本思想。COUNTING-SORT 是一种线性时间复杂度的排序算法，它适用于对一定范围内的整数进行排序。它的基本思想是，通过统计每个元素在待排序数组中出现的次数，然后根据这个次数将元素放到对应的位置上。
外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
桶排序、计数排序、基数排序 三种排序算法的时间复杂度是 O(n) 。因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。
终于来到了最后两个算法，非比较类的线性时间复杂度算法，计数排序和基数排序。上一篇也提到过，这几种排序算法理解起来都不难，时间、空间复杂度分析起来也很简单，但是对要排序的数据要求很苛刻，上一篇提到的桶排序就是适用于外部排序中，即所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
人到中年，容易变得油腻，思想懒惰，身体就容易发胖。为了摆脱中年油腻，不如和我一起学习算法来烧烧脑子，燃烧你的卡路里。
本系列为C++算法学习系列，会介绍 算法概念与描述，入门算法，基础算法，数值处理算法，排序算法，搜索算法，图论算法， 动态规划等相关内容。本文为排序部分。
计数排序，基数排序，桶排序是所有排序算法里面时间复杂度能达到O（N）级别的算法，这主要原因是因为他们不采用基于比较的算法，前面的文章已经介绍了计数排序的原理，本片文章我们来学习一下桶排序（Bucket sort)算法。
学过上一篇文章的计数排序之后，特别是归约化分治处理的计数排序（适用于较离散的非负整数序列）。计数排序的局限比较多，在排序之前需要解决负数和小数的问题，而桶排序不需要考虑这些。
我们知道快速排序的时间复杂度期望值是O(nlogn)，其中O(logn)是利用了二分法进行远距离比较和交换元素的位置。如果不去做比较交换计算，有没有可能有一种算法，它的时间复杂度期望值能降低到O(n)线性时间呢？
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
原题链接: http://oj.leetcode.com/problems/sort-colors/ 这道题也是数组操作的题目。事实上就是要将数组排序，仅仅是知道数组中仅仅有三个元素0,1,2。熟悉 计数排序 的朋友可能非常快就发现这事实上就是使用计数排序，元素空间仅仅须要三个元素就可以。代码例如以下：
计数排序属于非比较排序算法类，故其时间复杂度不受比较排序算法时间复杂度下界的限制，可以达到 。其中， 为待排序序列的排序关键字的最大范围。 计数排序是稳定的、非原址的。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
