《写给大家看的算法书》笔记

一、什么是算法

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

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

• 算法的两个必要条件：

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

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

• 几种重要的算法：

• 数论算法：

  • 求解最大公约数的辗转相除法；
  • 求解联立方程的高斯消元法；
  • 求解定积分近似值的梯形公式;
  • 计算质数的艾拉斯托尼筛法;

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

  • 选择排序；
  • 冒泡排序；
  • 插入排序；
  • 希尔排序;
  • 归并排序;
  • 快速排序；

• 搜索算法：（比较求同）

  • 线性搜索；
  • 二分搜索；

• 字符串匹配算法：

  • 简单字符串搜索；
  • KMP算法；
  • BM算法；

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

• 顺序结构：按顺序处理；

  
  图片来源于网络

• 选择结构：按条件处理；

  
  图片来源于网络

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

  
  图片来源于网络

二、 变量和数组

1. 算法由数据和处理构成；

• 基本数据类型：
  • 整数；
  • 浮点数；
  • 字符；
  • 布尔值；
  • 字符串；
• 描述数据信息的方法是数据值；
• 变量是存放数据值的容器，变量的作用是使处理过程通用化，每个变量只能存放一个数据，变量名是区分不同变量的标记，变量名要能表示所装载的数据；
• 把数据赋值给变量的过程叫代入；
• 数组是用来保存大量同一数据类型值的，数组索引，即数组元素的位置标号，可以利用数组进行关联数据的处理；
• 二维数组，数组元素沿横纵方向排列；

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

1. 常用的数据结构：

• <b>数组</b>，快速定位第N个数据；

  
  图片来源于手机拍摄

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

  
  图片来源于网络

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

  
  图片来源于网络

• <b>队列</b>（先进先出），应用在电文发放和接收中；

  
  图片来源于网络

• <b>树</b>，管理父节点数据和子节点数据，二叉树一个父节点对用两个子节点，可以用数组来表示二叉树；

  
  图片来源于手机拍摄
  图片来源于手机拍摄
  图片来源于手机拍摄

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

  
  图片来源于手机拍摄

四、算法基础

1. 循环处理和控制变量

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

• 循环处理的步骤：

  • 设置控制变量的初始值；
  • 判断循环条件，如果为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. 几种常用的排序算法
   • 桶排序
     概念：
     准备与待排序数据取值范围大小个数的木桶，利用这些木桶对数据进行保存、排序。
     排序过程：
     （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，直至“待排序部分”只剩下一个元素。
   • 冒泡排序
     对比相邻的两个数据，根据大小关系调整两个数据的顺序。
   • 插入排序
     把目标数据按照正确的大小排列顺序插入相应的位置中。
   • 归并排序
     把目标数据分割成更小的部分进行排序，更小的部分正确排序之后再合并起来。
   • 希尔排序
     把目标数据按照一定的个数分成几个区域进行插入排序。
   • 快速排序
     从目标数据中任意选取一个数据，以这个数据的值为分割点，把目标数据分割为两部分。这样循环操作下去进行排序。

搜索算法

1. 常用的搜索算法：

• 线性搜索（随机排布的数据列中使用，效率比较低）；
• 二分搜索（已经排好序的数据列中使用，效率较高）；
• 利用哈希表进行搜索（高效搜索）；
• 简单字符串搜索（有长度的数据）；
• 利用KMP算法 进行字符串搜索；
• 利用BM算法进行字符串搜索。