## 三大类CS算法的总结

根据我们之前的post–why数据结构与算法中写道

基于用途对算法分类(参考Princeton CS算法课程)：

Sorting algorithm

Searching algorithm

Graph algorithm

Recursive and iterative algorithm的区别

**Both repeatedly execute**the set of instructions. 通常我们尽量避免使用recursion, 而更倾向于使用iteration。**Recursion**: when a statement in a function**calls itself repeatedly**.- 格式: 总共有2 parts.
- A base case: The base case defines the termination condition.
- The general recursive case: The general case where it calls itself.

- Infinite recursion can crash the system because it uses a stack.
- 速度: Slow in execution.

- 格式: 总共有2 parts.
**Iteration**: when a loop repeatedly executes**until the controlling condition becomes false**.- 格式: 总共有4 parts. Initialization, termination condition, execution of statement within the loop, and update the control variable.
- Infinite loop uses CPU cycles repeatedly because it does not use a stack.
- 速度:Fast in execution.

#### Sorting algorithm

Sort a list or array of $n$ elements, and the smallest one is to put on the left, the largest one on the right.

**Bubble Sort**：Starting on the left, compare adjacent items and keep “bubbling” the larger one to the right (it’s in its final place). Bubble sort the remaining $n -1$ items. [Best: O(n), Worst:O(N^2)]