最值与排序
一、求最值方法与日常生活接近
二、求最值方法与排序的算法关系紧密
三、课本里参考书中几乎没有这个章节，客 观上造成这一内容的学习障碍。
四、同学们如知其渊源则较容易掌握最值（最大值和最小值）数学中我们经常求某个区间的最大值最小值之类的，现在我们来看看如何用计算机编程的方法求一个数组中的最值。
键盘输入任意10整数：
98，12，－3，－45，0，
232，654，1，77，64
请编程找到其中的最大值。这个问题就好象十个人站队，我们可以很直观地看到谁是最高的一样。这其中一定要比较两个人的高低，是的，我们就是要把这种人类具有的智慧赋于计算机。
我们先来看看三种求最值的方法：
一、相邻比较并交换 先把十人排成一列，然后从一边开始。比较两相邻的高低，如果第一个人比第二个人低（高）则把他们调换位置，再比较第二个人和第三人的高低，如果第二个人比第三人低（高） ，则这两人调换位置，…… ，按这种方法，相邻两人两两比较，如符合条件就调换位置。经过九次比较调换，那么最低（高）那人一定会排在最后那个位置上。
用C语言可以描述出：
#include <stdio.h>
Main() { int I,j,t; Int a[10]={ 98，12，－3，－45，0，232，654，1，77，64}；
For(i=0,i<9;i++) If (a[i]>a[i+1]){t=a[i]；a[i]=a[i+1]；a[i+1]=t；}
Printf(“the max value is %d”,a[9])； }
冒泡法排序 冒泡排序是比较两个相邻元素的大小，若发现它们构成逆序，就交换它们的值。 以下程序是比较两相邻元素a[i],a[i+1]，第一轮比较结束后该数组10个元素中最大的元素被放置在最后；第二轮比较后，前9个元素中的最大数被放置在倒数第二个位置上； 第三轮比较后，前8个元素中的最大数被放置在倒数第三个位置上； …………。
任给十个整数，按由小到大的顺序排序后输出。
#include <stdio.h>
Main()
{ int I,j,k,t； Int a[10]={ 98，12，－3，－45，0，232，654，1，77，64 }；
For (j=0;j<9;j++) For(i=0,i<9-j;i++) If (a[i]>a[i+1]){t=a[i]；a[i]=a[i+1]；a[i+1]=t；}For(k=0;k<=9;k++) Printf(“the sorted values is %3d”,a[k])； }
二、定点比较且交换 先把十人排成一列，然后从一边开始。把第一个与其后的所有人依次两两比较，只要后边的人比他低（高）则进行交换，这样进行九次的比较交换，则最低（高）的那位就在最开始的位置。
用C语言也可以写出：
#include <stdio.h>
Main()
{ int I,j,t；
Int a[10]={ 98，12，－3，－45，0，232，654，1，77，64}；
For(i=1；i<=9；i++) If (a[0]>a[i]){t=a[i]；a[i]=a[i]；a[i]=t；}
Printf(“the min value is %d”,a[0]); }
交换法排序 把一个特定元素与所有待排序的元素依次进行比较，如果逆序则进行交换。确定最值，然后把最值排成一列就有序化了。
任给十个整数，按由小到大的顺序排序后输出
#include <stdio.h>
Main() { int I,j,k,t； Int a[10]={ 98，12，－3，－45，0，232，654，1，77，64 };
For (j=0;j<9;j++) For(i=j+1；i<=9；i++) If (a[j]>a[i]) { t=a[i]；a[i]=a[j]；a[j]=t；}
For(k=0;k<=9;k++) Printf(“the sorted values is %3d”,a[k])； }
三、比较记号不交换 先把十人排成一列，依次编号，然后从一边开始。把第一个与其后的所有人依次两两比较，只要后边的人比他低（高）则记住他的编号，再拿这个被编号的人与其后的所有人依次比较，如后边的人比他低（高）则记住他的编号，……。这样进行几次的比较记号，则最低（高）的那位的编号不就知道了吗？
用C语言也可以写出：
#include <stdio.h>
Main() { int K,j；
K =0 ……………设置变量K用来记录下标值
For (j = 1; j < = 9; J++ )
If ( a[ k ] > a[ j ] ) k=j； …………如果逆序则记录该元素下标
Printf(“%d”,a[k]); }
选择法排序 那么选择法排序又是如何呢？选择法排序与上例相似，只是遇到逆序的数不是立即进行交换，而是先记下它的下标，待一轮比较完毕后再交换。这种算法比较优化。
#include <stdio.h>
Main( )
{ int a[10],I,j,k；
For （I = 0；i<= 9；i++）
Scanf( “%d”, &a[ I ] ) ；
For ( I = 0；I <9 ；i++)
{ K = I ；
For (j = I + 1; j < = 9; J++ )
If ( a[ k ] > a[ j ] ) k=j；
If ( k != I ) swap（a[k],a[i]）； }
For ( I = 0 ;i<=9; i++)
Printf(“the sorted values is %3d”,a[k]); }
考试注意事项 对于以上排序法的三段程序，整体结构相似，但在对数组的处理这一环节不同，请同学们熟悉程序结构，再结合算法仔细推敲，不同之处经常是各类考试的填空题的偏爱。
内部排序与外部排序
（1）内部排序：将欲处理的数据存放在内存储器中做排序，数据可被随机存取。我们今天讲的所有排序方法都是这类型。
（2）外部排序：将欲处理的数据过于庞大，无法全部放在内存储器中，必须借助外部存储器，数据不可随机被存取。如：合并排序等。 排序的方法还有很多，待同学们以后学习《数据结构》课程的时候会有更多的认识！
双端选择法排序 双端选择排序 由选择排序变种而来，每次定位每个序列中的最小和最大元素，并把它们分别放在序列的开头和结尾。
课后作业： 用双端选择法排序输出一列数
