啊哈!算法.pdf

第 1 章 一大波数正在靠近——排序 第 1章 一大波数正在靠近 排序 1 啊哈！算法 第 1 节 最快最简单的排序——桶排序 在我们生活的这个世界中到处都是被排序过的东东。站队的时候会按照身高排序，考试 的名次需要按照分数排序，网上购物的时候会按照价格排序，电子邮箱中的邮件按照时间排 序……总之很多东东都需要排序，可以说排序是无处不在。现在我们举个具体的例子来介绍 一下排序算法。 首先出场的是我们的主人公小哼，上面这个可爱的娃就是啦。期末考试完了老师要将同 学们的分数按照从高到低排序。小哼的班上只有 5 个同学，这 5 个同学分别考了 5 分、3 分、 5 分、2 分和 8 分，哎，考得真是惨不忍睹（满分是 10 分）。接下来将分数进行从大到小排 序，排序后是 8 5 5 3 2。你有没有什么好方法编写一段程序，让计算机随机读入5 个数然后 将这 5 个数从大到小输出？请先想一想，至少想 15 分钟再往下看吧（*^__^*）。 2 第 1 章 一大波数正在靠近——排序 我们这里只需借助一个一维数组就可以解决这个问题。请确定你真的仔细想过再往下 看哦。 首先我们需要申请一个大小为 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 分出现过了一次。 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”没有出现过，不打印。 最终屏幕输出“2 3 5 5 8 ”，完整的代码如下。 #include stdio.h