数组 容器 递归 普通排序 线性排序
《数据结构与算法之美》读书笔记
写在前面
这本书的大部分内容比较浅显，因此只挑DSAA课程上没有涉及或没有深入讨论的点总结
第二章
数组相关
-
提高传统数组插入/删除数据效率的方法：
- 如果插入的数据不要求有序，可以直接把某位的原数据替换成新数据，然后把原数据放到数组末尾，避免大面积的数据移动。
- 删除时不用一个一个删，可以先把要删的元素一个个标记好，等到数组中没有更多的存储空间时一并集中删除。
-
警惕C语言中数组访问越界的问题，通过内存公式计算出的内存地址是可用的，即便越界，程序也可能不报任何错。
-
容器（ArrayList/vector）VS 传统数组：
- 容器好用，上手快，封装性强，但有时需要装箱拆箱，存在性能损失。
- 插入数据时的扩容操作隐藏了复杂度，一行操作可能实际上远远不止。
- 对于底层的开发，性能优化需要做到极致，数组优于容器。
C和Java数组的实现方式
-
C/C++的多维数组也是从前往后连续存储，Java则是存储对象的引用。
-
JavaScript根据存储内容动态选择存储结构，可利用ArrayBuffer进行底层开发。
第三章
递归
-
堆栈溢出不一定是死循环，可能是递归太深，栈装不下了。
-
递归时常常会不小心重复计算，可以使用哈希表等事先检测是否已求解过。
-
尾递归可避免堆栈溢出，但在实际软件开发中并没有多大用途。
排序
-
稳定排序与非稳定排序：稳定排序保持相同元素相对顺序不变。
-
归并排序虽稳定但空间复杂度高，通常不如快速排序实用。
-
线性排序：
-
桶排序：适用于数据易于划分成若干个桶的场景，需注意内存占用和数据范围。
-
计数排序：桶内数据相同，适用于高考分数等场景，注意处理负数和时间复杂度。
-
基数排序：要求每位排序使用稳定排序算法，时间复杂度近似O(n)。
-