第八章 算法
8.1 概念
8.1.1 非正式定义
是一种逐步解决问题或完成任务的方法，按照这种定义，算法完全独立于计算机系统
计算机算法接收一组输入数据，同时产生一组输出数据
8.1.2 示例
求5个正整数的最大值：
8.1.3 实义动作
8.1.4 细化
8.1.5 泛化
8. 2 三种结构
计算机专家为结构化程序或算法定义了三种结构，这种想法认为程序必定是由顺序、判断（选择）和循环组成，已经证实其他结构是不必要的
8.3 算法的表示
- 使用UML和伪代码来表示算法
- UML（统一建模语言）是算法的图形表示法，使用图的形式掩盖了算法的所有细节，只显示算法从开始到结束的整个流程
- 伪代码是算法的一种类似英语的表示法，现在还没有伪代码的标准
8.3.1 UML
8.3.2 伪代码
请看下面的例子：
8.4 更正式的定义
算法是一组明确步骤的有序集合，它产生结果并在有限的时间内终止
8.4.1 定义良好
算法必须是一组**定义良好（最优算法）**且有序的指令集合
8.5 基本算法
8.5.1 求和
对一组数据求和
- 将和（sum）初始化
- 循环，在每次迭代中将一个新数加到sum上
- 退出循环后返回结果
8.5.2 乘积
对一组数据的乘积
- 将乘积（product）初始化
- 循环，在每次迭代中将一个新的数与product相乘
- 退出循环后返回结果
8.5.3 最大和最小
求一组数据的最大和最小值
8.5.4 排序
根据一组数据的值对它们进行排序
- 选择排序
- 冒泡排序
- 插入排序
这三种排序方法是当今计算机科学中使用的快速排序的基础
选择排序：
数字列表可分成两个子列表（已排序和未排序），它们通过假想的一堵墙分开。求未排序子列表中最小的元素并把它和未排序子列表中第一个元素进行交换，经过每次选择和交换，两个子列表中假想的墙向前移动一个元素，这样每次已排序列表中将增加一个元素而未排序列表中减少一个元素，每次把一个元素从未排序列表移到已排序列表就完成了一轮排序。
选择排序示例：
选择排序-UML图解
冒泡排序：
数字列表被分为两个子列表：已排序和未排序。在未排序子列表中，最小的元素通过冒泡的方法选出并移到已排序子列表中，当把最小的元素移到已排序列表之后，墙向前移动一个元素，使得已排序元素的个数加1，而未排序元素的个数减少1个。每次元素从未排序子列表中移到已排序子列表中，最终完成排序。
冒泡排序示例：
插入排序：
排序列表被分为已排序和未排序两个列表。在每轮中，把未排序子列表中的第一个元素转移到已排序的子列表中，并插入到合适的位置
插入排序示例：
三种排序算法的总结：
这里的三种排序是最低效的排序算法
- 思路简单，容易理解和实现
- 是高效排序算法的基础
- 高效排序：快速排序、堆排序、希尔排序、桶排序、合并排序、基排序等
8.5.5 查找
是一种在列表中确定目标所在位置的算法
两种基本查找方法：
- 顺序查找：被查找的列表可以无序
- 折半查找：被查找的列表是有序的
顺序查找
顺序查找：用于查找无序列表，一般用于查找较小的或不常用的列表
顺序查找是从列表起始处开始查找，当找到目标元素或确信查找的目标不在列表中时，查找过程结束
顺序查找示例：
折半查找（又名：二分查找）
折半查找：当列表中的元素很多时，顺序查找的速度很慢，当列表有序时，可以通过折半查找提高查找速度
折半查找从列表的中间元素来判断，判断出目标在列表的前半部分还是后半部分，如果在前半部分，就不需要再查找后半部分。如果在后半部分，就不需要再查找前半部分，重复这个过程，直到找到目标或目标不在列表中
折半查找示例：
8.6 子算法
子算法：结构化编程的原则要求将算法分成几个单元，称为子算法。
主算法
每个子算法依次又可以分为更小的子算法
使用子算法的优点：
- 程序更容易理解
- 子算法可以在主算法中不同地方调用
选择排序中的子算法：
8.7 递归
递归：是自我调用的过程
8.7.1 迭代的定义
8.7.2 递归的定义
递归的定义：每一个算法出现在它本身定义中，该算法就是递归的定义。
