计数排序(桶排序），scratch桶排序案例详解

计数排序（也叫桶排序），是编程程序中比较常见的排序方法之一，之前我们了解过选择排序、冒泡排序等，桶排序也是很他们并列的，也是处理数据排序的方法。那什么是计数排序(桶排序），在scratch中如何去运用呢？scratch桶排序通过案例详解，分享给大家：

什么是计数排序(桶排序）

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

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

scratch桶排序案例详解：

班级举办现场scratch编程比赛，有6个学员报名参加，作品采用10分制，经过评比，6个同学的最终得分是5分、4分、5分、3分、9分、4分，从大到小相序，排序后是9、5、5、4、4、3。

scratch桶排序案例效果

我们可以用上面学习过的选择排序或者冒泡排序来达到目标，也可以换一种思路来排序。作品采用10分制，也就是我们]知道作品可能的得分。

scratch桶排序案例思路分析：

我们现在从“原始得分”表中从第1个数据开始，分别统计1分获得者有多少人，2分获得者有多少人，3分获得者有多少人，4分获得者有多少人，…10分获得者有多少人。

我们先将表格初始化，也就是统计前对应得分人数都是0人。

第1个人得了5分，所以5分的得分人数增加1。

第2个人得了4分，所以4分的得分人数增加1。

第3个人得了5分，所以5分的得分人数增加1。

第4个人得了3分，所以3分的得分人数增加1。

第5个人得了9分，所以9分的得分人数增加1。

第6个人得了4分，所以4分的得分人数增加1。

由以上表述可以看到:

1分得分人数为0,表示“1”没有出现过。

2分得分人数为0，表示“2”没有出现过。

3分得分人数为1,表示“3″出现过1次，3需要保存到新的列表中1次；

4分得分人数为2，表示“4”出现过2次。4需要保存到新的列表中2次；

5分得分人数为2，表示”5″出现过2次。5需要保存到新的列表中2次；

6分得分人数为0，表示”6″没有出现过。

7分得分人数为0，表示7没有出现过。

8分得分入数为0，表示’8没有出现。

9分得分人数为1，表示”9″出现过1次。9需要保存到新的列表中1次；

10分得分人数为0， 表示10没有出。

以上就是计数排序的原理，由此可见:计数排序只适合于整数排序，并且整数的范围是明确的。

scratch桶排序案例编程代码步骤：

step1、建立一个“原始得分”数据列表，按序写入6个原始成绩，代码如下:

step2、再建立一个“统计得分”列表，初始值都为0；

桶排序列表值初始化

step3、从前往后遍历“原始数据列表”，并对应的改变“统计得分”列表的项目值。设置变量i，初始值为1；

将原始得分列表的数据，统计到统计得分表中

step4、再设立一个“排序后的得分”列表，来保存排序后的数据。代码如下：

排序后的得分代码

scratch算法相关的重要知识点