算法面试题：排序与查找

1. 常见排序算法有哪些？

• 冒泡排序、插入排序、选择排序。
• 快排、归并排序、堆排序。
• 基数排序适合整数和固定长度字符串。

2. 快排与归并排序的时间复杂度是多少？

• 快排平均 O(n log n)，最坏 O(n^2)。
• 归并排序稳定 O(n log n)，但额外空间开销较大。

3. 二分查找的前提是什么？

• 数据必须有序。
• 递归与迭代方式都可以实现。
• 需要注意边界条件和循环终止条件。

4. 在什么情况下选择 O(n^2) 的排序算法？

• 数据量较小。
• 实现简单、开销低的场景。
• 对稳定性或内存有特定要求时。

5. 如何判断一个排序算法是否稳定？

• 如果相同键值的数据保持相对顺序，则稳定。
• 例如归并排序、插入排序是稳定的，快排和堆排通常不稳定。

6. 你会如何实现一个高效的查找结构？

• 哈希表适合快速查找和去重。
• 二叉搜索树适合有序数据检索。
• B 树适合磁盘存储场景。

7. 查找性能与数据结构的关系是什么？

• 数组顺序查找 O(n)。
• 哈希表平均 O(1)。
• 二叉搜索树平均 O(log n)。

8. 你如何优化大型数据集的查找？

• 用索引或分片提高查询效率。
• 采用缓存层减少热点访问。
• 预处理数据结构以减少扫描量。