一、什么是算法

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 算法进行字符串搜索。