在我们生活的这个世界中到处都是被排序过的东东。站队的时候会按照身高排序，考试的名次需要按照分数排序，网上购物的时候会按照价格排序，电子邮箱中的邮件按照时间排序……总之很多东东都需要排序，可以说排序是无处不在。之前介绍过冒泡排序，现在再介绍一种方便快捷的排序算法。
期末考试完了老师要将同学们的分数按照从高到低排序。小哼的班上只有5 个同学，这5 个同学分别考了5 分、3 分、5 分、2 分和8 分，哎考得真是惨不忍睹（满分是10 分）。接下来将分数进行从大到小排序，排序后是8 5 5 3 2。你有没有什么好方法编写一段程序，让计算机随机读入5 个数然后将这5 个数从大到小输出？请先想一想，至少想15 分钟再往下看吧(*^__^*) 。
我们这里只需借助一个一维数组就可以解决这个问题。（Scratch中可以用列表来模拟数组）请确定你真的仔细想过再往下看哦。首先我们需要申请一个大小为11 的数组int a[11]。OK，现在你已经有了11 个变量，编号从a[0]~a[10]。刚开始的时候，我们将a[0]~a[10]都初始化为0，表示这些分数还都没有人得过。例如a[0]等于0 就表示目前还没有人得过0 分，同理a[1]等于0 就表示目前还没有人得过1 分……a[10]等于0 就表示目前还没有人得过10 分。
下面开始处理每一个人的分数，第一个人的分数是5 分，我们就将相对应的a[5]的值在原来的基础增加1，即将a[5]的值从0 改为1，表示5 分出现过了一次。
第二个人的分数是3 分，我们就把相对应的a[3]的值在原来的基础上增加1，即将a[3]的值从0 改为1，表示3 分出现过了一次。
注意啦！第三个人的分数也是5 分，所以a[5]的值需要在此基础上再增加1，即将a[5]的值从1 改为2，表示5 分出现过了两次。
按照刚才的方法处理第四个和第五个人的分数。最终结果就是下面这个图啦。
你发现没有，a[0]~a[10]中的数值其实就是0 分到10 分每个分数出现的次数。接下来，我们只需要将出现过的分数添加到新列表顺序就排好啦具体如下。
a[0]为0，表示“0”没有出现过，不添加。
a[1]为0，表示“1”没有出现过，不添加。
a[2]为1，表示“2”出现过1 次，添加2。
a[3]为1，表示“3”出现过1 次，添加3。
a[4]为0，表示“4”没有出现过，不添加。
a[5]为2，表示“5”出现过2 次，添加5 5。
a[6]为0，表示“6”没有出现过，不添加。
a[7]为0，表示“7”没有出现过，不添加。
a[8]为1，表示“8”出现过1 次，添加8。
a[9]为0，表示“9”没有出现过，不添加。
a[10]为0，表示“10”没有出现过，不添加。
输入数据为：5 3 5 2 8
这个算法就好比有11 个桶，编号从0~10。每出现一个数，就在对应编号的桶中放一个小旗子，最后只要数数每个桶中有几个小旗子就OK 了。例如2 号桶中有1 个小旗子，表示2 出现了一次；3 号桶中有1 个小旗子，表示3 出现了一次；5 号桶中有2 个小旗子，表示5出现了两次；8 号桶中有1 个小旗子，表示8 出现了一次。
可以看出桶排序很好理解，而且算法复杂度也很低，但是如果最大数是10000的化就要开10000个空间数组，很有可能这10000个空间里只用到几百个，浪费的空间比较多，所以适用在最大数比较小的情况，如年龄的排序（不会超过150），如成绩的排序等。
由于Scratch列表下标索引是从1开始，脚本如下：
Python 程序实现桶排序
# 桶排序 样例输入 5 3 5 2 8 输出2 3 5 5 8
def cask_sort(nums):
casks = [0 for i in range(10)] # 初始化数组（开辟存数字的桶） 数组（0-9）下标 存入的都是0
for i in nums: # 遍历每一个输入的数
casks[i] = casks[i] + 1 # 把数放入相应的桶中 某个数出现几次 相应的桶中就是几
for index, value in enumerate(casks): # index 代表桶的序号 n 代表 相应序号桶里的值
if value > 0: # 如果相应序号桶里的值>0
for n in range(value): # 输出对应桶序号几次
print(index, end=' ')
if __name__ == '__main__':
nums = [5, 3, 5, 2, 8] # 待排序的数组
cask_sort(nums)
0 评论 最近
没有评论！