1. 查找
查找表是指由同一类型的数据元素（记录）构成的集合。
- 静态查找表：只进行查找操作
- 动态查找表：除了查找，还需要进行插入和删除操作
1.1 顺序查找
从表的一端开始，逐个将记录的关键字与给定值进行比较。
1.2 折半查找（二分查找）
要求查找表必须采用顺序存储结构，并且按关键字有序排列。
1.3 分块查找
将查找表分成若干块，块内元素可以无序，但块与块之间必须有序。
1.4 哈希表
哈希函数的构造方法
- 除留余数法：H(key) = key % p
处理冲突的方法
- 开放地址法：当冲突发生时，形成一个探测序列，沿此序列逐个地址探测，直到找到一个空位置
- 链地址法：将所有关键字为同义词的记录存储在一个单链表中
2. 排序
2.1 排序的基本概念
排序是将一组记录按照某个关键字的大小进行排列的过程。
2.2 简单排序
直接插入排序
将待排序的记录逐个插入到已排好序的有序序列中。
简单选择排序
每一趟从待排序的记录中选出关键字最小的记录，按顺序放在已排好序的记录序列的最后。
冒泡排序
重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
2.3 希尔排序
将待排序的记录分成若干子序列，分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。
2.4 快速排序
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分继续进行排序。
2.5 堆排序
利用堆这种数据结构进行排序。堆是一个近似完全二叉树的结构，并同时满足堆积性质：即子结点的键值或索引总是小于（或大于）它的父节点。
2.6 归并排序（分治）
将两个或两个以上的有序表合并成一个新的有序表。
2.7 排序总结
| 排序方法 | 时间复杂度（平均） | 时间复杂度（最坏） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 直接插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 简单选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(n²) | O(1) | 不稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
评论