什么叫程序？随着我们学习的不断进展，这个问题的答案不断有新的表述。
今天，我们学过了“流程”，也学过了“数据类型”。
“流程”表达某种动作或操作的过程；“数据”表达现实生活的事物。因此，程序自然可以表达为“通过流程控制，来对数据进行正确的处理”。其实这一句话，也可以用两个字来代替“算法”。
事实上有一个著名的公式，说：程序 = 数据结构 + 算法。
要想真正理解什么叫算法，最好的办法还是从我们的现实生活入手。
最常见的例子，就是给整理扑克牌了。给你一付打乱的扑克牌，然后让你把它们整理，就是让你排序。结果是：前四张是：黑桃A，红心A，草花A、方块A，然后是2，3……老K，最后是大小王两张。
这个过程使用的是“排序”算法。
更简单的，给你3张牌，让你找出其中最大的一张，这也需要一种算法。称为“求最值”。
你会说，这也算“算法”，3张牌往桌子上一摆，我“一眼”就能找出哪一张最大啊，我的大脑好像没有进行过任何计算。呵呵，这样说可就不对了。你把这三张牌往一头猪前面摆，摆上三年它也找不出哪一张是最大的。这可以证明，我们的大脑的确进行了一定的演算。
一套相同的算法，其实是连续的一段“流程控制”。可以用在不同的数据上。比如排序算法，我们可以用于整理扑克，也可以用于排出学员成绩的名次，而不这两样数据的数据结构是什么。但是一套算法在实现时，针对不同数据结构，有不同的实现。
这一章主要就是讲两种算法在数组上的实现，这两种算法是:“求最值”、“排序”。
18.1 求数组中的最大值
数组含有许多元素，这些元素如果是可以比较大小的，那就常常需要一种计算，求出这些元素中的最大值或最小值。求最值的算法应用在方方面面，比如：如何找出一条街上你喜欢的那某裙子最便宜卖的那家店。比如当早上第四节下课铃敲响后，如何找出从教室到食堂最近的一条路等等。
18.1.1 基本思路与实现
我想大家都知道了，一到要讲实例，我举的例子就是“成绩管理”。“烦不烦呢？”我看到有些同学使劲撇嘴。可不能烦啊，上一章的成绩管理中，“求成绩第一名”和“成绩排序”这样重要的功能还没实现呢。本章的作业就是它们了。
比如有这么一个数组，用于存储几个学生成绩。现在老师想找出其中的第一名。
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];
if(N > n[3])
N = n[3];
if(N > n[4])
N = n[4];
这可不叫“算法”。所以前面的表达并没有说出真正的算法。我们要改进它。
1、首先假设第一个数就是最大值，则 N = 2;
2、把N和下一个数比较，如果下一个数比N大，则让N等于该数;
3、重复第二步，直到没有下一个数。
明白了吗？算法就是这样而来的。第一，这三行话可以适用于无论多少个数求最大值的情况，这是你的算法是否正确的一个必要条件，如果你的算法表达的长短依赖于具体数据的个数，那么你的算法不是通用的算法，不管是否能解决问题。第二，我们在表达中看到了“如果”，看到“重复”，很好，“如果”就是“分支流程”，就是if或switch；而“重复”就是“循环流程”，是for 或 while 或 do...while。
int n[5] = {2,3,1,4,0};
int N = n[0];
for( int i = 1; i < 5; i++)
{
if(n[i] > N)
N = n[i];
}
循环从数组下标1开始，因为从算法的表述中，我们也看到了，N一开始就等于数组中的第一个数，而后和“下一个数”开始比较。
我们可以把代码改良，以让它方便于应用在任何个数的元素上。
int n[] = {2,3,1,4,0};
int N = n[0];
int count = sizeof(n) / sizeof(n[0]);
for( int i = 1; i < count; i++)
{
if (n[i] > N)
N = n[i];
}
18.1.2 实例
要求：
1、不使用数组，实现让用户输入10个数，然后输出其中最大值。
2、同1，但要求使用数组。
既然是两个小题，我们就分别写两个函数吧。
//不使用数组的例子:
void max1()
{
cout << "请输入10个数（每个数输入后加回车)" << endl;
int N,n;
cout << "第1个数：" :
cin >> N;
for(int i = 1; i<10; i++)
{
cout << "第" << i+1 << "个数:" ;
cin >> n;
if( n > N)
N = n;
}
cout << "最大值为：" << N << endl;
system("PAUSE"); //让控制台系统暂停。相当于我们以前的cin.get()或 getchar();
}
//使用数组的例子：
void max2()
{
cout << "请输入10个数（每个数输入后加回车)" << endl;
int n[10];
int N;
for(int i = 0; i<10; i++)
{
cout << "第" << i+1 << "个数：";
cin >> n[i];
}
N = n[0];
for(int i=1; i<10; i++)
{
if(n[i] > N)
N = n[i];
}
cout << "最大值为：" << N << endl;
system("PAUSE"); //让控制台系统暂停。
}
这样就完成了求最大值实例，如果是要求求最小值呢？改动仅在于那个if判断条件：
……
N = n[0]; //一开始假设第一个元素就是最小值
for(……）
{
if (n[i] < N) //如果有元素比我们假设的最小值还小，那就让最小值等于它吧
N = n[i];
}
……
这套题目我没有提供实际代码，大家找开CB自已完成吧。重要的是，在调通程序之后，认真地比较两种处理方法之间的异同。
结论应该是：“算法的抽象逻辑是一样的，只是用在于不同的数据结构上，会有不同的实现”。前者只使用简单的数据类型，所以它不得不在一边输入的情况下，一边求最大值；而后者采用了数组，所以可以从容地先完成输入工作，然后再求最大值。
当算法经较复杂时，采用良好的数据结构的重要性就开始体现，比如下面的排序，我们必须使用数组或其它更复杂的数据。否则就实现不了。
18.2 将数组元素排序
排序，一个经典教学课程。
排序，一个在超高频的实用算法。
第一点是说，我们必须去学。第二点是说，像这样一个实用算法以，事实上C,C++肯定都为我们写好了，以库函数等形式提供给我们使用，而且，这些写好的代码，肯定是最优秀的实现。
可是我们还是要学，而且是从最笨“冒泡算法”学起。所谓的最笨，是指效率差的。
学习的原因：1、前面说了，为了锻炼我们的逻辑思维。2、为了在某些时候，我们可以对排过程做更多的控制。
18.2.1 现实算法与程序算法的不同
大家都是这么整理扑克牌：把54张摊开放在桌面，然后不断地调整各张牌的位置，并把已经有序的牌放到另外一个位置。
生活中的各种算法一般不用考虑“内存”的问题。比如上面的问题，54牌每一张都要占用一点桌面，这算是固定需要的内存，而在“腾挪”各张牌，使之渐渐变得有序的过程中，还需要开辟新的空间，包括手里抓着的牌，即手心也算是一个内存。
程序排序，要求既要占用内存少，又要速度快。这是衡量一个算法是否优秀的两个基本点。
若是应用到人整理牌这一例子，则除了实现将54张牌按次序（牌值和牌花）排好以外，还需另有要求：
1、除了54张牌一开始占用的桌面，及你的一个手心以外，你在整理的过程中，不能让牌再占用新的桌面空间。
2、要求“比较两张牌大小”“交换两张的位置”等过程都尽量地少。
你可以拿出家里的扑克牌，现在就开始按上面的要求进行手工排序。也可以下载网站上的“扑克排序”的程序，通过它来模拟手工排序：鼠标点击某一张牌，该牌将移到当前的空位上。（正工学员下载课程包中已含该程序）
18.2.2 冒泡排序
“冒泡”是什么意思？湖底有时会冒出一个气泡，气泡刚在湖底时，是很小的，在向上浮的过程中，才一点地慢慢变大。学过高中的物理的人，应该不难解释这一现象。冒泡排序的过程有点类似这个过程，每前进一步，值就大一点。
排序当然有两个方向，一种是从小排到大，一种是从大排到小。大多数教科书里都讲第一种，我们也如此。这样一来，冒泡排序法就改为“沉泡法”了，较大值一点点跑到数组中的末尾。
一般教科书里也会说，冒泡排序法是人们最熟悉，及最直观的排序法，我可不这样认为。或许老外在生活中用的是这种最笨的排序法？我猜想，大家在生活中99%使用后面要讲的“选择”排序法。
冒泡排序是这么一个过程(从小到大):
1、比较相邻的两个元素，如果后面的比前面小，就对调二者。反复比较，到最后两个元素。结果，最大值就跑到了最末位置。
2、反复第一步，直到所有较大值都跑到靠后的位置。
看一眼例子：
2，5，1，4，3
第一遍：
·比较第一对相邻元素：2，5，发现后面的5并不比2小，所以不做处理。 序列保持不变：2，5，1，4，3
·继续比较后两对元素：5，1，发现后面的1比前面的5小，所以对调二者。现在，序列变为：2，1，5，4，3
·继续比较后两对元素：5，4……对调，于是：2，1，4，5，3
·继续比较后两对元素：5，3……对调，于是：2，1，4，3，5 <----- OK,现在最大值5跑到最尾处了。
大泡泡“5”浮出来了，但前面的2,1,4,3,还是没有排好，没事，再来一遍，不过，由于最后一个元素肯定是最大值了，所以我们这回只排到倒数第二个即可。
第二遍：
·比较第一对相邻元素：2，1，发现1比2小，所以对调：1,2,4,3,5
·继续比较后两对元素：2，4，不用处理，因为后面的数比较大。序列还是：1,2,4,3,5
·继续 4，3，对调：1,2,3,4,5。
前面说，5 不用再参加比较了。现在的序列是1，2，3，4，5。接下来，我们再来一遍：
第三遍：
·比较第一对相邻元素：1，2：不用对调。
……等等……
有人说，现在已经是1，2，3，4，5了，完全是排好序了啊，何必再来进行呢？我们确实是看出前面1，2，3也井然有序了，但对于程序来说，它只能明确地知道自己已经排好了两个数：4，5，并不知道的1，2，3凑巧也排好了。所以它必须再排两次，直到确认把3和2都已推到合适的位置上。最后剩一个数是1，因为只有一个数，没得比，所以这才宣告排序结束。
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
