写给大家看的算法书笔记

一、什么是算法

1、算法是对特定问题的解决步骤（对信息进行排序、搜索目标信息等）

算法 → 更优质的算法 → 好的程序；

2、算法的两个必要条件：

• 准确性，证明方法——断言；

• 可停止性（死循环不能看做算法）；

3、几种重要的算法：

(1) 数论算法：

• 求解最大公约数的辗转相除法；

• 求解联立方程的高斯消元法；

• 求解定积分近似值的梯形公式;

• 计算质数的艾拉斯托尼筛法;

(2) 排序算法(按序排列)：

• 选择排序；

• 冒泡排序；

• 插入排序；

• 希尔排序;

• 归并排序;

• 快速排序；

(3) 搜索算法：（比较求同）

• 线性搜索；

• 二分搜索；

(4) 字符串匹配算法：

• 简单字符串搜索；

• KMP 算法；

• BM 算法；

4、结构化编程思想

旨在高效描述程序，最大限度减少设计误差的方法论，其中的处理流程结构组合包括：

(1) 顺序结构：按顺序处理；

(2) 选择结构：按条件处理；

(3) 循环结构：条件成立下，进行定量循环处理；

二、 变量和数组

算法由数据和处理构成；

(1) 基本数据类型：整数、浮点数、字符、布尔值及字符串；

(2) 描述数据信息的方法是数据值；

(3) 变量是存放数据值的容器，变量的作用是使处理过程通用化，每个变量只能存放一个数据，变量名是区分不同变量的标记，变量名要能表示所装载的数据；

(4) 把数据赋值给变量的过程叫代入；

(5) 数组是用来保存大量同一数据类型值的，数组索引，即数组元素的位置标号，可以利用数组进行关联数据的处理；

(6) 二维数组，数组元素沿横纵方向排列；

三、数据结构——高效的管理大量数据的构造

常用的数据结构：

(1) 数组，快速定位第 N 个数据；

(2) 链表，离散数据排序，快速插入删除数据（插入、删除数据不改变数据位置）。单向链表只能单向检索，元素由数据和“NEXT 指针”构成，HEAD 指针标记链表的第一个元素。双向链表元素由数据，PREV、NEXT 指针构成，可向前向后检索数据，链表为空的状态，HEAD 指针，TAIL 指针分别存储“没有起始元素”、“没有末尾元素”的信息；

(3) 堆栈（先进后出），数据操作：入栈 → 写入数据（push）→ 出栈（POP）→ 读取数据。考虑计算机优先级或者计算机管理子程序调用的顺序时用到；

(4) 队列（先进先出），应用在电文发放和接收中；

(5) 树，管理父节点数据和子节点数据，二叉树一个父节点对用两个子节点，可以用数组来表示二叉树；

(6) 图，自由的表示各种关系的数据。图的分类：有向图（边有方向性）、加权图（边有权重）；

四、算法基础

1、 循环处理和控制变量

(1) 循环处理：利用一个控制变量来管理循环次数，从而进行必要次数的处理；

(2) 循环处理的步骤：

• 设置控制变量的初始值；

• 判断循环条件，如果为 true，进行以下 3,4,步，否则为 false，终止处理；

• 执行循环体；

• 改变控制变量，回到步骤 2；

(3) 利用循环处理使处理过程通用化；

案例：

计算 1~N 的整数的总和。

算法：

JavaScript 代码：

2、 使用数组可以高效的处理大量数据

(1) 求斐波那契数列。

算法：

JavaScript 代码：

(2) 数组求和

计算一年的营业额。

算法：

JavaScript 代码：

(3) 求平均值

求班级考试的平均分。

算法：

JavaScript 代码：

(4) 求数组数据中的最大值

求最高分。

算法：

JavaScript 代码：

(5) 求数据中的最小值

求最低分。

算法：

JavaScript 代码：

(6) 为数组元素排序

为考试成绩排名。

算法：

JavaScript 代码：

(7) 二维数组操作

求全班学生不同科目考试合计总分。

算法：

JavaScript 代码：

(8) 求两个数的最大公约数

辗转相除法

算法：

JavaScript 代码：

2、排序算法

几种常用的排序算法

(1) 桶排序: 准备与待排序数据取值范围大小个数的木桶，利用这些木桶对数据进行保存、排序。

排序过程：

• 准备好木桶数据，把其所有元素初始化为 0；

• 把保存排序数组（n 个数据）的下标的变量 i 初始化为 0；

• i 小于 n 时，循环执行 4~5；

• 把 data[i]代入变量 value；

• bucket[value]加 1；

• i 加 1；

• 从 bucket 的起始元素开始，把每个数值非 0 的元素的下标按照数值（出现次数）取出来，排成一列。

(2) 选择排序: 遍历数据，把数据中的最大值（或最小值）与起始（或者末尾）数据进行交换。

排序过程：

• 从“待排序部分”中找到最小值；

• 把最小值和“待排序部分起始位置的元素”交换；

• “待排序部分”的起始位置向后移动一位；

• 循环操作 1~3，直至“待排序部分”只剩下一个元素。

(3) 冒泡排序: 对比相邻的两个数据，根据大小关系调整两个数据的顺序。

(4) 插入排序: 把目标数据按照正确的大小排列顺序插入相应的位置中。

(5) 归并排序: 把目标数据分割成更小的部分进行排序，更小的部分正确排序之后再合并起来。

(6) 希尔排序: 把目标数据按照一定的个数分成几个区域进行插入排序。

(7) 快速排序: 从目标数据中任意选取一个数据，以这个数据的值为分割点，把目标数据分割为两部分。这样循环操作下去进行排序。

3、搜索算法

常用的搜索算法：

• 线性搜索（随机排布的数据列中使用，效率比较低）；

• 二分搜索（已经排好序的数据列中使用，效率较高）；

• 利用哈希表进行搜索（高效搜索）；

• 简单字符串搜索（有长度的数据）；

• 利用 KMP 算法 进行字符串搜索；

• 利用 BM 算法进行字符串搜索。