排序算法七:计数排序

马谦马谦马谦 数据结构和算法评论430字数 758阅读2分31秒阅读模式

一、计数排序

其基本思想为:假设n个输入的元素中的每一个都是在0到k之间的一个整数,对于每一个输入元素x,确定小于x的元素个数,直接把x放在它输出的数组中的位置上。例如有17个元素小于x,则x就应该在数组的第18个位置上。当有几个元素相同时,这一方案就要略作修改,不能都放在同一个位置上。

计数排序需要提供两个辅助数组用来计数,一个用来保存已经排好序的元素,一个用来保存每个元素在数组中出现的次数。计数排序是不稳定的排序算法,时间复杂度(n),空间复杂度是O(n + k),其中k是排序数组元素的范围。

例如以下数组A:

排序算法七:计数排序-图片1

在通过计数后,得到的辅助数组C为:

排序算法七:计数排序-图片2

对于元素1而言,它前面有两个0,因此排序后它的位置在第三个,即下标为2的位置上,但是它的数量为0,就不应该给他排序。而元素2是有的,它的位置应该是0的数量和1的数量(如果有元素1的话)之和的后面一位,在这里是第3位,下标为2。这里类似斐波那契数列:每个元素都等于前面两个的和。

因此,有必要对辅助数组C做处理,设置其所在的位置为前面所有元素数量之和,这样就不用每次都重新计算前面的数量了(参考斐波那契数列计算):

排序算法七:计数排序-图片3

要注意的是,对于2这个元素来说,它出现了两次,如果不做特殊处理,它们处的位置都是第四个位置。要想办法把两个2分别放到自己合适的位置上去。可以采取的办法是从后往前排序,每排完一个数字,当前数字的值减一。

图例:

第一步,A的最后一个元素是3,得到C[3]的值为7,把3先放到第7个位置,并把C[3]的值减一:

排序算法七:计数排序-图片4

第二步,现在A的最后一个元素(未排序的)是0,得到C[0]为2,放到第二个位置,C[0]减一:

排序算法七:计数排序-图片5

第三步,重复以上步骤,直到A中所有的元素都排序完毕:

排序算法七:计数排序-图片6

此时,整个数组就是有序的了。

二、计数排序的代码实现

 最后更新:2020-2-7
马谦马谦马谦
  • 本文由 马谦马谦马谦 发表于 2019年4月27日11:20:14
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/count-sort.html
排序算法四:梳排序 数据结构和算法

排序算法四:梳排序

一、梳排序简介 梳排序是冒泡排序的一种优化方案,主要是为了解决冒泡排序中的尾部小数值问题。它主要的思想是通过比较元素和固定步长位置上的数据,先进行部分优化,然后逐步减少步长,以此来对数据进行预处理。 ...
排序算法五:堆排序 数据结构和算法

排序算法五:堆排序

一、堆排序原理 通过最大堆的性质可以知道:一个堆中最大的元素总是在堆顶的,即数组下标0的位置。基于这一点,我们可以每次都把堆中的最大值提取出来,放到当前数组的后面。然后重新构建最大堆,重复这个过程,以...
排序算法三:冒泡排序 数据结构和算法

排序算法三:冒泡排序

一、原理 冒泡排序的原理很简单, 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从从Z到A)错误就把他们交换过来。 冒泡排序是一种稳定的排序算法。 冒泡排序不管在什...
排序算法二:选择排序 数据结构和算法

排序算法二:选择排序

一、原理 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找...
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证