# 算法
## 冒泡排序的原理和实现
**原理**
两两相邻的数进行比较，如果反序就交换，否则不交换。
**编码**
~~~
$arr = [12, 4, 5, 7, 0, 3];
$len = count($arr);
for ($i=1; $i<$len; $i++) { // 做多少趟的排序：$len - 1
$exchange = false; // 交换标志，排序前为false
for ($j=$len-1; $j>=$i; $j--) { // 对当前排序区做自上而下的扫描
if ($arr[$j] < $arr[$j-1]) { // 后面 < 前面，则交换
$tmp = $arr[$j];
$arr[$j] = $arr[$j-1];
$arr[$j-1] = $tmp;
$exchange = true;
}
}
// 本趟没有发生交换，提前终止算法
if (!$exchange) {
return;
}
}
print_r($arr);
~~~
**分析**
时间复杂度：O(n<sup>2</sup>)
空间复杂度：O(1)
## 算法的概念
解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法的五个特征：
+ 有穷性
+ 确切性
+ 输入项
+ 输出项
+ 可行性
## 时间复杂度和空间复杂度
时间复杂度：执行算法所需要的计算工作量。一般来说，计算机算法是问题规模`n`的函数`f(n)`，算法的时间复杂度记为`T(n) = O(f(n))`。
### 时间复杂度的计算方式
+ 算法的计算次数公式
+ 用常数1代替所有时间中的加法常数，如：`O(3) => O(1)`
+ 运行次数是一个多项幂次式，只保留最高阶，如： O(n<sup>2</sup>+n) => O(n<sup>2</sup>)
+ 如果表达式中最高次幂存在系数且不为1，则将其改为1，如：O(4n<sup>2</sup>+2n+1) => O(n<sup>2</sup>)
常见的时间复杂度：
+ 常数阶：O(1)
+ 线性阶：O(n)
+ 平方/立方阶：O(n<sup>2</sup>) /O(n<sup>3</sup>)
+ 指数阶： 2<sup>n</sup>
+ 对数阶：O(log<sub>2</sub>n)
~~~php
while ($n>=1) {
$n = $n /2;
}
~~~
分析：
| n | 执行次数 |
| --- | --- |
| 1 | 1 |
| 2 | 2 |
| 3 | 2 |
发现以上的操作发现不了规律，所以做以下的分析：
常见时间复杂度的效率：
O(1) > O(log<sub>2</sub>n) > O(n) > O(nlog<sub>2</sub>n) > O(n<sup>2</sup>) > O(n<sup>3</sup>) > O(2<sup>n</sup>) > O(n!) > O(n<sup>n</sup>)
### 其他概念
**最坏情况**：最坏情况下的运行时间。如果没有特别说明，时间复杂度即为最坏情况的时间复杂度。
**平均情况**：
### 空间复杂度
算法需要消耗的内存空间，记作`S(n) = O(f(n))`
包含以下三个部分：
+ 程序代码所占用的空间
+ 输入数据所占用的空间
+ 辅助变量所占用的空间
**空间复杂度的计算方式**
有时用空间换时间。
## 常见的排序算法
+ 冒泡排序
+ 直接插入排序
+ 希尔排序
+ 选择排序
+ 快速排序
+ 堆排序
+ 归并排序
## 常见的查找方法
+ 二分查找
+ 顺序查找
# 数据结构
+ Array：数组
特性：使用连续的内存来存储，数组中的元素必须是相同的类型（或类型的衍生）、元素可以通过下标访问
+ LinkedList：线性链表
元素之间是一对一的关系（除了第一个和最后一个，其他元素都是收尾相接）、顺序存储和链式存储结构两种
+ Stack：栈
特性：存储数据是先进后出，栈只有一个出口，只能从栈顶增加或删除元素
+ Heep：堆
特性：子节点的健值或索引总是小于它的父节点，每个节点的左右子树又是一个二叉堆，又分为大根堆、小根堆。
+ List：线性表
特性：第一个元素无先驱，最后一个元素无后继，其他元素只有一个先驱和一个后继，0个元素构成的线性表是**空表**。
+ DoublyLinkedList：双向链表
特性：每个元素都是一个对象，每个对象有一个关键字key和两个指针（prev、next）
+ Queue：队列
特性：先进先出，并发中使用可以安全的将对象从一个任务传给另一个任务
+ Set：集合
特性：保存不重复的元素
+ Map：字典
特性：关联数组也被叫做字典或键值对
+ Graph：图
特性：通常使用**邻接矩阵**和**邻接表**表示，前者易实现但对于稀疏矩阵会浪费较多空间，后者使用**链表**的方式存储信息但对于图搜索时间复杂度较高。
# 其他逻辑算法
