数据结构与算法 面试题目总结
HeZephyr1 排序算法
| 排序算法 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据对象稳定性 | 算法基本思路 |
|---|---|---|---|---|---|
| 冒泡排序 | $$O(n^2)$$ | $$O(n^2)$$ | $$O(1)$$ | 稳定 | 反复交换相邻逆序的元素，直到没有逆序对 |
| 选择排序 | $$O(n^2)$$ | $$O(n^2)$$ | $$O(1)$$ | 数组不稳定、链表稳定 | 反复选择未排序部分中的最小（大）元素，放在已排序部分的末尾 |
| 插入排序 | $$O(n^2)$$ | $$O(n^2)$$ | $$O(1)$$ | 稳定 | 逐一选择未排序元素，将其插入到已排序部分的正确位置 |
| 快速排序 | $$O(n \log_2 n)$$ | $$O(n^2)$$ | $$O(\log_2 n)$$ | 不稳定 | 选择基准，将数组分为小于和大于基准的两部分，递归排序 |
| 堆排序 | $$O(n \log_2 n)$$ | $$O(n \log_2 n)$$ | $$O(1)$$ | 不稳定 | 构建最大（小）堆，将堆顶元素与末尾元素交换，调整堆 |
| 归并排序 | $$O(n \log_2 n)$$ | $$O(n \log_2 n)$$ | $$O(n)$$ | 稳定 | 递归地将数组分为两部分，分别排序后合并 |
| 希尔排序 | $$O(n \log_2 n)$$ | $$O(n^2)$$ | $$O(1)$$ | 不稳定 | 分组进行插入排序，逐渐减少间隔，直到间隔为1 |
| 计数排序 | $$O(n + m)$$ | $$O(n + m)$$ | $$O(n + m)$$ | 稳定 | 统计每个元素的出现次数，根据计数对元素进行排序 |
| 桶排序 | $$O(n)$$ | $$O(n)$$ | $$O(m)$$ | 稳定 | 将元素分配到不同的桶中，分别排序后合并 |
| 基数排序 | $$O(k \cdot n)$$ | $$O(n^2)$$ | 取决于实现 | 稳定 | 逐位排序，从最低有效位到最高有效位进行 |
2 栈与队列的区别
- 队列（Queue）：是限定只能在表的一端进行插入和在另一端进行删除操作的线性表；
- 栈（Stack）：是限定只能在表的一端进行插入和删除操作的线性表。
- 队列先进先出，栈先进后出。
- 栈只能在表尾插入删除，队列在表尾插入表头删除。
- 应用场景不同：
- 栈：括号问题的求解等
- 队列：计算机系统中各种资源的管理等。
- 遍历速度不同：
- 队列：基于地址指针进行遍历，而且可以从头部或者尾部进行遍历，但不能同时遍历，无需开辟空间，因为在遍历的过程中不影响数据结构，所以遍历速度要快；
- 栈：只能从顶部取数据，也就是说最先进入栈底的，需要遍历整个栈才能取出来，而且在遍历数据的同时需要为数据开辟临时空间，保持数据在遍历前的一致性。
3 两个栈实现一个队列
使用两个栈来实现一个队列，可以有效地利用栈的特性（后进先出）来模拟队列的特性（先进先出）。我们可以使用两个栈来分离入队和出队操作，具体实现步骤如下：