第18章 数组.docx

第18章 数组.docx

《第18章 数组.docx》由会员分享，可在线阅读，更多相关《第18章 数组.docx（26页珍藏版）》请在冰点文库上搜索。

第18章数组

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

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基本思路与实现

我想大家都知道了，一到要讲实例，我举的例子就是“成绩管理”。

“烦不烦呢？

”我看到有些同学使劲撇嘴。

可不能烦啊，上一章的成绩管理中，“求成绩第一名”和“成绩排序”这样重要的功能还没实现呢。

本章的作业就是它们了。

比如有这么一个数组，用于存储几个学生成绩。

现在老师想找出其中的第一名。

intcj[]={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行？

按照它的表达，我们写成的代码是：

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

intN=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。

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

intN=n[0];

for（inti=1;i<5;i++）

{

  if（n[i]>N）

    N=n[i];

}

循环从数组下标1开始，因为从算法的表述中，我们也看到了，N一开始就等于数组中的第一个数，而后和“下一个数”开始比较。

我们可以把代码改良，以让它方便于应用在任何个数的元素上。

intn[]={2,3,1,4,0};

intN=n[0];

intcount=sizeof（n）/sizeof（n[0]）;

for（inti=1;i

{

  if（n[i]>N）

    N=n[i];

}

18.1.2实例

要求：

1、不使用数组，实现让用户输入10个数，然后输出其中最大值。

2、同1，但要求使用数组。

既然是两个小题，我们就分别写两个函数吧。

//不使用数组的例子:

voidmax1（）

{

 cout<<"请输入10个数（每个数输入后加回车）"<

 intN,n;

 cout<<"第1个数：

":

 cin>>N;

 for（inti=1;i<10;i++）

 {

     cout<<"第"<

";

     cin>>n;

     if（n>N）

        N=n;

 }

 cout<<"最大值为：

"<

 system（"PAUSE"）; //让控制台系统暂停。

相当于我们以前的cin.get（）或getchar（）;

}

//使用数组的例子：

voidmax2（）

{

  cout<<"请输入10个数（每个数输入后加回车）"<

  intn[10];

  intN;

  for（inti=0;i<10;i++）

  {

     cout<<"第"<

";

     cin>>n[i];

  }

  N=n[0];

  for（inti=1;i<10;i++）

  {

    if（n[i]>N）

      N=n[i];

  }

 cout<<"最大值为：

"<

 system（"PAUSE"）; //让控制台系统暂停。

}

这样就完成了求最大值实例，如果是要求求最小值呢？

改动仅在于那个if判断条件：

……

N=n[0];//一开始假设第一个元素就是最小值

for（……）

{

 if（n[i]

     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，因为只有一个数，没得比，所以这才宣告排序结束。

那么到底要排几遍？

看一看前面的“第一遍”、“第二遍”的过程你可发现，每进行一遍，可以明确地将一个当前的最大值推到末尾，所以如果排Count个数，则应排Count遍。

当然，最后一遍是空走，因为仅剩一个元素，没得比较。

下面就动手写冒泡排序法的函数。

写成函数是因为我们希望这个排序法可处理任意个元素的数组。

//冒泡排序（从小到大）：

//num:

要接受排序的数组

//count:

该数组的元素个数

voidbubble（intnum[],intcount）

{

   inttmp;

   //要排Count个数，则应排Count遍：

   for（inti=0;i

   {

      for（intj=0;j

      {

          //比较相邻的两个数：

          if（num[j+1]

          {

              //对调两个数，需要有"第三者"参以

              tmp=num[j+1];

              num[j+1]=num[j];

              num[j]=tmp;

          }

      }

   }     

}

注意在内层循环中j的结束值是count-i-1。

要理解这段代码，明白为什么结束在count-i-1？

如果你忘了如何在CB进行代码调试，如果设置断点，如何单步运行，如何观察变量的值，那么你需要“严重”复习前面有关“调试”的章节；如果你一直是高度着每一章的程序到现在，那么你可以继续下面的内容。

排序函数写出一个了，如何调试这个函数？

在CB里新建一空白控制台程序，然后在主函数里，让我们写一些代码来调用这个函数，并且观察排序结果。

#include

……

voidbubble（intnum[],intcount）

{

 ……

}

intmain（）//我实在有些懒得写main里两个参数，反正它们暂时对我们都没有用，

          //反正CB会为你自动生成，所以从此刻起，我不写了,除非有必要。

{

   intvalues[]={2,5,1,4,3};

   intcount=sizeof（values[]）/sizeof（values[0]）;

   bubble（value,sizeof）;

}

你要做的工作是单步跟踪上面的代码，看看整个流程是不是像我前面不厌其烦的写的“第一遍第二遍第三遍”所描述的。

完成上面的工作了吗？

全部过程下来，只花20分钟应该算是速度快或者不认真的了（天知道你是哪一种？

天知道你到底是不是没有完成就来骗我？

）。

现在让这个程序有点输出。

我们加一个小小的函数：

//输出数组的元素值

//num:

待输出的数组

//count:

元素个数

voidprintArray（intnum[],intcount）

{

 for（inti=0;i

 {

    count<

 }

 cout<

}

把这个函数加到main（）函数头之前，然后我们用它来输出：

intmain（）//我实在有些懒得写main里两个参数，反正它们暂时对我们都没有用，

          //反正CB会为你自动生成，所以从此刻起，我不写了,除非有必要。

{

   intvalues[]={2,5,1,4,3};

   intcount=sizeof（values[]）/sizeof（values[0]）;

   cout<<"排序之前：

"<

   printArray（values,count）;

   //冒泡排序：

   bubble（value,sizeof）;

   cout<<"排序之后:

" <

   printArray（values,count）;

   system（"PAUSE"）;

}

后面要讲的其它排序法也将用这个printArray（）来作输出。

冒泡排序是效率最差劲的方法（速度慢），不过若论起不另外占用内存，则它当属第一。

在交换元素中使用了一个临时变量（第三者），还有两个循环因子i和j，这些都属于必须品，其它的它一个变量也没多占。

我们现在讲讲如何避免数据其实已经排好，程序仍然空转的的局面。

首先要肯定一点，至少一遍的空转是不可避免的，这包括让人来排，因为你要发现结果已是1，2，3，4，5了，你也是用眼睛从头到尾抄了一遍（如果你视力不好，说不定还要扫两遍呢）。

接下来一点，我们来看看除了第一遍空转，后面的是否可以避免。

冒泡排序法的空转意味着什么？

因为算法是拿相邻的两个比较，一发现次序不合“从小到大”的目的（小的在大的后头），就进行对调。

所以如果这个对调一次也没有进行，那就说明后面的元素必然是已经完全有序了，可以放心地结束。

让我们来加个变量，用于标志刚刚完成的这一遍是否空转，如果是空转，就让代码跳出循环。

//冒泡排序（从小到大，且加了空转判断）：

voidbubble（intnum[],intcount）

{

   inttmp;

   boolswapped; //有交换吗？

   //要排Count个数，则应排Count遍：

   for（inti=0;i

   {

      //第一遍开始之前，我们都假充本遍可能没有交换（空转）：

      swapped=false;

      for（intj=0;j

      {

          //比较相邻的两个数：

          if（num[j+1]

          {

              swapped=true; //还是有交换

              //对调两个数，需要有"第三者"参以

              tmp=num[j+1];

              num[j+1]=num[j];

              num[j]=tmp;

          }

      }

      if（!

swapped）

         break;

   }     

}

加了swapped标志，这个算法也快不了多少，甚至会慢也有可能。

冒泡排序还有一些其它的改进的可能，但同样作用不大，并且会让其丧失仅有优点“代码简单直观”。

所以我个人认为真有需要使用冒泡排序时，仅用最原汁原味的“泡”就好。

必竟，你选择了冒泡算法，就说明你对本次排序的速度并无多高的要求。

对于n个元素，原汁原味的“冒泡排序”算法要做的比较次数是固定的：

（n -1）*n/2次的比较。

交换次数呢？

如果一开始就是排好序的数据，则交换次数为0。

一般情况下为3*（n-1）*n/4;最惨时（逆序）为3* （n-1）*n/2。

冒完泡以后——情不自禁看一眼窗台罐头瓶里那只胖金鱼——让我们开始中国人最直观的选择排序法吧。

对了，补一句，如果你看到有人在说“上推排序”，那么你要知道，“上推排序”是“冒泡排序”的另一种叫法，惟一的区别是：

它不会让我们联想到金鱼。

18.2.3选择排序

本章前头我们讲了“求最值”的算法，包括最大值和最小值。

其实，有了求最值的算法，排序不也完成了一半？

想像一下桌子上摊开着牌，第一次我们从中换挑出大王放在手上，第二次我们挑出小王，然后是黑桃老K……黑桃Q，如此下去直到小A，手中的牌不也就已经排好次序了？

每次从中选出最大值或最小值，依此排成序，这就是选择排序法的过程描述。

不过，上述的过程有一点不合要求。

我们说过手中只能过一张牌。

因此，在程序实现时，我们找出一个最大值之后，就要把它放到数组中最末。

那数组中最末位置原来的值？

当然是把它放到最大值原来所在位置了。

为了再稍稍直观点，我们改为：

每次找的是最小值，找出后改为放到数组前头。

//选择排序（从小到大）

voidselect（intnum[],intcount）

{

   inttmp;

   intminIndex;//用于记住最小值的下标

   for（inti=0;i

   {

        minIndex=i;//每次都假设i所在位置的元素是最小的

        for（intj=i+1;j