第十八章数组(三) 数组的最值与排序 18.1求数组中的最大值 18.1.1基本思路与实现 18.1.2实例 18.2将数组元素排序 18.2.1现实算法与程序算法的不同 18.2.2冒泡排序 18.2.3选择排序 18.2.4快速排序(选修) 18.3小结 什么叫程序?随着我们学习的不断进展,这个问题的答案不断有新的表述 今天,我们学过了“流程”,也学过了“数据类型 “流程”表达某种动作或操作的过程:“数据”表达现实生活的事物。因此,程序自然可以 达为“通过流程控制,来对数据进行正确的处理”。其实这一句话,也可以用两个字来代替 “算法”。 事实上有一个著名的公式,说:程序=数据结构+算法。 要想真正理解什么叫算法,最好的办法还是从我们的现实生活入手 最常见的例子,就是给整理扑克牌了。给你一付打乱的扑克牌,然后让你把它们整理,就是 让你排序。结果是:前四张是:黑桃A,红心A,草花A、方块A,然后是2,3……老K,最后 是大小王两张 这个过程使用的是“排序”算法。 更简单的,给你3张牌,让你找出其中最大的一张,这也需要一种算法。称为“求最值
第十八章 数组（三） ---- 数组的最值与排序 18.1 求数组中的最大值 18.1.1 基本思路与实现 18.1.2 实例 18.2 将数组元素排序 18.2.1 现实算法与程序算法的不同 18.2.2 冒泡排序 18.2.3 选择排序 18.2.4 快速排序 （选修） 18.3 小结 什么叫程序？随着我们学习的不断进展，这个问题的答案不断有新的表述。 今天，我们学过了“流程”，也学过了“数据类型”。 “流程”表达某种动作或操作的过程；“数据”表达现实生活的事物。因此，程序自然可以 表达为“通过流程控制，来对数据进行正确的处理”。其实这一句话，也可以用两个字来代替 “算法”。 事实上有一个著名的公式，说：程序 = 数据结构 + 算法。 要想真正理解什么叫算法，最好的办法还是从我们的现实生活入手。 最常见的例子，就是给整理扑克牌了。给你一付打乱的扑克牌，然后让你把它们整理，就是 让你排序。结果是：前四张是：黑桃 A，红心 A，草花 A、方块 A，然后是 2，3……老 K，最后 是大小王两张。 这个过程使用的是“排序”算法。 更简单的，给你 3 张牌，让你找出其中最大的一张，这也需要一种算法。称为“求最值
你会说,这也算“算法”,3张牌往桌子上一摆,我“一眼”就能找出哪一张最大啊,我的 大脑好像没有进行过任何计算。呵呵,这样说可就不对了。你把这三张牌往一头猪前面摆,摆 上三年它也找不出哪一张是最大的。这可以证明,我们的大脑的确进行了一定的演算 一套相同的算法,其实是连续的一段“流程控制”。可以用在不同的数据上。比如排序算法, 我们可以用于整理扑克,也可以用于排出学员成绩的名次,而不这两样数据的数据结构是什么 但是一套算法在实现时,针对不同数据结构,有不同的实现。 这一章主要就是讲两种算法在数组上的实现,这两种算法是:“求最值”、“排序 18.1求数组中的最大值 数组含有许多元素,这些元素如果是可以比较大小的,那就常常需要一种计算,求出这些元 素中的最大值或最小值。求最值的算法应用在方方面面,比如:如何找出一条街上你喜欢的那 某裙子最便宜卖的那家店。比如当早上第四节下课铃敲响后,如何找出从教室到食堂最近的 条路等等 18.1.1基本思路与实现 我想大家都知道了,一到要讲实例,我举的例子就是“成绩管理”。“烦不烦呢?”我看到 有些同学使劲撇嘴。可不能烦啊,上一章的成绩管理中,“求成绩第一名”和“成绩排序”这 样重要的功能还没实现呢。本章的作业就是它们了。 比如有这么一个数组,用于存储几个学生成绩。现在老师想找出其中的第一名 int cj[]={80,67,76,87,78}
你会说，这也算“算法”，3 张牌往桌子上一摆，我“一眼”就能找出哪一张最大啊，我的 大脑好像没有进行过任何计算。呵呵，这样说可就不对了。你把这三张牌往一头猪前面摆，摆 上三年它也找不出哪一张是最大的。这可以证明，我们的大脑的确进行了一定的演算。 一套相同的算法，其实是连续的一段“流程控制”。可以用在不同的数据上。比如排序算法， 我们可以用于整理扑克，也可以用于排出学员成绩的名次，而不这两样数据的数据结构是什么。 但是一套算法在实现时，针对不同数据结构，有不同的实现。 这一章主要就是讲两种算法在数组上的实现，这两种算法是:“求最值”、“排序”。 18.1 求数组中的最大值 数组含有许多元素，这些元素如果是可以比较大小的，那就常常需要一种计算，求出这些元 素中的最大值或最小值。求最值的算法应用在方方面面，比如：如何找出一条街上你喜欢的那 某裙子最便宜卖的那家店。比如当早上第四节下课铃敲响后，如何找出从教室到食堂最近的一 条路等等。 18.1.1 基本思路与实现 我想大家都知道了，一到要讲实例，我举的例子就是“成绩管理”。“烦不烦呢？”我看到 有些同学使劲撇嘴。可不能烦啊，上一章的成绩管理中，“求成绩第一名”和“成绩排序”这 样重要的功能还没实现呢。本章的作业就是它们了。 比如有这么一个数组，用于存储几个学生成绩。现在老师想找出其中的第一名。 int cj[] = {80,67,76,87,78};
我们还是一眼“找”出了结果:87。但如果不是5个成绩,而是5万个成绩呢(比如首钢的 工人进行考试的结果)?我们就不能一眼看出,而是不断地从一个个成绩里搜寻那个最大值。 不管是5万还是5个,其实算法是一样的。 冰心老奶奶举了个例子:同样是从动物园回来,有的小学生写出让你如临其境的作文,而有 的小学生则像是没有去过动物园一样,写得干巴巴的。 在把你的解决问题的思路转化为程序代码的过程中,显然第一步应该做是你能够用自然语言 清楚地,准确地表达出你的思路。有些人能做好这一点,而有些人则表达得相当困难,仿佛他 不会解决问题。 当然这是一个双向锻炼的过程,如果你原来在这方面不擅长,跟着我在这里学习编程,慢慢 的你会发现自已不仅学会也写程序,而且学会了如何表达自己的想法、思路、情感……很多人 说学习编程是一件快乐的事,很多人沉迷于编程,其中的一点奥妙,他们都不肯“泄密”,我 泄密了。 言归正传。大家提起精神来! 求最大值是一个“比较”的过程。我们就说5个数的情况,看看如何找出5个数中的最大值: 为了方便表达,我们用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不变
我们还是一眼“找”出了结果：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行?按照它的表达,我们写成的代码是: intn[5]={2,3,1,4,0} int N=n[0]: if(N>n[1]) N=n[1 if(N>n[2]) if(N>n[3]) N=n[3] f(N>n[4]) N=n[4] 这可不叫“算法”。所以前面的表达并没有说出真正的算法。我们要改进它。 1、首先假设第一个数就是最大值,则N=2; 2、把N和下一个数比较,如果下一个数比N大,则让N等于该数 3、重复第二步,直到没有下一个数。 明白了吗?算法就是这样而来的。第一,这三行话可以适用于无论多少个数求最大值的情况, 这是你的算法是否正确的一个必要条件,如果你的算法表达的长短依赖于具体数据的个数,那 么你的算法不是通用的算法,不管是否能解决问题。第二,我们在表达中看到了“如果”,看 到“重复”,很好,“如果”就是“分支流程”,就是if或 switch:而“重复”就是“循环 流程”,是for或 while或do.. while intn[5]={2,3,1,4,0}
求五个数的最大值，我们用了五行话表达，如果求 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 for( int i=1:i N) 循环从数组下标1开始,因为从算法的表述中,我们也看到了,N一开始就等于数组中的第 个数,而后和“下一个数”开始比较。 我们可以把代码改良,以让它方便于应用在任何个数的元素上。 intn[]={2,3,1,4,0} nt N=n[oj int count sizeof(n)/ sizeof(n[Ol) for( int i =1:iN) N=nli] 18.1.2实例 要求
int N = n[0]; for( int i = 1; 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 N) N = n[i]; } 18.1.2 实例 要求：
1、不使用数组,实现让用户输入10个数,然后输出其中最大值 2、同1,但要求使用数组。 既然是两个小题,我们就分别写两个函数吧。 //不使用数组的例子 void max1 o cout>N for(int i =1: 1>n if(n>N cout<<"最大值为:"<<N<<endl; system(" PAUSE");//让控制台系统暂停。相当于我们以前的cin.getO或 getchar0
1、不使用数组，实现让用户输入 10 个数，然后输出其中最大值。 2、同 1，但要求使用数组。 既然是两个小题，我们就分别写两个函数吧。 //不使用数组的例子: void max1() { cout > N; for(int i = 1; i> n; if( n > N) N = n; } cout << "最大值为：" << N << endl; system("PAUSE"); //让控制台系统暂停。相当于我们以前的 cin.get()或 getchar(); }
//使用数组的例子 void max2O cout N cout<<"最大值为:"<<N<<endl system(" PAUSE");//让控制台系统暂停。 这样就完成了求最大值实例,如果是要求求最小值呢?改动仅在于那个if判断条件:
//使用数组的例子： void max2() { cout > n[i]; } N = n[0]; for(int i=1; i N) N = n[i]; } cout << "最大值为：" << N << endl; system("PAUSE"); //让控制台系统暂停。 } 这样就完成了求最大值实例，如果是要求求最小值呢？改动仅在于那个 if 判断条件： ……
N=n[O];//一开始假设第一个元素就是最小值 for if(n[i]<N)〃/如果有元素比我们假设的最小值还小,那就让最小值等于它吧 N=nli]: 这套题目我没有提供实际代码,大家找开CB自已完成吧。重要的是,在调通程序之后,认 真地比较两种处理方法之间的异同。 结论应该是:“算法的抽象逻辑是一样的,只是用在于不同的数据结构上,会有不同的实现”。 前者只使用简单的数据类型,所以它不得不在一边输入的情况下,一边求最大值:而后者采用 了数组,所以可以从容地先完成输入工作,然后再求最大值 当算法经较复杂时,采用良好的数据结构的重要性就开始体现,比如下面的排序,我们必须 使用数组或其它更复杂的数据。否则就实现不了。 18.2将数组元素排序 排序,一个经典教学课程 排序,一个在超高频的实用算法。 第一点是说,我们必须去学。第二点是说,像这样一个实用算法以,事实上C,C++肯定都为 我们写好了,以库函数等形式提供给我们使用,而且,这些写好的代码,肯定是最优秀的实现。 可是我们还是要学,而且是从最笨“冒泡算法”学起。所谓的最笨,是指效率差的 学习的原因:1、前面说了,为了锻炼我们的逻辑思维。2、为了在某些时候,我们可以对排 过程做更多的控制
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.22冒泡排序 “冒泡”是什么意思?湖底有时会冒出一个气泡,气泡刚在湖底时,是很小的,在向上浮的 过程中,才一点地慢慢变大。学过高中的物理的人,应该不难解释这一现象。冒泡排序的过程 有点类似这个过程,每前进一步,值就大一点。 排序当然有两个方向,一种是从小排到大,一种是从大排到小。大多数教科书里都讲第一种, 我们也如此。这样一来,冒泡排序法就改为“沉泡法”了,较大值一点点跑到数组中的末尾
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<---0K,现在最大值5跑 到最尾处了。 大泡泡“5”浮出来了,但前面的2,1,4,3,还是没有排好,没事,再来一遍,不过,由于最 后一个元素肯定是最大值了,所以我们这回只排到倒数第二个即可。 比较第一对相邻元素:2,1,发现1比2小,所以对调:1,2,4,3,5
一般教科书里也会说，冒泡排序法是人们最熟悉，及最直观的排序法，我可不这样认为。或 许老外在生活中用的是这种最笨的排序法？我猜想，大家在生活中 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