三大类CS算法的总结

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

基于用途对算法分类(参考Princeton CS算法课程)：
Sorting algorithm
Searching algorithm
Graph 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.
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.

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)]

Hathaway Zhu