基础算法原理

最近，补了一下数据结构和算法的基础知识。参考书籍-《算法》by Sedgewick 。现整理如下：

基础数据类型

背包

API 如下所示：
- Bag()
- size();
- isEmpty();
- add(Item item);

队列

API 如下：
- Queue();
- enqueue();
- dequeue();
- size();
- isEmpty();

下压栈

API 如下：
- Stack();
- push(Item item);
- pop();
- size();
- isEmpty();

算法分析

算法分析的指标主要有两个：
- 时间复杂度（增长数量级）。
- 空间复杂度（内存）。

增长数量级指的是程序运行的总次数，分为一下7个等级：
- 常数级别 1;
- 对数级别 logN，二分策略，如二分查找；
- 线性级别 N，循环，如单层循环；
- 线性对数级别 N*logN，分治，如归并排序；
- 平方级别 N^2，双层循环;
- 立方级别 N^3， 三层循环;
- 指数级别 2^N，穷举查找；

基础排序算法

快速排序

原理：
- 找到一个基准数，把比他大的放在左边，比他小的放在右边。
- 切分，递归。

插入排序

原理：
- 从第二个数开始，如果比第一个数大，就放在第一个数的右边，否则，就与第一个数交换位置。
- 第三个数依次它左边的数比较，并插入合适的位置。
- 后面的数依次执行重复操作。

冒泡排序

原理：
- 将第一个数与后面所有的数依次比较，如果大于后面的数，就交换位置。这样最大的数就浮到了最后一个。
- 后面的数依次重复上一个步骤。

归并排序

• 前提是两个有序数组。
• 将两个有序数组的第一个数相比较，将其中较小的那个拿出来，放在一个新数组中，并指向原数组中的下一个。
• 递归。

基础查找算法

快速查找

原理：
- for循环整个数组，如果找到与目标值相等的，就返回其下标。

二分查找

原理：
- 前提是有序数组。
- 将数组分成两部分，如果目标值大于中间值，就在右边继续查找。若小于，就在左边继续查找。若等于，就返回其下标。

二叉查找树

原理：
- 结点左边的数都比结点小，结点右边的数都比结点大。

本文原创 https://duckhere.blogspot.com/， 转载请注明出处。