本篇整理常见查找与排序算法，并从时间复杂度、空间开销和数据特征出发比较算法选择。

1. 查找算法

本章从「顺序查找」「二分查找」和「树表的查找」等方面说明查找算法。

1.1 顺序查找

查找过程为：从表中一端开始，依次比较表中元素和给定的目标值，如果元素值等于目标值，则查找成功。
时间复杂度：O(N)
空间复杂度：O(1)
如果数组无序且数组规模比较小，那么可以使用；如果规模很大，这个实现性能会很差

1.2 二分查找

二分查找也称为折半查找。使用二分查找的前提是数组元素必须是有序的。查找过程为：给定一个数组和一个目标值，从表的中间位置开始记录，如果目标值和中间元素相同，则查找成功；如果中间元素小于或大于目标值，则在比中间值大或小的那一半中查找。重复操作，直到查找成功。实现代码有两种写法，取决于给定的查找范围是左闭右闭还是左闭右开的。
时间复杂度：O(logN)
空间复杂度：O(1)
时间复杂度计算过程：
第一次比较，剩余规模 n/2
第二次比较，剩余规模 n/4
第三次比较，剩余规模 n/8
……
第 k 次比较，剩余规模
在最坏情况下，搜索区间只剩最后一个元素，所以我们的 k 满足；
所以 ，时间复杂度为

1.3 树表的查找

树表是利用树形结构组织的数据查找表，其目标是实现 级别的高效查找、插入和删除操作。
1.3.1 二叉排序树（BST）
又称为二叉查找树、二叉搜索树，是一种特殊的二叉树，满足以下基本特性：
  1. 左小右大：左边的节点小于中间的节点，中间的节点小于右边的节点
  1. 左右子树本身也分别是二叉排序树
  1. 中序遍历 BST 得到的序列是完全有序的
平均时间复杂度：O(log N)
最坏时间复杂度：O(N)
1.3.2 平衡二叉树（AVL）
是最早被发明的自平衡二叉树，严格满足以下特性：
  1. 任意节点左右子树的高度差的绝对值不超过 1
  1. 平衡因子 = 左子树高度 − 右子树高度
平均时间复杂度（查找、增删）：O(log N)
1.3.3 红黑树
红黑树是一种在平衡性和维护成本很好的折中的自平衡二叉排序树，每个节点被标记为黑色或红色。
满足以下规则：
  1. 根节点是黑色
  1. 叶子节点是黑色
  1. 如果一个节点是红色，那么它的两个子节点必须是黑色
  1. 从任意节点出发到其所有叶子节点上包含的黑色节点数量必须相等（黑色平衡）
平均时间复杂度（查找、增删）：O(log N)
1.3.4 B 树
B 树是一种多路搜索树，它的设计初衷是为了优化外部存储（如硬盘、SSD）的数据查找效率，与前面几种树的内存优化目标不同。
查找复杂度：。虽然理论上与 级别相似，但在外部存储中，M 越大，I／O 次数越少，实际性能越好。

2. 排序算法

本章从「直接插入排序」「二分插入排序」和「希尔排序」等方面说明排序算法。

2.1 直接插入排序

基本思想：类似于我们整理扑克牌，逐个顺序比较后插入。将数组分为已排序和未排序两个部分，第一个元素放入已排序部分，和未排序部分比较，直到排序完成。
时间复杂度：
  • 最好情况：O(n) - 数组已经有序
  • 最坏情况：O(n²) - 数组完全逆序
  • 平均情况：O(n²)
适用条件：当数据规模小、数据基本有序时可以使用。

2.2 二分插入排序

基本思想：二分插入排序是对直接插入排序的优化，在寻找插入位置时用二分查找代替顺序查找，减少了比较次数，但是移动次数不变。
时间复杂度：
  • 比较次数：O(n log n)
  • 移动次数：O(n²)
  • 总时间复杂度：O(n²)
适用条件：比较代价比较高的时候使用。

2.3 希尔排序

基本思想：也是对直接插入排序改进，又称为缩小增量排序，分组比较代替逐个比较。将原序列分成多个子序列进行插入排序，缩小间隔。重复以上过程，直到排序完成。
常见的增量序列：
  1. 希尔增量：n/2, n/4, …, 1
  1. Hibbard 增量：1, 3, 7, 15, …, 2^k-1
  1. Sedgewick 增量：1, 5, 19, 41, …
时间复杂度：
  • 最好情况：O(n log n)
  • 最坏情况：O(n²) - 使用希尔增量时
  • 平均情况：取决于增量序列
适用条件：中等规模数据时使用。

2.4 冒泡排序

基本思想：比较相邻元素，如果第一个元素比第二个元素大，则交换两个元素的位置。比较每一对•相邻元素，最后的元素一定是未排序中最大的。重复以上操作，直到排序完成。
时间复杂度：
  • 平均时间复杂度：O(N^2)
  • 交换次数：O(N^2)
  • 空间复杂度：O(1)
适用条件：小规模数据、数组基本有序、内存受限的情况。

2.5 选择排序

基本思想：在冒泡排序的基础上改进了交换次数，从第一个元素开始和后面的所有元素相比，比较出最小的元素，先记录下标，跟最后一个元素比较完之后再交换位置，得到最小元素。重复以上过程，直到排序完成。
时间复杂度：
  • 平均时间复杂度：
  • 交换次数：O(N)
  • 空间复杂度：O(1)
适用条件：小规模数据且比较代价高，内存受限的情况。

