发布时间 : 星期三 文章第三章 程序设计基础更新完毕开始阅读
3.10.3 排序
假设将需排序的数放在一维数组中，要求从小到大排序 1． 直接插入排序法：
算法：将一新数据插入到一有序表中，使该有序表成为一新的、数据增1的有序表。 如：一组数组A：66，37，89，23，1，9，3，43 下标：1 2 3 4 5 6 7 8 J I
先假定：[66] [37，89，23，1，9，3，43] 有序 J I 无序
第一趟：[37，66] [89，23，1，9，3，43] 第二趟：[37，66，89] [23，1，9，3，43] . . .
第七趟: [1，3，9，23，37，43，66，89] 【例3.21】用直接插入排序法从小到大排序一组数。 关键字：监视哨、移位、插入 2． 冒泡排序法：
算法：通过对一无序表N个数相邻两数进行比较，将大的交换到后面，这样一趟就将一个数沉下去，至多经N-1趟后有序。 如：一组数组A：66，37，89，23，1，9，3，43 下标：1 2 3 4 5 6 7 8 第一趟：37，66，23，1，9，3，43，89 第二趟：37，23，1，9，3，43，66，89 ． ． ．
第七趟：1，3，9，23，37，43，66，89 【例3.22】用冒泡排序法从小到大排序一组数。 3． 选择排序法：
算法：将无序部分中最小的数据选择出来，附加在有序表表尾。 如：一组数组A：66，37，89，23，1，9，3，43 下标：1 2 3 4 5 6 7 8 先假定：[] [66，37，89，23，1，9，3，43] 有序 无序
第一趟：[1][37，89，23，66，9，3，43] 第二趟：[1，3][89，23，66，9，37，43] ． ． ．
第七趟：[1，3，9，23，37，43，66，89] 【例3.23】用选择排序法从小到大排序一组数。
3.10.4 查找
1． 顺序查找
算法：从第一个元素开始逐一比较，直到末尾。 假设A数组中存放N个整数，要找X。 【例3.24】用顺序查找的方法查找某数X。
第 25 页 共 26 页
2． 折半查找
（查找对象必须已有序，假设按从小到大排序）
算法：设三个指示器TOP指向有序表表头，BOT指向有序表表尾，求出 MIDDLE=（TOP+BOT）\\ 2 ，X为要找的数。 A（MIDDLE）与X比较，若相等，则找到；
若X>A（MIDDLE），则查找范围可缩小为后半部分，更改范围； 若X
找43，因43>a(middle)故在后半部分，则TOP指向37，MIDDLE 指向43 43=a(middle),则找到
【例3.25】用折半查找的方法查找某数X。
3.10.5 矩阵运算 1． 矩阵的加法
设有两个M*N矩阵A，B，那么矩阵A与B之和记作A+B，规定为：
A+B= a11+b11 a12+b12 … a1n+b1n a21+b21 a22+b22 … a2n+b2n ……….
am1+bm1 am2+bm2… amn+bmn
只有当两个矩阵的行数相同且列数也相同(同型矩阵)时，这两个矩阵才可以相加。 【例3.26】设有矩阵A，B，均为2*2矩阵，计算A+B的值。
2. 矩阵相乘
设 A 是一个 M*S
矩阵,B 是一个S*N矩阵,A*B=C,C是一个M*N的矩阵
S CIJ= ∑ AIK BKJ
K=1
如：A= A11 A12 A21 A22 A31 A32 B= B11 B12 B13 B21 B22 B23
C=A11*B11+A12*B21 A11*B12+A12*B22 A11*B13+A12*B23
A21*B11+A22*B21 A21*B12+A22*B22 A21*B13+A22*B23 A31*B11+A32*B21 A31*B12+A32*B22 A31*B13+A32*B23
【例3.27】设有4*2矩阵A，2*3矩阵B，计算A*B的值。
第 26 页 共 26 页