第2章_算法基础

1、BISTU1BISTU 第第 2 2 章章 算法基础算法基础 BISTU2 内容提要 1、算法的概念、算法的概念 2、算法设计、算法设计 3、算法的评价、算法的评价 BISTU3 1、算法的定义 l 简单地说，算法（Algorithm）是用计算机 解决计算问题时所采取的一系列计算步骤 组成的序列。 l 严谨的定义：“算法就是任何明确定义的 计算过程，该过程取某个值或值的集合作 为输入并产生某个值或值的集合作为输出。 这样，算法就是把输入转换成输出把输入转换成输出的计算计算 步骤的一个序列步骤的一个序列。” BISTU4 2、算法的特性 （1）有穷性有穷性：能在执行有限个步骤之后结束 （2）确定

2、性确定性：每一步骤都必须明确、无二义性。 （3）可行性可行性：算法的每一步都是可行的，即算法的每 一步都能被计算机所理解和执行，并且能得到正确的结 果。 （4）零个或多个输入零个或多个输入：输入可以来自键盘、文件或网 络。程序可以没有输入。 （5）至少一个输出至少一个输出：没有输出的算法没有意义。 BISTU5 3、算法设计的要求 正确性正确性 可读性可读性 健壮性健壮性 时间效率高时间效率高 存储量需求低存储量需求低 BISTU6 正确性正确性的层次的层次 算法程序没有语法错误; 算法程序对于合法的输入数据能够产生满 足要求的输出结果; 算法程序对于非法的输入数据能够得出满 足规格说明的结果

3、; 算法程序对于精心选择的，甚至刁难的测 试数据都有满足要求的输出结果。 BISTU7 可读性可读性 为了便于阅读、理解和交流，可读性要素： 增加算法文件名、子图、子程序、算法样本数 据文件名的可读性； 在算法语句中增加注释语句，说明重要变量、 决策语句的用途； 将算法有关的文档整理在一个目录中 BISTU8 健壮性健壮性 能对输入数据不合法的情况做合适的处理 比如输入的时间或者距离不应该是负数 算法的健壮性表现在当输入数据不合法时，算 法也能做出相关处理，而不是产生异常或无法 解释的结果 BISTU9 时间效率高和存储量需求低时间效率高和存储量需求低 对于同一个问题，如果有多个算法能够达 到

4、同样的问题解决标准，执行时间最短的 算法效率最高 存储量需求指的是算法在执行过程中需要 的最大存储空间，主要指算法程序运行时 所占用的内存或外部硬盘存储空间，越少 越好 BISTU10 4、算法的描述 四种方式描述算法的方法： l 自然语言自然语言：直观、易于理解，但易产生歧义。 l 流程图流程图：流程图描述了算法所要执行的操作的顺 序及执行操作的条件。流程图直观形象、易于理 解。 l 伪代码伪代码：伪代码既类似于自然语言，又使用与程 序设计语言相似的方法描述算法。这使得伪代码 即能够清晰地表达算法的结构，又不必像程序那 样在细节上非常严谨。 l 程序设计语言程序设计语言：算法的终极表示。能运

5、行并获得 结果。 BISTU11 【例【例2-1】用自然语言写出求两个正整数a，b 的最大公约数的算法。 欧几里德算法又称辗转相除法，用于计算 两个正整数a,b的最大公约数。 其计算原理依赖于定理 gcd(a,b) = gcd(b, a mod b) ， 其中gcd(a,b)表示正整数a，b的最大公约数 a mod b表示a/b后的余数。 BISTU12 【例【例2-1】用自然语言写出求两个正整数a，b 的最大公约数的算法。 用自然语言描述该算法的思路： 步骤1：输入a，b。 步骤2：如果a小于b，则对换a、b的值。 步骤3：a除以b得余数r。 步骤4：若r 等于0,则b为所求的最大公约数；

6、否则，以b为a、r为b,继续步骤3。 BISTU13 【例【例2-2】从一组数（至少两个）中找到最大 的数。 步骤1：输入这一组数。 步骤2：将最大数置为第一个数。 步骤3：将下一个数和最大数进行比较，如 果该数大于最大数，将最大数置为该数， 反之保持最大数不变。 步骤4：重复步骤3，直至比较至最后一个 数，此时，将得到最大数。 BISTU14 流程图 用图框图框表示各种操作，用流程线流程线表示操作的执行 顺序。 流程图描述了算法所要执行的操作的顺序及执行 操作的条件。 流程图直观形象、易于理解。 美国国家标准化协会（American National Standard Institute ,

