数据结构

排序算法

快速排序

主要步骤：

1. 选择基准元素（pivot）：从数组中选择一个元素作为基准。
2. 划分（Partition）：将数组分为两部分，使得左边的元素都小于等于基准，右边的元素都大于等于基准。
3. 递归排序：对左右两部分分别递归地进行快速排序

空间复杂度：O(logn)

时间复杂度：

• 最好情况：O(n log n)，每次划分都均匀
• 最坏情况：O(n²)，每次划分都极不均匀（例如本来就升序或者降序）

如何避免？可以三数取中位数，作为基准元素

归并排序

时间复杂度：O(nlog n)

空间复杂度：O(n)

堆排序

堆：完全二叉树

1. 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
3. 直到数组有序

堆排序的时间复杂度为O(nlogn)，空间复杂度O(1)

C++的sort函数

一种内省排序，结合三个排序算法的有点

1. 快速排序 作为主要排序算法，因为它在平均情况下非常高效（O(n log n)）。
2. 当递归深度过大时（防止最坏情况 O(n²)），切换到堆排序，保证最坏情况下仍然是 O(n log n)。
3. 当子数组规模较小时（如 ≤16），切换到插入排序，为什么几十个数的时候用选择排序？小规模数据可能完全驻留在CPU缓存中，此时简单的顺序访问（如选择排序）可能比快速排序的分区跳跃访问更快，而且不需要额外的

二叉搜索树

1. 高效查找：平均 O(log n)，比线性搜索 O(n) 快
2. 动态维护有序数据：插入/删除后仍然保持有序
3. 中序遍历是升序

最坏情况下退化为链表，O(n)

为了优化 BST 的性能，可以使用 自平衡二叉搜索树：

• AVL 树：严格平衡，旋转操作保证 O(log n) 操作

B+树

数据库索引，BST思想，一种多路平衡搜索树，所有数据都存储在叶子节点

• 内部节点只存储键值，不存储数据
• 叶子节点通过指针连接形成有序链表

B+树的插入和删除，子节点的自下向上分裂和合并

B+树的所有叶子节点通过指针连接，形成一个有序链表，使得范围查询（如 WHERE age BETWEEN 20 AND 30）非常高效，只需找到范围的起始点，然后顺序遍历链表即可，无需回溯树结构

3层的 B+树就可以存储两千多万，一个结点可以存储关键字1170个，叶子节点存储的关键字可能少一点，因此一般不会超过4阶

红黑树

C++的std::map

• 每个节点是 红色或黑色
• 根节点是 黑色
• 红色节点的子节点必须是 黑色（不能有连续红色）
• 从任意节点到其叶子节点的路径包含相同数量的 黑色节点

应用场景：字典Map，集合Set

红黑树的调整开销小，插入删除比AVL更加高效，查询效率不如AVL，AVL适用于读多写少，红黑树适合频繁插入删除的

哈夫曼树

用于无损数据压缩

场景题

1. 如何从10亿数据中，找到top 100最大的数？
   • 考虑内存的情况，可以动态维护一个最小堆，如果当前的值比最小堆的堆顶元素大，就替换，并进行一次down操作，时间复杂度为O(nlogk)，空间复杂度为O(K)
   • map-reduce的思想，Map 阶段：每台机器处理自己的数据，得到本地的 Top 100；Reduce 阶段：将所有机器的 Top 100 合并，再计算全局 Top 100。