第三章 程序设计基础

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），则查找范围可缩小为后半部分，更改范围； 若XBOT 则没找到。 T:TOP M:MIDDLE B:BOTTOM 设一有序数组A：1，3，9，23，37，43，66，89 T M B

找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 页