一、什么是算法
- 算法是对特定问题的解决步骤（对信息进行排序、搜索目标信息等）；
算法→更优质的算法→好的程序；
算法的两个必要条件：
准确性，证明方法——断言；
可停止性（死循环不能看做算法）；
几种重要的算法：
-
数论算法：
- 求解最大公约数的辗转相除法；
- 求解联立方程的高斯消元法；
- 求解定积分近似值的梯形公式;
- 计算质数的艾拉斯托尼筛法;
-
排序算法(按序排列)：
- 选择排序；
- 冒泡排序；
- 插入排序；
- 希尔排序;
- 归并排序;
- 快速排序；
-
搜索算法：（比较求同）
- 线性搜索；
- 二分搜索；
-
字符串匹配算法：
- 简单字符串搜索；
- KMP算法；
- BM算法；
结构化编程思想：旨在高效描述程序，最大限度减少设计误差的方法论，其中的处理流程结构组合包括：
-
顺序结构：按顺序处理；
图片来源于网络 -
选择结构：按条件处理；
图片来源于网络 -
循环结构：条件成立下，进行定量循环处理；
图片来源于网络
二、 变量和数组
- 算法由数据和处理构成；
- 基本数据类型：
- 整数；
- 浮点数；
- 字符；
- 布尔值；
- 字符串；
- 描述数据信息的方法是数据值；
- 变量是存放数据值的容器，变量的作用是使处理过程通用化，每个变量只能存放一个数据，变量名是区分不同变量的标记，变量名要能表示所装载的数据；
- 把数据赋值给变量的过程叫代入；
- 数组是用来保存大量同一数据类型值的，数组索引，即数组元素的位置标号，可以利用数组进行关联数据的处理；
- 二维数组，数组元素沿横纵方向排列；
三、数据结构——高效的管理大量数据的构造
- 常用的数据结构：
-
<b>数组</b>，快速定位第N个数据；
图片来源于手机拍摄 -
<b>链表</b>，离散数据排序，快速插入删除数据（插入、删除数据不改变数据位置）。单向链表只能单向检索，元素由数据和“NEXT指针”构成，HEAD指针标记链表的第一个元素。双向链表元素由数据，PREV、NEXT指针构成，可向前向后检索数据，链表为空的状态，HEAD指针，TAIL指针分别存储“没有起始元素”、“没有末尾元素”的信息；
图片来源于网络 -
<b>堆栈</b>（先进后出），数据操作：入栈→写入数据（push）→出栈（POP）→读取数据。考虑计算机优先级或者计算机管理子程序调用的顺序时用到；
图片来源于网络 -
<b>队列</b>（先进先出），应用在电文发放和接收中；
图片来源于网络 -
<b>树</b>，管理父节点数据和子节点数据，二叉树一个父节点对用两个子节点，可以用数组来表示二叉树；
图片来源于手机拍摄
图片来源于手机拍摄
图片来源于手机拍摄 -
图，自由的表示各种关系的数据。图的分类：有向图（边有方向性）、加权图（边有权重）；
图片来源于手机拍摄
四、算法基础
- 循环处理和控制变量
循环处理：利用一个控制变量来管理循环次数，从而进行必要次数的处理；
-
循环处理的步骤：
- 设置控制变量的初始值；
- 判断循环条件，如果为true，进行以下3,4,步，否则为false，终止处理；
- 执行循环体；
- 改变控制变量，回到步骤2；
-
利用循环处理使处理过程通用化；
<b>案例：</b>
计算1~N的整数的总和。
算法：
JavaScript代码：
-
使用数组可以高效的处理大量数据
<b>案例：</b>
求斐波那契数列。
算法：
JavaScript代码：
-
数组求和
<b>案例：</b>
计算一年的营业额。
算法：
JavaScript代码：
-
求平均值
<b>案例：</b>
求班级考试的平均分。
算法：
JavaScript代码：
-
求数组数据中的最大值
<b>案例：</b>
求最高分。
算法：
JavaScript代码：
-
求数据中的最小值
<b>案例：</b>
求最低分。
算法：
JavaScript代码：
-
为数组元素排序
<b>案例：</b>
为考试成绩排名。
算法：
JavaScript代码：
-
二维数组操作
<b>案例</b>
求全班学生不同科目考试合计总分。
算法：
JavaScript代码：
-
求两个数的最大公约数
<b>案例：</b>
辗转相除法
算法：
JavaScript代码：
排序算法
- 几种常用的排序算法
- 桶排序
概念：
准备与待排序数据取值范围大小个数的木桶，利用这些木桶对数据进行保存、排序。
排序过程：
（1）准备好木桶数据，把其所有元素初始化为0；
（2）把保存排序数组（n个数据）的下标的变量i初始化为0；
（3）i小于n时，循环执行4~5；
（4）把data[i]代入变量value；
（5）bucket[value]加1；
（6）i加1；
（7）从bucket的起始元素开始，把每个数值非0的元素的下标按照数值（出现次数）取出来，排成一列。 - 选择排序
概念：
遍历数据，把数据中的最大值（或最小值）与起始（或者末尾）数据进行交换。
排序过程：
（1）从“待排序部分”中找到最小值；
（2）把最小值和“待排序部分起始位置的元素”交换；
（3）“待排序部分”的起始位置向后移动一位；
（4）循环操作1~3，直至“待排序部分”只剩下一个元素。 - 冒泡排序
对比相邻的两个数据，根据大小关系调整两个数据的顺序。 - 插入排序
把目标数据按照正确的大小排列顺序插入相应的位置中。 - 归并排序
把目标数据分割成更小的部分进行排序，更小的部分正确排序之后再合并起来。 - 希尔排序
把目标数据按照一定的个数分成几个区域进行插入排序。 - 快速排序
从目标数据中任意选取一个数据，以这个数据的值为分割点，把目标数据分割为两部分。这样循环操作下去进行排序。
- 桶排序
搜索算法
- 常用的搜索算法：
- 线性搜索（随机排布的数据列中使用，效率比较低）；
- 二分搜索（已经排好序的数据列中使用，效率较高）；
- 利用哈希表进行搜索（高效搜索）；
- 简单字符串搜索（有长度的数据）；
- 利用KMP算法 进行字符串搜索；
- 利用BM算法进行字符串搜索。