7、ANSI）规定了常用的程序流程图符号 BISTU15 流程图符号 常用的流程图符号 起止框起止框判断框判断框处理框处理框输入输入/ /输出框输出框 注释框注释框流向线流向线 连接点连接点 BISTU16 算法的三种基本结构 三种基本结构： 顺序结构 选择结构 循环结构 任何算法都是上述三种结构的组合。 BISTU17 算法的三种基本结构 （a) 顺序结构 (b) 选择结构 (c1) 直到型 循环结构 (c2) 当型 循环结构 BISTU18 【例【例2-3】用流程图描述求两个正整数a，b的 最大公约数的算法。 采用欧几里得 算法求两个正 整数的最大公 约数。该算法 的流程图如右 图。 BIST

8、U19 【例【例2-4】从一组数（至少两个）中找到最大 的数的算法。 右图表示 的算法适 用于使用 数组来存 放输入的 数据 BISTU20 【例【例2-4】从一组数（至少两个）中找到最大 的数的算法 右图表示的算 法适用于反复 使用一个变量 来存放输入的 数据 BISTU21 基于流程图的编程环境 为了帮助学生绕过编程语言来实现算法，出现了 多种基于流程图的编程环境，其中开源软件 Raptor就是一个优秀的流程图工具。 Raptor 是一种基于流程图的编程环境，不必记忆 复杂的编程语言语法，就可实现一个算法 Raptor中的用流程图表示的算法可以直接执行， 并显示执行结果。 上机实验指导的第

9、2章，给出了几个基于Raptor环 境的算法设计实验，供同学们练习。 BISTU22 伪代码（本部分内容仅要求理解） 使用伪代码(Pseudocode)描述算法是一种常用 的方法。 伪代码既类似于自然语言，又使用与程序设 计语言相似的方法描述算法。这使得伪代码 即能够清晰地表达算法的结构，又不必像程 序那样在细节上非常严谨。 伪代码没有通用的语法标准 BISTU23 伪代码规范的内容 我们采用了如下伪代码规范： （1）变量 在伪代码中，变量不需声明，变量名是字母开头、由字母数 字组成的符号串，用小写表示，例如x、y、a1。 （2）表达式 表达式是由运算符将运算量（常量、变量或表达式）连接起 来

10、的式子，分为算术表达式、关系表达式、逻辑表达式。 BISTU24 运算符和表达式 算术运算符用 +、-、*、/、% 表示加、减、乘、除、求余 运算。 关系运算符用 、表示判断“是否等 于”、“是否不等于”、“是否小于”、“是否大于”、 “是否小于等于”、“是否大于等于”。 逻辑表达式用 and、or、not表示“并且”、“或者”、“ 非”。 例子： b*b-4*a*c 是一个算术表达式； a+bc and b+ca and a+cb 是一个逻辑表达式，其中又 包括了三个关系表示式。 BISTU25 伪代码规范的内容 （3）赋值 用“=”表示赋值，如x=e表示将e的值赋给x （4）注释 用“/”

11、表示注释开始，一直到该行的行尾。注释是对伪代码 的更详细的解释说明。 （5）选择语句 IF （表达式C） THEN 语句块S1 ELSE 语句块S2 BISTU26 伪代码规范的内容 （6）循环语句 这里给出两种循环语句：当型循环(即WHILE循环)、FOR型循 环。 当型循环的基本形式： WHILE (表达式C) 语句块S FOR循环的基本形式： FOR (i=begin TO end ) 语句块S BISTU27 伪代码规范的内容 （7）数组 用数组来表示一组相同类型的数据，其中每个数据称为数组 元素。 用 aj 表示数组a的第j个元素。 a1. j表示含元素a1、 a2、 aj的数组，符

12、号“. ”用 来指示数组中下标取值的范围。 BISTU28 【例【例2-5】用伪代码写出求两个正整数a，b的最大公 约数的算法。 输入：正整数a,b 输出：a,b的最大公约数 GCD(a,b) 1 IF （ab） / 如果ab 2 THEN 3 c=a 4 a=b 5 b=c 6 r = a%b /求a除以b后的余数 7 WHILE （r0） 8 a=b 9 b=r / 实施“辗转相除” 10 r = a%b 11 返回（b） BISTU29 【例【例2-6】用伪代码写出用伪代码写出从一组数（至少两个）中找 到最大数的算法。 输入：数组a1. n 输出：最大值 MaxValue(a1. n)

13、1 max=a1 2 k=2 3 WHILE （kn） 4 IF （maxak） 5 THEN 6 max= ak 7 k=k+1 8 返回（max） BISTU30 程序设计语言 用程序设计语言描述算法是计算机算法的 终极表示。 设计算法的目标就是为了使算法能在计算 机上运行并获得结果。 程序设计语言表示的算法恰恰实现了这一 目标。 一个算法可以用多种不同的程序设计语言 表示。 BISTU31 【例【例2-7】用用C语言实现语言实现求两个整数的最大公 约数程序。 #include int main() int a , b , c , r ; printf(请输入整数a,b: ); scanf

