数组、链表
| 特性 | 数组 | 链表 |
|---|
| 内存 | 连续 | 非连续 | | 访问 | 可随机访问（通过下标索引） | 只能遍历访问 | | 增删改查 | 内容固定，移动麻烦 | 内存可申请，节点变换容易 |
队列、栈
队列 先进先出
栈 先进后出
选择排序
原理：新建同等size缓存，一个个将数据按大小一个放入新缓存当中
源数据：
src:【7】【12】【6】【9】【8】
des:【】【】【】【】【】
Step1:
src:【7】【】【6】【9】【8】
des:【12】【】【】【】【】
Step2:
src:【7】【】【6】【】【8】
des:【12】【9】【】【】【】
Step3:
src:【7】【】【6】【】【8】
des:【12】【9】【】【】【】
Step4:
src:【7】【】【6】【】【】
des:【12】【9】【8】【】【】
Step5:
src:【】【】【6】【】【】
des:【12】【9】【8】【7】【】
Step6:
src:【】【】【】【】【】
des:【12】【9】【8】【7】【6】
算法思路之分治(D&C）
原理：
（1）找出简单的基线条件
（2）确定如何缩小问题的规模，使其符合基线条件
快速排序
原理：分治思维 递归
把数组缩小，再缩小，直到size为1或者0
int *qsort(int *Array, int Array_size)
{
if(Array_size <= 1)
{
return Array;
}
else
{
int left_size = 0;
int right_size = 0;
int temp = (int *)malloc(Array_size*sizeof(int))
for(int i = 1; i < Array_size; i++)
{
if(Array[0] > Array[i])
{
temp[left_size] = Array[i];
left_size++;
}
else
{
temp[Array_size-right_size-1] = Array[i];
right_size++;
}
}
temp[left_size] = Array[0];
memcpy(Array, temp, sizeof(int)*Array_size)
qsort(Array,left_size);
qsort(Array+left_size+1,right_size);
return Array;
}
}
散列表(散列映射、映射、字典、关联数组，在大多数语言已经实现)
-
散列函数特点：将输入映射到数字 -
它必须是一致的：固定输入，得到一定为固定输出 -
它应将不同的输入，映射到不同输出，即唯一性 -
举个例子应用散列函数，可以构建散列表。
Array：【】【】【】【】【】
假设输入苹果（单价5.9元），得到3
苹果->散列函数->3
Array：【】【】【5.9】【】【】
则可以把苹果存在3处，下次查找苹果价格时，直接输入苹果，取得3，直接访问数组index3。
广度优先搜索（非加权图的算法 回答最短路径问题）
- 用于有向图
- 依靠队列实现。
- 不断地把下一个点加入到队列里，直到查找到or最终找不到
- 注意去重
狄克斯特拉（加权图的算法 最短时间最短路径）
- 用于有向无环图
- 难点在于节点开销的更新，每次更新最新节点的最小。
贪婪算法
- 用于NP完全问题（要求计算每个可能的合集，查找最优，运算量巨大）
- 这是一种近似的解法，每次都选择最符合要求的那个。一路到底。
动态规划
- 用网格，逐渐增加横竖参量。
- 问题分解的思维
- 只能用于每个事物都是离散的，有相关性的话，就失灵了
最长公共子串
最长公共子序列
这两个字符串算法可能会被问到。
|