专栏首页编程理解排序算法(八):计数排序

排序算法(八):计数排序

计数排序是一种非比较性质的排序算法,元素从未排序状态变为已排序状态的过程,是由额外空间的辅助和元素本身的值决定的。计数排序过程中不存在元素之间的比较和交换操作,根据元素本身的值,将每个元素出现的次数记录到辅助空间后,通过对辅助空间内数据的计算,即可确定每一个元素最终的位置。

比较性质排序算法的时间复杂度有一个理论边界,即

个元素的序列,能够形成的所有排列个数为

,即该序列构成的决策树叶子节点个数为

,由叶子节点个数可知,决策树的高度为

,即由决策树根节点到叶子节点的比较次数为

,由斯特灵公式,

转换可得,比较性质的算法复杂度理论边界为

算法过程

  1. 根据待排序集合中最大元素和最小元素的差值范围,申请额外空间;
  2. 遍历待排序集合,将每一个元素出现的次数记录到元素值对应的额外空间内;
  3. 对额外空间内数据进行计算,得出每一个元素的正确位置;
  4. 将待排序集合每一个元素移动到计算得出的正确位置上。

演示示例

待排序集合:[3, -1, 2, 3, 1]

step 1:

序列中最大值为:

,最小值为:

,根据序列中最大值和最小值的差值范围,可得申请额外空间大小为:

step 2:

因为申请的额外空间足以将

之间的所有元素记录,所以将待排序集合中每一个元素都记录到额外空间上,例如元素 3,对应的记录位置下标为:

,即最后一个位置;元素 -1,对应的记录位置下标为:

,即第一个位置。

所有元素的出现次数和元素值记录如下,其中

表示该元素出现的次数,

表示元素值:

可以发现,计数排序的该过程,其实就是将待排序集合中的每个元素值本身大小作为下标,依次进行了存放。而记录的

次数,就是为了确定该元素值出现了几次。

step 3:

记录每个元素出现的次数,并对次数做计算,作用是当移动待排序集合元素到已排序集合中时,确保相同元素都被移动,且保持算法稳定性。因为额外空间中元素值是有序排列的,即额外空间的序列中每个元素,其元素的最终位置都是在前一个元素的后面,所以将其中每个元素的次数更新为加上前一个元素的次数和。例如元素 2 的最终位置在 元素 1 之后,而元素 1 只出现了 1 次,所以将元素 2 的

值更新为 3。

step 4:

根据额外空间已经确定的元素序列,移动待排序集合元素到已排序集合中。

算法示例

def countingSort(arr):  # the elements in the array are all integers
    maximum, minimum = max(arr), min(arr)
    countArr = [0] * (maximum - minimum + 1)
    for i in arr: # record the number of times of every element in the array
        countArr[i - minimum] += 1
    for i in range(1, len(countArr)): # calculate the position of every element
        countArr[i] += countArr[i-1]
    targetArr = [None] * len(arr)
    for i in range(len(arr)-1, -1, -1): # reverse-order traversal is for the stability
        countIndex = arr[i] - minimum
        targetArr[countArr[countIndex] - 1] = arr[i]
        countArr[countIndex] -= 1
    return targetArr

第一个循环用于在额外空间中记录每一个元素出现的次数,复杂度为

;第二个循环用于计算每一个元素的最终位置,复杂度为

为申请的额外空间大小;第三个循环用于移动待排序集合中元素到已排序集合的正确位置上,复杂度为

算法分析

由算法示例可知,计数排序的时间复杂度为

。因为算法过程中需要申请一个额外空间和一个与待排序集合大小相同的已排序空间,所以空间复杂度为

。由此可知,计数排序只适用于元素值较为集中的情况,若集合中存在最大最小元素值相差甚远的情况,则计数排序开销较大、性能较差。通过额外空间的作用方式可知,额外空间存储元素信息是通过计算元素与最小元素值的差值作为下标来完成的,若待排序集合中存在元素值为浮点数形式或其他形式,则需要对元素值或元素差值做变换,以保证所有差值都为一个非负整数形式。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 排序算法(一):冒泡排序

    冒泡排序是一种通过交换元素位置实现的稳定排序方式,其特点是每一轮排序后,都会在首端或尾端产生一个已排序元素,就像水泡不断上浮一样,通过多次排序,最终所有元素变得...

    zhipingChen
  • 排序算法(二):选择排序

    选择排序算法维护一个待排序集合和一个已排序集合,每轮迭代,从待排序集合中选择一个最小(最大)元素,添加到已排序集合中,通过多次迭代,最终完成排序。

    zhipingChen
  • 排序算法(九):桶排序

    桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中,也就是根据元素值特性将集合拆分为多个区域,则拆分后形成的多个桶,从值域上看是处于有序状态的。对每个桶中...

    zhipingChen
  • Java之异常处理

    Java异常处理 异常:异常就是Java程序在运行过程中出现的错误。 异常由来:问题也是现实生活中一个具体事务,也可以通过java 的类的形式进行描述,并封装成...

    二十三年蝉
  • java异常分类和处理

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    chenchenchen
  • 《Java从入门到放弃》JavaSE入门篇:异常

    十方上下
  • 感觉JVM的默认异常处理不够好,既然不好那我们就自己来处理异常呗!那么如何自己处理异常呢?

    * 如果程序出现了问题,我们没有做任何处理,最终JVM会做出默认的处理。 * 把异常的名称、原因及出现的位置等信息输出在控制台。同时会结束程序。 * ...

    黑泽君
  • 前端入门4-CSS属性样式表声明正文-CSS属性样式表

    作为一个前端小白,入门跟着这四个来源学习,感谢作者的分享,在其基础上,通过自己的理解,梳理出的知识点,或许有遗漏,或许有些理解是错误的,如有发现,欢迎指点下。

    请叫我大苏
  • Oracle sql loader 导数据时添加序号的三种方法

    1.用触发器和序列实现 CREATE SEQUENCE u.seq_questionno START WITH 0 MAXVALUE 9999999999999...

    用户1148526
  • 优先进行测试的 6 条原则

    有一次洗完之后,我看到蓬蓬乱乱的,就想着给梳顺了再吹,谁知道这梳子一下去怎么也梳不动,稍微使劲又拽着头发痛,我就犯嘀咕了,这不是刚洗完的头发应该丝滑般顺柔的么?

    sylan215

扫码关注云+社区

领取腾讯云代金券