第十八章 数组（三） ---- 数组的最值与排序.doc

第十八章数组(三) ---- 数组的最值与排序

求数组中的最大值
  基本思路与实现
  实例
将数组元素排序
  现实算法与程序算法的不同
  冒泡排序
  选择排序
  快速排序(选修)
小结

什么叫程序?随着我们学****的不断进展,这个问题的答案不断有新的表述。
今天,我们学过了“流程”,也学过了“数据类型”。
“流程”表达某种动作或操作的过程;“数据”表达现实生活的事物。因此,程序自然可以表达为“通过流程控制,来对数据进行正确的处理”。其实这一句话,也可以用两个字来代替“算法”。
事实上有一个著名的公式,说:程序= 数据结构+ 算法。

要想真正理解什么叫算法,最好的办法还是从我们的现实生活入手。

最常见的例子,就是给整理***牌了。给你一付打乱的***牌,然后让你把它们整理,就是让你排序。结果是:前四张是:黑桃A,红心A,草花A、方块A,然后是2,3……老K,最后是大小王两张。 
这个过程使用的是“排序”算法。

更简单的,给你3张牌,让你找出其中最大的一张,这也需要一种算法。称为“求最值”。
你会说,这也算“算法”,3张牌往桌子上一摆,我“一眼”就能找出哪一张最大啊,我的大脑好像没有进行过任何计算。呵呵,这样说可就不对了。你把这三张牌往一头猪前面摆,摆上三年它也找不出哪一张是最大的。这可以证明,我们的大脑的确进行了一定的演算。

一套相同的算法,其实是连续的一段“流程控制”。可以用在不同的数据上。比如排序算法,我们可以用于整理***,也可以用于排出学员成绩的名次,而不这两样数据的数据结构是什么。但是一套算法在实现时,针对不同数据结构,有不同的实现。

这一章主要就是讲两种算法在数组上的实现,这两种算法是:“求最值”、“排序”。

求数组中的最大值
数组含有许多元素,这些元素如果是可以比较大小的,那就常常需要一种计算,求出这些元素中的最大值或最小值。求最值的算法应用在方方面面,比如:如何找出一条街上你喜欢的那某裙子最便宜卖的那家店。比如当早上第四节下课铃敲响后,如何找出从教室到食堂最近的一条路等等。
基本思路与实现
我想大家都知道了,一到要讲实例,我举的例子就是“成绩管理”。“烦不烦呢?”我看到有些同学使劲撇嘴。可不能烦啊,上一章的成绩管理中,“求成绩第一名”和“成绩排序”这样重要的功能还没实现呢。本章的作业就是它们了。

比如有这么一个数组,用于存储几个学生成绩。现在老师想找出其中的第一名。

int cj[] = {80,67,76,87,78};

我们还是一眼“找”出了结果:87。但如果不是5个成绩,而是5万个成绩呢(比如首钢的工人进行考试的结果)?我们就不能一眼看出,而是不断地从一个个成绩里搜寻那个最大值。不管是5万还是5个,其实算法是一样的。

冰心老奶奶举了个例子:同样是从动物园回来,有的小学生写出让你如临其境的作文,而有的小学生则像是没有去过动物园一样,写得干巴巴的。

在把你的解决问题的思路转化为程序代码的过程中,显然第一步应该做是你能够用自然语言清楚地,准确地表达出你的思路。有些人能做好这一点,而有些人则表达得相当困难,仿佛他不会解决问题。

当然这是一个双向锻炼的过程,如果你原来在这方面不擅长,跟着我在这里学****编程,慢慢的你会发现自已不仅学会也写程序,而且学会了如何表达自已的想法、思路、情感……很多人说学****编程是一件快乐的事,很多人沉迷于编程,其中的一点奥妙,他们都不肯“泄密”,我泄密了。

言归正传。大家提起精神来!

求最大值是一个“比较”的过程。我们就说5个数的情况,看看如何找出5个数中的最大值:

2、3、1、4、0

为了方便表达,我们用 N 来表示最大值。

1、首先假设第一个数就是最大值,则 N = 2;
2、把N和第二个数比较,发现 3 比 N 大,于是让 N = 3;
3、把N和第三个数比较,发现 1 不比 N 大,于是N不变。
4、把N和第四个数比较,发现 4 比 N 大,于是让 N = 4;
5、把N和第五个数比较,发现 0 不比 N 大,于是N不变;

求五个数的最大值,我们用了五行话表达,如果求100个数的最值呢?要比较99次,岂不是要写100行?按照它的表达,我们写成的代码是:

int n[5] = {2,3,1,4,0};

int N = n[0];

if(N > n[1])
  N = n[1];
if(N > n[2])
  N = n[2]