2.6 快速排序

基本思想：采用分治策略。选择一个基准元素，通过一趟排序将序列分隔成独立的两个部分，其中左边部分的所有元素比基准元素小，右边部分的所有元素都比基准元素大，然后再对这两个部分递归排序。
其中基准元素一般选：第一个元素、最后一个元素、中间元素。
时间复杂度
  • 平均时间复杂度：
  • 最坏时间复杂度：
  • 空间复杂度：
适用条件：当数据规模比较大、内存空间受限、数据分布随机时可以使用快排，但是如果数据分布本来就比较有序，选择最后一个元素作为基准时就容易将时间复杂度退化为。

2.7 堆排序

堆排序是一种树形选择排序，可以将待排序的数组看成是一颗完全二叉树的顺序存储结构。基本思想：排序规则是根节点小于或大于子节点，这样就可以将待排序序列构造成一个小顶堆或者是大顶堆。将堆顶元素和末尾元素交换，将剩余元素重新调整成堆，重复以上过程，直到堆中只剩一个元素。
堆的特性：
  1. 结构性：堆是一颗完全二叉树，底层节点从左到右填入
  1. 堆序性：
堆排序示意图
堆排序示意图
时间复杂度：（平均、最好、最坏）
空间复杂度：
适用条件：内存受限，且需要时间复杂度保证的场景。

2.8 归并排序

本节从「分治法」「单链表实现」和「数组实现」等方面说明归并排序。
2.8.1 分治法
分治通常包含三个步骤：
  1. 分解：将原问题拆成规模更小的子问题；
  1. 解决：递归或迭代处理子问题；
  1. 合并：组合子问题结果。
归并排序把“合并”作为核心步骤；快速排序则通过分区把元素放到基准值两侧，再分别处理两个子区间。
2.8.2 单链表实现
链表适合归并排序的原因：链表可以通过调整指针合并有序序列，不依赖随机访问。
  • 找中点可使用快慢指针；
  • 合并有序链表只需调整 next 指针；
  • 不依赖随机访问；
  • 时间复杂度稳定为 O(n log n)；
  • 可以保持稳定性。
递归实现：先使用快慢指针拆分链表，再递归排序并合并两个有序链表。
复杂度：
  • 时间复杂度：O(n log n)
  • 辅助空间复杂度：O(log n)，主要来自递归调用栈
边界条件中，下面这种写法：
在 head == nullptr 时会发生空指针解引用，应写成：
优先队列中转法：先把节点值放入小根堆，再按升序写回链表。
将节点值放入小根堆，再按顺序写回：
  • 时间复杂度：O(n log n)
  • 空间复杂度：O(n)
  • 实现简单；
  • 只改变值，不改变节点顺序。
如果题目要求真正重排节点、节点身份有意义，或节点除 val 外还含有相关数据，只交换/覆盖 val 可能不符合要求。
2.8.3 数组实现
复杂度：
  • 时间复杂度：O(n log n)
  • 空间复杂度：O(n)
  • 稳定：在相等时优先取左侧元素
常见应用：
  • 逆序对；
  • 外部排序；
  • 链表排序；
  • 需要稳定性的排序。
数组归并排序和链表归并排序示例已使用 C++17 编译，并在开启 -Wall -Wextra -Wpedantic -Werror 后通过空数组、重复值、负数及链表排序测试。

2.9 桶排序

基本思想：桶排序的思想不是基于比较来实现的，而是通过分配来实现的一种排序算法。设置固定数量的空桶；遍历数组，将每个元素放入对应的桶里；对每个非空桶进行排序，按照顺序把每个桶里的元素放回原数组。
平均时间复杂度：
最坏时间复杂度：
空间复杂度：
适用条件：数据分布均匀，数据范围有限。如整理扑克牌、给学生成绩排序。

3. 计数排序与基数排序

本章围绕「非比较排序」展开，先明确核心概念与适用边界。

3.1 非比较排序

本节从「计数排序」和「基数排序」两方面说明非比较排序。
3.1.1 计数排序
  • 适合整数键范围较小；
  • 时间复杂度通常为 O(n + k)；
  • 空间复杂度通常为 O(k)；
  • 是否稳定取决于具体实现。
3.1.2 基数排序
  • 按位或按字符分阶段排序；
  • 每一阶段通常要求稳定的子排序；
  • 复杂度取决于位数、基数和子排序；
  • 适合定长整数、字符串等特定键。

4. 数据结构与算法选择建议

  • vector 和数组适合需要随机访问及缓存友好的场景。
  • 需要链表排序：优先归并排序。
  • std::sort 适合一般数组排序；只有在教学、特定分区需求或需要自定义行为时再手写快速排序。
  • 只需要前 K 个：根据目标考虑维护大小为 k 的堆；找最大的 K 个通常维护小根堆，找最小的 K 个通常维护大根堆。
  • 查询很多且更新少：AVL 可能合适。
  • 增删查综合平衡：红黑树类结构常见。
  • 磁盘页和范围查询：B/B+ 树类结构。
  • tuple 可用于临时返回多个值。

5. 总结

查找与排序算法没有脱离数据规模和分布的“唯一最优解”。选择时应比较时间复杂度、额外空间、稳定性、是否原地、数据是否近乎有序，以及键值范围能否支持计数或基数方法。

6. 参考资料

  • 严蔚敏、李冬梅、吴伟民：《数据结构（C 语言版·第 2 版）》。