14、(%d%d, if(ab) c=a; a=b; b=c; r=a%b; while(r!=0) a=b; b=r; r=a%b; printf(result=%dn,b); return 0; BISTU32 三、 算法设计 l算法设计策略 l简单排序算法 l简单查找算法 BISTU33 （一）常用的算法设计策略 算法设计过程中，发现问题、分析问题及解决问 题的思路、步骤与其他学科中的方法是一致的， 就是寻找规律 计算机科学家在算法研究过程中总结了一些具有 普遍意义的算法策略和一些可循的规律，能够帮 助我们较快地找到算法 BISTU34 （一）常用的算法设计策略 本节讨论几个常用的算法设计策略

15、： l穷举法 l递推法 l递归法 l分治法 l贪心法 BISTU35 1、穷举法 n 也称蛮力法，它是一种简单而直接的问题求解方法 ，解题思路常常直接基于问题的描述，是计算机求 解最容易应用的方法，也是比较耗时的算法。 n 有很多问题，根据其描述和相关的知识，能确定一 个大概的解空间范围大概的解空间范围，在这个解空间范围内，按照 某种顺序一一枚举一一枚举和检验检验每个可能的值每个可能的值，直到找到 一个或全部符合条件的值（即问题的解），有时候 甚至可能无解可能无解。 BISTU36 穷举法 采用穷举法解题的基本思路： n 确定穷举对象、穷举范围和判定条件； n 一一穷举可能的解，验证是否是问题

16、的解 在穷举法中，穷举对象的选择对象的选择也是非常重 要的，它直接影响着算法的时间复杂度， 选择适当的穷举对象可以获得更高的效率 BISTU37 穷举法 举例 【例【例2-9】古典数学问题：百钱买百鸡问题。 某人有一百元钱，要买一百只鸡。其中 ，公鸡五元一只，母鸡三元一只，小鸡一 元三只。问：如何用一百元钱正好买一百 只鸡？ BISTU38 百钱买百鸡问题 算法分析 n 第一步：先计算一下100元钱最多能买多少只公鸡 和母鸡： u经计算：100元钱最多最多能买20只公鸡只公鸡；100元钱最多最多能 买33只母鸡只母鸡；当然，虽然100元钱能买300只小鸡，受 条件约束，小鸡的数目必须在100以

17、内。这样，就初步就初步 确定了此问题的解空间范围。确定了此问题的解空间范围。 n 第二步：检验公鸡、母鸡、小鸡的数目哪种组合 能满足总价钱为100元。 n设求出的解为公鸡x只、母鸡y只、小鸡z只，则x、y、z 满足条件是“5x+3y+z/3正好等于100”。 BISTU39 用伪代码描述百千买百鸡问题的算法 (注：算法中“/”表示对算法步骤的注释) FOR( x =0 TO 20 ) /x取值范围为取值范围为020，判断一次x值增加1。 FOR( y =0 TO 33 ) / y取值范围为取值范围为033，判断一次y值加1 z = 100-x-y; /小鸡最多100只，但根据x，y计算出小 /

18、鸡的数目，这样就缩小了穷举范围 IF (x*5+y*3+z/3 = 100) /判断条件 THEN 输出x,y,z的值 BISTU40 如果需要解决的问题规模不大 用穷举法设计的算法其速度是可以接受的 BISTU41 分析：分析： 对对5 5本书从本书从1 1至至5 5编号，假设编号，假设a,ba,b两个人分别借这两个人分别借这5 5 本书中的本书中的1 1本。当本。当a=ia=i时，表示时，表示a a借了编号为借了编号为i i的书。的书。 则则a a、b b的取值范围为：的取值范围为：1 = 1 = a a、b= 5b= 5 当当2 2个人所借的书的编号不相同时（个人所借的书的编号不相同时（

19、a!=ba!=b） ，就，就 是满足题意的一种借阅方法。是满足题意的一种借阅方法。 问题：问题：小明有小明有5 5本新书，要借给、两位小朋友，若本新书，要借给、两位小朋友，若 每人每次只能借一本，则可有多少种不同的借法？每人每次只能借一本，则可有多少种不同的借法？ 算法：算法： 1.1.考察考察a a可能的范围：可能的范围：a=1a=1，2 2，3 3，4 4，5 5； 2.2.考察考察b b可能的范围：可能的范围：b=1b=1，2 2，3 3，4 4，5;5; 3.3.验证验证a,ba,b的所有取值，若的所有取值，若a!=ba!=b，则输出，则输出a,ba,b。 BISTU42 2、递推法

20、递推法是利用问题本身所具有的一种递推 关系求解问题的一种方法 所谓递推，是指从已知的初始条件出发，依据 某种递推关系，逐次推出所要求的各中间结果 及最后结果 其中初始条件或是问题本身已经给定，或是通 过对问题的分析与化简后确定 BISTU43 可递推求解的问题特点 该类题目一般有以下二个特点： n问题可以划分成多个状态； n除初始状态外，其它各个状态都可以用固定的 递推关系式来表示 在实际解题中，该类题目一般不会直接给 出递推关系式，而是需要通过分析各种状 态，找出递推关系式 BISTU44 猴子吃桃问题 小猴子摘桃若干，立即吃了一半 还觉得不过瘾，又多吃了一个； 第二天接着吃剩下桃子的一半，

21、仍 觉得不过瘾又多吃了一个，以后小 猴子都是吃剩下的桃子一半多一个 ； 到第10天小猴子再去吃桃子的时候 ，看到只剩下一个桃子； 则小猴子第一天共摘了多少桃子？ BISTU45 递推问题求解 由题意可以得到下表： 分析后可知，猴子吃桃问题递推关系为： nSn=1 （当n=10时） nSn =2（Sn+1+1）（当1n10时） 在此基础上，以第10天的桃数作为基数， 用以上归纳出来的递推关系设计出一个循 环过程，将第1天的桃数推算出来 BISTU46 斐波那契数列 n斐波那契数列（Fibonacci）：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ， n数

22、列的规律：数列的规律：这个数列从第3项开始，每一 项都等于前两项之和。 n第1项和第2项为初始项。即，f1=1，f2=1， nf3=f1+f2，fn=fn-1+fn-2 (当n3时)。逐步求 出所需要的斐波那契数列项。 n递推关系式递推关系式 fn=fn-1+fn-2 BISTU47 费波纳切数列的奇妙性质 随着数列项数的增加，前一项与 后一项之比越逼近黄金分割 0.6180339887，因此，斐波那契 数列也称黄金分割数列。 斐波那契数列在物理学、化学、 经济领域、生物学都有直接应用 。 它与自然界的许多现象也有很多 巧合，例如许多植物的花瓣数呈 现斐波那契数列特性。 BISTU48 用伪代

23、码描述求斐波那契数列的算法 f1=1 f2=1 输出f1,f2的值 FOR( i =2 TO 20 ) /本算法求费波纳契的前20项 f3 = f1+f2; /后一项等于前两项之和 输出f3的值; f1=f2; / 为了得到新的f3更新f1 f2=f3; / 为了得到新的f3更新f2 BISTU49 3、递归法 能采用递归描述的算法通常有这样的特征： 为求解规模为N的问题，设法将它分解分解成规模较 小的问题，然后从这些小问题的解方便地构造出 大问题的解。（分解时会利用递推公式） 并且，这些规模较小的问题也能采用同样的分解分解 和综合综合方法，分解成规模更小的问题，并从这些 更小问题的解构造出规

24、模较大问题的解。 特别地，当规模N=1时，能直接得解。 递归算法的执行过程分为问题分解分解和回归回归两 个阶段。 BISTU50 用递归法求费波纳切数列 例如，编写计算斐波那契数列的第n项函数 fib(n)。 实现该函数的核心伪代码为： IF ( n=1 or n=2) THEN 得到函数值为 1 ELSE 计算 fib(n-1)+fib(n-2) 的值 BISTU51 4、分治法 分治法（分治法（Divide and Conquer）的基本思想是，将 一个较大规模的问题分解为若干个较小规模的子 问题，找出子问题的解，然后把各个子问题的解 合并,从而得到整个问题的解 分治法的分（Divide）

25、是指将较大的问题划分 为若干个较小的问题，然后用递归法求解子问 题； 分治法的治（Conquer）是指从小问题的解来构 建大问题的解 BISTU52 4、分治法 分治法算法中至少包含有两次递归过程，只有一 个递归过程的算法在严格意义上不能算作分治算 法 二分查找算法采用了分治法策略 分治法在每一层递归上都有三个步骤。 （1）分解：将原问题分解为若干个规模较小，相互独立，与原问 题形式相同的子问题； （2）解决：若子问题规模较小而容易被解决则直接解，否则递归 地解各个子问题； （3）合并：将各个子问题的解合并合并为原问题的解。 BISTU53 二分查找算法中的分治法策略 计算n/2，得到序列的中

26、间位置值 mid，于是待查找的有序序列以 amid为界限，被分成个数大致相同的两半。 原任务得到一次分解 。 判断amid的值是否等于key。 若amid等于key，则在序列中找到指定元素，查找过程结束。 若amid小于key，则继续在amid右侧序列中查找指定元素（递归查找）。 若amid大于key，则继续在amid左侧序列中查找指定元素（递归查找）。 采用上述同样的方法处理左右两部分序列，直到找到满足条件的 记录，使查找成功；或直到无法在分出子序列为止，此时查找不 成功。 BISTU54 5、贪心法 贪心法是指，在对复杂问题求解时，总是做出在 当前看来最好的选择（即局部最优）。 贪心法是一

27、种不追求最优解、只希望得到较为满 意解的方法。 贪心法一般可以快速得到满意的解，因为它省去 了为找最优解要穷尽所有可能而必须耗费的大量 时间。 贪心法以当前情况为基础作最优选择，而不考虑 各种可能的整体情况。 BISTU55 “数字三角形”问题 一个“数字三角形”如右图所 示。 从三角形的顶点出发，向下行 走，到达最底层的某一个节点 ，称为一条路径。 每次向下层行走时，只能看到 其下接的两个相邻节点。 问：能否找到一条路径，使得 路径上节点值之和最大（称为 最大权值路径，每个节点的值 称为“权”）？ BISTU56 用贪心法的求解数字三角形的过程 用贪心法的求解过程： 从第一层的节点5向下走，

28、使用贪心策略，选择第 二层中的较大者（即节点4）。 继续从第二层的节点4向下走，使用贪心策略，选 择第三层中的较大者（即节点8）。 继续按此方法向下行走，最终得到一条符合局部局部 最优的路径最优的路径 5 4 8 10 5（权值32）。 BISTU57 用贪心法最终得到一条符合局部最优的路径局部最优的路径 5 4 8 10 5（权值32）。 而实际上，数字三角形的最大权值路径为而实际上，数字三角形的最大权值路径为5 4 6 7 15（权值（权值37）。）。 用什么方法能求出最优解呢，用什么方法能求出最优解呢，-动态规划法动态规划法 感兴趣的同学可查阅资料，了解此算法。感兴趣的同学可查阅资料，了

29、解此算法。 BISTU58 6、迭代法 (选讲) 迭代是数值计算中通过从一个初始估计出 发寻找一系列近似解来解决问题（一般是 解方程或者方程组）的过程 为实现这一过程所使用的方法统称为迭代法（ Iterative Method） BISTU59 6、迭代法 一个简单的代数方程 求上述方程根的 一种迭代法 令x0初始值为1，则代入上 式，可计算出x1 为2， 再次代入迭代式，得出x2为1.5，直到满足条件： 新求出的值与上一次值相差不超过10-9 01 2 xx n n x x 1 1 1 BISTU60 （二）排序与查找算法 从浩瀚的数据中找到用户所需的数据，是计算机 处理数据的基本操作之一。

30、 尤其是互联网发达的今天，使用计算机的人经常 会用搜索引擎查找并下载自己所需的文字、图片 等信息。 例如，我们使用搜索引擎（比如“百度”）查找 关键词“算法”，搜索引擎就去从百度服务器的 “索引库”中搜索出所有包含“算法”的页面， 并显示在浏览器窗口。 BISTU61 1、查找算法 从一系列数据中找到需要的数据，需要使用查找 算法，其中需要查找的数据称为查找关键字（ Search Key）。 人们已经研究出了多种不同的查找算法，不同的 算法查找策略和效率不同。 本节只讨论两种简单、常用的查找算法： 顺序查找 二分查找。 BISTU62 （1）顺序查找 顺序查找，也称线性查找， 其执行过程是：

31、从一组数据（也称线性表）中的第一个数据元素开始， 依次查看每一个元素，将其与查找关键字进行比较， 若发现此元素的值与查找关键字相等，即找到所需的数 据元素，查找成功； 反之，若查到最后一个数据元素若查到最后一个数据元素，数据元素的值都不与 查找关键字相等，则表明线性表中没有所找的元素，查 找失败。 BISTU63 （1）顺序查找 课堂练习：用一个“寻找秘密号码”小游戏来模 拟顺序查找算法。 然后请回答下列问题： 在一次游戏中，你最多花费的猜测次数是多少？你最 少花费的猜测次数是多少？ 在一次游戏中，你第一次就能猜对的概率是多少呢？ 在游戏中，平均花费多少次猜测能猜对呢？ 在一次游戏中，如果秘密

32、号码卡片不在这些卡片中， 要猜多少次才能发现呢？ BISTU64 （1）顺序查找 l 右图为顺序查找算法流程图 l 输入：n个数据组成的一个 序列，查找关键 字key。这里假定n的值已知 。 l 输出：key在序列中的位置 ，或者key不在序列中的信 息。 l 提示：因为从第一个数据开 始比较，所以令k=1 BISTU65 （2）二分查找 二分查找，也称折半查找， BinarySearch ， 它的基本思想是，将n个元素分成个数 大致相同的两半（这里假设此数据序列按升序排 列），取an/2与欲查找的 key 作比较 如果key=an/2，则找到key，算法终止。 如果keyan/2，则只要在数

33、据序列的右半部继续搜索key BISTU66 （2）二分查找 二分查找算法的自然语言描述： 输入：n个数据组成的一个序列，查 找关键字key。这里假定n的值已知。 输出：key在序列中的位置，或者key不在序列中 的信息（此算法中用0表示）。 BISTU67 （2）二分查找 二分查找算法的自然语言描述： 第一步：设查找区间初值，即设区间下界left=1,设区间上界 right=n； 第二步：如果 leftright 则 计算中间位置 mid=(left+right)/2; (除不尽时舍小数取整) 否则 查找失败，算法结束。 第三步： 如果 keyamid 则 left=mid+1, 并继续执行

34、第二步； 如果 key=amid 则 查找成功成功，返回目标元素位置位置mid。 BISTU68 （2）二分查找 二分查找算法的 流程图描述： BISTU69 （2）二分查找 课堂练习： n设由10个元素组成的从小到大排列的有序序列 a1，a2，a3，a10为：1，5，8，9，12，14，15 ，18，20，25，要求查找元素18是否在序列中 。请写出查找过程中变量left,right,mid的取值， 以及查找成功花费的查找次数查找成功花费的查找次数。 n请与顺序查找算法做比较，查找同一个的数， 顺序查找算法所需的查找次数。 n哪个算法效率高？ BISTU70 2、排序算法 在计算机科学中，排

35、序是研究最多的问题之一。通过排序 ，将一组无序的数据序列调整为按照元素关键字排序的有 序序列（这里，一个数据元素可能包含多个子项，其中参 与排序比较的子项称为关键字）。 排序分为内部排序和外部排序。如果整个排序过程都在计 算机的内存里完成，称为内部排序；如果排序的数据量非 常大，整个排序过程不可能在内存里完成，则称为外部排 序。 本节只讨论几种常见的内部排序算法：选择排序、冒泡排 序和插入排序。 BISTU71 （1）选择排序 选择排序算法的思路： 第一步：从所有数据中选一个最小数，作为已排 序的第一个数； 第二步：从剩下未排序数据中选最小的数，添加 到已排序数据的后面； 第三步：反复执行步骤

36、第二步，直到所有数据都 处理完毕。 把第二步的操作称为一趟排序。n个元素的序列需 要n-1趟排序，就能变成有序序列。 BISTU72 （1）选择排序 右图演示了对数列 12，18，10，23，4， 30，25 进行选择排序的过程 。有序区间用中括 号标出，其右侧为 无序区间。 虚线表示数据互换 BISTU73 （1）选择排序 课堂练习： 设由10个元素组成的无序序列 a1，a2，a3， a4，a5，a6， a7，a8，a9，a10 值为：12，8，15，3，4，2，1，18，20，25 ，按照选择排序算法对该序列排序，要求写 出每趟排序中的有序区和无序区区间。 BISTU74 （2）冒泡排序

37、冒泡排序的基本思想： 将全部数据元素分成两部分：有序序列 和无序序列。无序序列的初始序列为，有序 序列的初始序列为空。 冒泡排序的基本操作是比较相邻的元素， 如果第一个比第二个大，就交换他们两个在序列中的位置，让较小 的居前，较大者居后。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对 。 最后的元素将是值最大的数据，将该元素加入到有序序列中，并令 无序序列的长度减1。 BISTU75 （2）冒泡排序 下图演示了对数列12，18，10，23，4，30，25进行冒泡 排序的过程。 有序区间用中括号标出。 BISTU76 （2）冒泡排序 课堂练习： 设由10个元素组成的无序序列 a1，

38、a2，a3， a4，a5，a6， a7，a8，a9，a10 值为：12，8，15，3，4，2，1，18，20，25，按 照冒泡排序算法对该序列排序，要求写出每趟排 序中的有序区和无序区区间。 与选择排序进行对比，分别统计排序过程中进行 数据比较的次数。 BISTU77 （3）插入排序 插入排序的基本思想： 将全部数据元素分成两部分： 有序序列和无序序列。 有序序列的初始序列为，无序序列的初始序列 为。 插入排序的基本操作：将无序序列中的一个数据插 入到已经排好序的有序序列中，并要求插入后的序 列仍然有序。进行n-1次插入并排序的操作后，将使 全部数据得到排序。 BISTU78 （3）插入排序

39、插入排序效率不高，但是容易实现。它借助了逐步 扩大成果的思想，使有序列表的长度逐渐增加，直 至其长度等于原列表的长度。 BISTU79 下图演示了对数列12，18，10，23，4，30，25进行插入排 序的过程。有序区间用中括号标出，其右侧为无序区间 图中，将18 放入有序区 时不需要移 动数据，而 将10放入有 序区时则需 要移动数据， 为什么？ BISTU80 （3）插入排序 课堂练习： 设由10个元素组成的无序序列 a1，a2，a3， a4，a5，a6， a7，a8，a9，a10 值为：12，8，15，3，4，2，1，18，20，25 ，按照插入排序算法对该序列排序，要求写 出每趟排序中

40、的有序区和无序区区间。 BISTU81 四、算法的评价 对同一个问题，可用不同的算法来解决， 执行这些算法所用的时间和存储空间也各 不相同。 一个算法的质量优劣通常用时间复杂度时间复杂度和 空间复杂度空间复杂度来衡量。 BISTU82 1、时间复杂度 同一个算法在不同的软硬件环境下，运行时间会有较 大差异。 因此，不能用算法的实际执行时间来衡量时间复杂度 通常是抛开计算机软硬件环境，只对算法中的计算工 作量进行统计。 算法中语句执行次数越多，它花费的时间就越多。 只有顺序结构和选择结构的程序，其执行时间基本固 定 而循环结构的程序，其执行时间与问题的规模有关 BISTU83 例如，下述算法：

41、FOR( i =1 TO n ) / i的取值范围为1n，此外层for语句执行次数为n FOR( j =1 TO n ) / j的取值范围为1n，此for语句执行次数为n2 k = 100-i-j; /该步骤是基本操作，执行次数为 n2 IF (i*5+j*3+k/3 = 100) /该步骤是基本操作，执行次数为n2 THEN 输出i,j,k的值 可见，这段用伪代码描述的算法总的执行次数是：f(n) = 3n2+n。 BISTU84 1、时间复杂度 一般情况下，算法的基本操作重复执行的次数是 问题规模n的某一函数f(n)。 当问题的规模n趋向于无穷大时，如果f(n)的值增 长缓慢，则算法为优。

42、 一般用f(n)的数量级O来粗略的表示算法的时间复 杂度，即T(n) = O ( f(n) )。 上例中的时间复杂度可粗略地表示为 T(n) = O( n2 ) 。 BISTU85 2、空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存空间算法的空间复杂度是指执行这个算法所需要的内存空间， 用S(n)表示，其中n表示问题的数据规模。 执行算法所需的内存空间其实包括两部分：固定空间和可 变空间。 固定空间是算法执行时运行环境本身所占用的内存空间， 与问题规模无关，不属于算法的空间复杂度考虑范围内的 空间； 可变空间是存储问题中的数据所占的空间。 一个算法所需的存储空间用f(n)表示，算法的

43、空间复杂度 S(n) = O ( f(n) )。 在实际应用中，设计算法时，只要计算机的内存容量许可 ，一般都是用空间换时间。 BISTU8686 BISTU87 RAPTOR基本程序环境 基本界面 BISTU88 四种基本符号/语句 目的目的符号符号名称名称 说明说明 输入 输入语句输 入 数 据 给 一个变量变量 处理 赋值语句使 用 各 类 运 算 来 更 改 的 变量变量的值 处理 过程调用执 行 一 组 在 命 名 过 程 中 定义的指令 输出 输出语句显 示变 量变 量的 值。 BISTU89 变量 变量（variable）表示的是计算机内存中的 位置，用于保存数据值 在任何时候，

44、一个变量只能容纳一个值 在程序执行过程中，变量的值可以改变 BISTU90 变量赋值过程 说明说明X的值的值程序程序 当程序开始时，没有 任何变量存在 未定义 第一个赋值语句，X32， 分配数据值32给变量X 32 下一个赋值语句， XX +1，检索到当前X的 值为32，给它加1，并把 结果33给变量X 33 下一个赋值语句，XX * 2，检索到X当前值为33， 乘以2，并把结果66给变 量X 66 BISTU91 RAPTOR变量值的设置 基本原则： 任何变量在被引用前必须存在并被赋值 变量的类型由最初的赋值语句所给的数据决定 设置方法 通过输入语句赋值 通过赋值语句的中的公式运算后赋值 通

45、过调用过程的返回值赋值 BISTU92 RAPTOR数据类型 数值（Number）： 如12，567，-4，3.1415，0.000371 字符串 （String）： 如“Hello， how are you?”， “James Bond”， “The value of x is： ” 字符（Character）： 如A，8，!。 BISTU93 变量报错的原因 未定义引用 BISTU94 变量报错的原因 拼写错 BISTU95 不同类型的数据不可比较 BISTU96 RAPTOR常量 RAPTOR定义了四个常量（Constant） pi（圆周率） 定义为 3.1416 e （自然对数的底）定

46、义为 2.7183 true /yes(布尔值: 真) 定义为 1 false/no(布尔值：假) 定义为 0 BISTU97 输入输入(Input)语句语句 输入语句的编辑 （Edit）对话框 提示部分 变量部分 BISTU98 输入输入(Input)语句语句 输入语句在流 程图中显示的 状态 运行时对话框 BISTU99 赋值语句（编辑） Set部分为接受赋值的变量或数组元素 To部分为表达式 BISTU100 赋值语句（显示） 流程图中的赋值语句 BISTU101 表达式表达式 可以是任何计算单个值的简单或复杂公式 是值（无论是常量或变量）和运算符的组 合。 例如，考虑下面的两个例子：

47、（1）x (3+9)/3（2）x 3+(9/3) BISTU102 表达式计算的“优先顺序” 1. 计算所有函数的值，然后； 2. 计算括号中表达式，然后； 3. 计算乘幂(，*)，然后； 4. 从左到右，计算乘法和除法，最后 5. 从左到右，计算加法和减法。 BISTU103 内置运算符和函数 数学运算: +，-，*，/，*（加、减、乘、除、乘方） mod， sqrt（求余，开平方） log， abs， （对数，绝对值） ceiling， floor （向下取整，向上取整） BISTU104 内置运算符和函数 三角函数: sin，cos，tan；正弦正弦 ，余弦余弦 ，正切正切 cot，ar

48、csin，arccos；余切余切 ，反正弦反正弦 ，反余弦反余弦 arctan， arccot；反正切反正切 ，反余切反余切 BISTU105 过程调用语句(编辑) 编辑对话框 注意已有过程提示 BISTU106 过程调用语句（显示） 注意，内置过程，子图，子程序的调用使 用同样的语句，但子图没有参数；内置过 程或子程序需要参数 BISTU107 输出语句 执行输出语句将 在主控（Master Console）窗口显 示输出结果 输出的结果可以 使用或不使用换 行操作 BISTU108 输出语句的设计技巧 BISTU109 注释 注释本身对计算机毫无意义，并不会被执 行。注释的目的是增强程序的

49、可读性，帮 助他人理解你所设计的程序或算法 BISTU110 一个带注释的算法 注释的四种类型： 1.编程标题 2.分节描述 3.逻辑描述 4.变量说明 BISTU111 RAPTOR基本程序环境 基本界面 BISTU112 四种基本符号/语句 目的目的符号符号名称名称 说明说明 输入 输入语句输 入 数 据 给 一个变量变量 处理 赋值语句使 用 各 类 运 算 来 更 改 的 变量变量的值 处理 过程调用执 行 一 组 在 命 名 过 程 中 定义的指令 输出 输出语句显 示变 量变 量的 值。 BISTU113 变量 变量（variable）表示的是计算机内存中的 位置，用于保存数据值

50、在任何时候，一个变量只能容纳一个值 在程序执行过程中，变量的值可以改变 BISTU114 变量赋值过程 说明说明X的值的值程序程序 当程序开始时，没有 任何变量存在 未定义 第一个赋值语句，X32， 分配数据值32给变量X 32 下一个赋值语句， XX +1，检索到当前X的 值为32，给它加1，并把 结果33给变量X 33 下一个赋值语句，XX * 2，检索到X当前值为33， 乘以2，并把结果66给变 量X 66 BISTU115 RAPTOR变量值的设置 基本原则： 任何变量在被引用前必须存在并被赋值 变量的类型由最初的赋值语句所给的数据决定 设置方法 通过输入语句赋值 通过赋值语句的中的公

51、式运算后赋值 通过调用过程的返回值赋值 BISTU116 RAPTOR数据类型 数值（Number）： 如12，567，-4，3.1415，0.000371 字符串 （String）： 如“Hello， how are you?”， “James Bond”， “The value of x is： ” 字符（Character）： 如A，8，!。 BISTU117 变量报错的原因 未定义引用 BISTU118 变量报错的原因 拼写错 BISTU119 不同类型的数据不可比较 BISTU120 RAPTOR常量 RAPTOR定义了四个常量（Constant） pi（圆周率） 定义为 3.141

52、6 e （自然对数的底）定义为 2.7183 true /yes(布尔值: 真) 定义为 1 false/no(布尔值：假) 定义为 0 BISTU121 输入输入(Input)语句语句 输入语句的编辑 （Edit）对话框 提示部分 变量部分 BISTU122 输入输入(Input)语句语句 输入语句在流 程图中显示的 状态 运行时对话框 BISTU123 赋值语句（编辑） Set部分为接受赋值的变量或数组元素 To部分为表达式 BISTU124 赋值语句（显示） 流程图中的赋值语句 BISTU125 表达式表达式 可以是任何计算单个值的简单或复杂公式 是值（无论是常量或变量）和运算符的组 合。 例如，考虑下面的两个例子： （1）x (3+9)/3（2）x 3+(9/3) BISTU126 表达式计算的“优先顺序” 1. 计算所有函数的值，然后； 2. 计算括号中表达式，然