数组应用举例（下）在线视频

例3是找出数组中的最大值或者最大值所在的位置

这个方法同样适合找出最小值

我们看一下具体方法

先设定数组中第一个元素就下标为0这个元素为当前最大值

然后依次与数组中的每个元素比较

如果有哪个元素的值比当前的最大值更大

它就成为当前最大值

比较一遍后

就能得到数组中的最大值

我们看一下计算最大值的算法的这样一个比较形象化的表示

最初假定开始的这个人个子最高

他的编号是i=0

然后她跟旁边的i=1

就是第二个人比较

第二个人的个子没有她高

那么她继续是最高的

然后她跟第三个人比

第三个人个子比她高

那么现在第三个人暂时成为个子最高的

她的编号是2

然后她跟第四个人比较

第四个人个子比她高

那么第四个人现在是最高的

编号是3

然后她跟第五个人比较

那么第五个人没有她高

这个时候比较完了

所以整个下来她就是最高的

她的编号是3

我们看一下具体的程序

这个程序左侧这个是找出最大值

右侧这个是找出最大值所在的位置

基本的方法差不多

我们看一下左侧

首先

这个地方max这个变量就是表示最大值的这样一个变量

它的初值设为score [0]

就是最开始的那个元素的值先假定它是最大的

然后

后面这个循环就是从i等于1

就是第二个数据开始

一直到最后一个数据

然后每个循环的时候每一次都跟当前的这个最大值比较

如果它的值比当前的这个最大值还要大

那么就把它的值赋值给max

那么这时候

它就成为当前最大的

那么整个这个过程循环一遍以后

最大值就找到了

然后就返回

其实这个过程

跟我们刚才那个形象化的

就是从一群人当中找出最高个的那个过程还是很相似的

我们看这个

这个跟刚才左侧的这个很像

只不过这个地方我们最初的时候

设置的时候不是像这边是把这个值给这个

而是把下标就最初认为下标为0的值是最大的

就是下标设为0

然后

在后面的循环过程当中

如果有某个值比刚才的这个下标的值还要大

那么就把新的这个值赋给这个下标

然后循环结束以后

这样就是返回下标值

因为有些时候我们可能需要的是返回下标值

而不是返回最大值

排序就是让事物有序排列

可以是从小到大排序

也可以从大到小排序

计算机中

数组排序是很常见的且有用的操作

排序算法有很多种

在以后的其他课程中

会更加深入的探讨这个问题

这里只介绍两种

交换法和选择法

我们看一下交换法排序的原理

这也是一个形象化的方法

这个里面

形象化这个方法是要把这堆人从个子大到个子小依次排序

最初的时候是从最左侧的人开始

她跟旁边的人比较

旁边的人高

就跟她换一下

然后她再跟第三个人比较

那么她比这个人个子还高

所以就不发生交换

然后她跟第四个人比较

她的个子依然比这个人高

所以也不发生交换

再跟第五个人比较

她也不发生交换

那么这样一趟下来

就确定了最高的人

她排在队伍最开头的位置

再下面的过程是找第二个

就是除了前面那个最高的个子以外第二高的人

然后就是她跟他旁边的这个人比较

这个比她的个子高

然后发生交换

然后她再跟这个比较

那么她个子高

所以不发生交换

然后她跟这个比较

也不发生交换

这样就把第二个人排好了

那么第三个人跟前面的过程类似

这个地方就不演示了

那么这样一直排到最后

所有的人就按照从大到小的顺序就排好了

我们再来看看这个过程

就是交换排序法它的过程每一趟

它能够确定最大的那个值或者说个子最高的那个人

然后第二趟过来确定队伍当中第二个（次）高的这个人

就是剩下的这些人里面他是最高的

然后第三趟再下来就再确定第三高的人

整个就是这样一个步骤

我们看下交换排序法的具体程序

在程序当中

要理解这个程序主要是看这个地方

这儿它有一个双重循环

这个双重循环怎么理解呢 是这样的

就是内层的这个循环

这一趟相当于我们刚才那个里面内层循环

循环一趟排好一个人

内层循环的时候注意这个j 等于i+1

那么内层循环它每次排的时候越往后那么比较的次数越少

就是说排第一个人的时候

它要跟后面每一个人都要做一次比较

排第二个人的时候

比较的次数就减少一个了

那越到后面比较的次数越少

所以这个地方是i+1

就是内层循环它是排好其中的一个人

而整个外层循环就是排多少趟

你有多少个人 那么循环的次数

比如说你有五个人

那么会循环四次

因为前面的四个排好了

第五个人他自然就是排好的

所以这个地方是小于n-1

这样认识了以后

那你就会明白这个交换法的具体工作的原理

我们看一下交换法排序的这个完整的程序

这个完整程序当中

main函数也是采用了比较直接的办法

就是元素的个数N定义成6

这个数组的初值直接这样设了

然后这地方就调用交换法排序的这个函数

排完序以后

就把排序的结果再输出出来

因为你要是不输出可能不知道整个程序运行正确不正确

好我们编译运行一下

那这是排好序的结果

排好序的结果就是这样

当然这个排序的算法我们刚才看到是从大到小排序

其实如果你是从小到大排序的话方法极为类似

只不过就是在这些地方它交换的时候

到底是大于交换还是小于交换

只要把这个地方变一下就好了

下面我们看一下选择排序法的原理

选择排序法是这样

就是最初先假定第一个人个子最高

然后跟旁边比较

然后发现第二个个子高

然后当前高的就是他

下标是1

然后她再跟后面这些人比较

那么这一趟下来

就是确定了个子做高的那个人的位置

确定了以后

就把他换到队伍的最前面

完了第二趟是在剩下的人里面然后再找个子最高的

那么这一趟里面我们确定k 等于2

就是下标为2的这个人她是剩下这些人里面个子最高的

然后把他换到第二位

然后再剩下的过程是在剩下的这三个人当中再找个子高的

那这个过程就不演示了

那么从这个过程当中我们可以看到

选择法它发生交换的次数比刚才的交换法要少

它每一趟能找到这一趟需要找的最大的那个值

找到了以后

就发生一次交换

好我们看一下选择排序法的具体程序

这个程序理解的时候也是有双重循环

双重循环中外层循环相当于是有多少趟

这个也是比如有五个人

那么这个就循环四次

然后里面这个就是刚才看到的

形象化的身高的排队的例子当中的这一趟下来

我们能够找到这一趟要找的那个最大值

就是个子最高的那个人他所在的位置

找到了以后

这个时候就发生交换

就把他换到他需要的地方去

整个理解这个程序

那么你最需要关注的就是内层循环

与外层循环它的意思是什么

这样的话

这个程序就比较容易记忆或者理解

如果你不理解它的内外层循环的含义

那么这个程序可能你不太好掌握它是怎么实现的