五分钟学会一个有意思的排序:计数排序

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画来描述常见的数据结构和算法。本系列包括十大排序、堆、队列、树、并查集、图等等大概几十篇。

你可以在公众号 五分钟学算法 获取更多排序内容

计数排序

计数排序是一种非基于比较的排序算法,其空间复杂度和时间复杂度均为O(n+k),其中k是整数的范围。基于比较的排序算法时间复杂度最小是O(nlogn)的。该算法于1954年由 Harold H. Seward 提出。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数

算法步骤

  1. 花O(n)的时间扫描一下整个序列 A,获取最小值 min 和最大值 max
  2. 开辟一块新的空间创建新的数组 B,长度为 ( max - min + 1)
  3. 数组 B 中 index 的元素记录的值是 A 中某元素出现的次数
  4. 最后输出目标整数序列,具体的逻辑是遍历数组 B,输出相应元素以及对应的个数

算法演示

排序动画过程解释

  1. 首先,扫描一下整个序列
  2. 获得最小值为 2 ,最大值为 7
  3. 新建数组包含 2~7 的元素
  4. 再次扫描序列,将序列的值放置在新建数组中
  5. 扫描数字 5,数组中 index 为 3 的值为 5,次数为 1
  6. 扫描数字 3,数组中 index 为 1 的值为 3,次数为 1
  7. 扫描数字 4,数组中 index 为 2 的值为 4,次数为 1
  8. 扫描数字 7,数组中 index 为 5 的值为 7,次数为 1
  9. 扫描数字 2,数组中 index 为 0 的值为 2,次数为 1
  10. 扫描数字 4,数组中 index 为 2 的值为 4,次数为 2
  11. 扫描数字 3,数组中 index 为 1 的值为 3,次数为 2
  12. 按照这种节奏,扫描结束后,新建数组中存放了整个序列以及每个数字出现的次数
  13. 最后输出目标整数序列
  14. 输出数字 2,同时数组中 index 为 0 的值为 2 的元素次数变为 0
  15. 输出数字 3,同时数组中 index 为 1 的值为 3 的元素次数变为 1
  16. 同样的操作,整个序列就完全输出了

代码实现

为了更好的让读者用自己熟悉的编程语言来理解动画,笔者将贴出多种编程语言的参考代码,代码全部来源于网上。

Go代码实现

Java代码实现

Python代码实现

JavaScript代码实现

如果你是iOS开发者,可以在GitHub上 https://github.com/MisterBooo/Play-With-Sort-OC 获取更直观可调试运行的源码。

你可以在公众号 五分钟学算法 获取更多排序内容

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小白的技术客栈

Python基础语法-内置数据结构概览

本文内容非常简单,主要介绍接下来要讲的内容。那就是Python的内置数据结构。今天只是简单介绍一下Python都有哪些内置数据结构,这样就可以循序渐进地进行学习...

3477
来自专栏小樱的经验随笔

【C#学习笔记之一】C#中的关键字

C#中的关键字 关键字是对编译器具有特殊意义的预定义保留标识符。它们不能在程序中用作标识符,除非它们有一个 @ 前缀。例如,@if 是有效的标识符,但 if 不...

4434
来自专栏软件开发 -- 分享 互助 成长

sizeof(结构体)的计算

摘要: 经常被计算结构体的sizeof给搞晕,于是找了个时间,静下心来,搞定它。 一、为什么结构体计算这么乱? 答案是字节对齐,计算机存储系统中以Byte为单位...

2919
来自专栏代码世界

Python之迭代器和生成器

迭代器 可迭代的数据类型: list   dic   str    set     tuple      f=open()--文件句柄      range  ...

38711
来自专栏沈唁志

PHP中系统函数http_build_query系统函数使用方法

1634
来自专栏机器学习算法与Python学习

python基础语法(1)

从今天起,将进行python的一个系列学习,从基本的语法学起,后期会推出一些关于web开发,网络爬虫以及用python的第三方库进行数据挖掘与机器学习等高级的开...

38514
来自专栏决胜机器学习

PHP数据结构(二十一) ——希尔排序

PHP数据结构(二十一)——希尔排序 (原创内容,转载请注明来源,谢谢) 一、概述 希尔排序,又称缩小增量排序,也属于插入排序类方法,时间上有较大改进。前面...

3407
来自专栏软件开发

C语言 第二章 数据类型、变量和输入函数

一、数据类型简介 在 C 语言中,数据类型指的是用于声明不同类型的变量或函数的一个广泛的系统。变量的类型决定了变量存储占用的空间,以及如何解释存储的位模式。 ?...

2335
来自专栏数说戏聊

SUBSTRING() 与 CONV() 函数1.substring()函数2.conv()函数

MySQL 字符串截取函数:left(), right(), substring(), substring_index()。

832
来自专栏小樱的经验随笔

1347 旋转字符串

1347 旋转字符串 基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题 S[0...n-1]是一个长度为n的字符串,定义旋转函数...

3468

扫码关注云+社区