数据结构和算法知识整理
数据结构和算法知识整理
排序算法哪些是稳定排序？
快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法。
基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
几种排序的应用场景
- 若n较小（数据规模较小），插入排序或选择排序较好
- 若数据初始状态基本有序（正序），插入、冒泡或快速排序为宜
- 若n较大，则采用时间复杂度为O(nlogn)的排序方法：快速排序或堆排序
- 快速排序是目前基于比较的排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
- 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
递归的优缺点
优点：
1 简洁
2.在树的前序，中序，后序遍历算法中，递归的实现明显要比循环简单得多。
缺点：
1.递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址以及临时变量，而往栈中压入数据和弹出数据都需要时间。->效率
2.递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算，如fibonacci斐波那契数列的递归实现。->效率
3.调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。->性能
哈希冲突的四种解决方法
- 开放定址法
线性探测再散列
平方探测再散列 - 链地址法
将所有哈希地址相同的记录都链接在同一链表中 - 再哈希法
产生冲突时计算另一个哈希函数地址，直到冲突不再发生为止。 - 建立一个公共溢区