数据结构-排序

排序分类

稳定性分类

若序列中关键字值相等的节点经过某种排序方法进行排序之后，仍能保持它们在排序前的相对顺序，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。

• 稳定排序算法：
  • 插入排序
  • 冒泡排序
  • 归并排序
• 不稳定排序算法：
  • 选择排序
  • 希尔排序
  • 快速排序
  • 堆排序

内存使用情况分类

• 内部排序：数据存储和位置调整均在内存中进行
• 外部排序：大部分数据元素存储在外存，借助内存进行位置调整

据排序实现手段分类

• 基于“比较-交换”的排序：通过对关键字的比较，交换关键字在序列中的位置 l 插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序、堆排序
• 基于“分配”的排序：通过将元素进行分配和收集进行排序 l 桶排序、计数排序和基数排序

难易程度分类

• 基本排序：插入排序、冒泡排序、选择排序、……
• 高级排序：快速排序、归并排序、堆排序、基数排序、……

经典排序

插入排序

基本思想：将一个记录插入到已经排好序的序列中，形成一个新的、记录数增1的有序序列 。

我们一般使用直接插入排序。将A[i]插入有序序列，让前面所有的元素比它大/小，从而得到新有序序列。

时间复杂度：平均为O(n^2) 空间复杂度： O(1)

折半插入排序

二分法进入排序,即为折半插入排序,查找位置时间复杂度为O(logn),但是元素挪动依然为O(n),所以整体的时间复杂度为O(n^2)

希尔排序

基本原理：先对所有记录按增量(d)进行分组，组内进行插入排序；然后减少增量重复上述步骤，直至增量为1 。 画线可以连接在一起的视为一个组，比如示例，57，48，66为一个组，进行比较的时候57与48交换，交换后也要考虑57和66是否可以互相交换。

时间复杂度：依赖于增量序列，没有确切结论，可以优于 O(n2)，例如某些情况下可达到 O(nlog2n) 或 O(n^3/2) 。

• 选一个初始 gap，比如 n/2
• 按 gap 把数组分成若干组
• 对每组做插入排序
• 缩小 gap，比如 gap /= 2
• 重复直到 gap = 1（就是普通插排）

---

简单选择排序

基本思想：首先选出最小的项，与第一个项交换；然后在剩余项中选出次小的项，与第二个项交换；以此类推，直到整个序列有序 。

• 过程：每次在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置 。  
• 性能：
  • 时间复杂度：O(n^2) (最佳、最坏、平均情况均为 O(n^2) 次比较) 。  
  • 空间复杂度：O(1) 。

堆排序

基本思想：将待排序序列构造成一个大顶堆（或小顶堆），此时堆顶元素即为最大（或最小）值。将其与末尾元素交换，然后将剩余n-1个元素重新调整为堆，重复此过程 。

过程：包括建堆和调整堆两个主要步骤 。 先看建立堆过程吧。

性能：

• 时间复杂度：O(nlogn) 。  
• 空间复杂度：O(1) 。

交换排序

核心思路：对序列中的元素进行多次两两交换，从而使序列元素有序 。

冒泡排序

基本思想：依次比较相邻两个元素，如果反序则交换，重复操作直到整个序列有序。每趟排序会将当前未排序部分的最大（或最小）元素”冒泡”到最终位置 。

性能：

• 时间复杂度：O(n2) 。  
• 空间复杂度：O(1)。

快速排序

基本思想：通过递归分治方法，基于轴点 (pivot) 将待排序序列拆分成两个子序列（左边元素均小于等于轴点，右边元素均大于等于轴点），然后对两个子序列分别递归排序 。

• 选定轴点：通常是当前子序列最后一个元素（也可以是别的，但这是经典选择）。

• 分区过程：

  • 使用左右指针（或一个指针i）遍历序列。
  • 保证所有小于轴点的元素在左边，大于等于轴点的在右边。
  • 划定边界：找出最终轴点应该插入的位置，把它交换过去。

• 递归处理：

  • 以轴点为界，继续分别对左子序列和右子序列进行快速排序。

• 终止条件：

  • 子序列长度为 0 或 1，说明那一段已经有序，无需继续处理。

快排比较复杂，这里给一个拆分示例，轴点寻找和插入位置寻找不看图不行。（这里使用的是左右双指针法）：

👇 初始数组：

[10, 20, 15, 4, 1, 9, 6]

我们使用最简单直观的 Lomuto 分区法（用最后一个元素当轴点）。每一次递归我们都分区 + 继续快排子数组。

---

✅ 第一次快排（全数组） 数组：[10, 20, 15, 4, 1, 9, 6]
pivot（轴点）= 6
i = -1

遍历 j=0 到 j=5：

• 10 > 6 → 跳过
• 20 > 6 → 跳过
• 15 > 6 → 跳过
• 4 < 6 → i=0, 交换 arr[0] ↔ arr[3] → [4, 20, 15, 10, 1, 9, 6]
• 1 < 6 → i=1, 交换 arr[1] ↔ arr[4] → [4, 1, 15, 10, 20, 9, 6]
• 9 > 6 → 跳过

结束后，i = 1，交换 arr[2] ↔ pivot (arr[6])
→ 最终：[4, 1, 6, 10, 20, 9, 15]

现在 6 已经在正确的位置了！

---

🎯 快排左边 [4, 1] pivot = 1
i = -1

• 4 > 1 → 跳过 结束后 i = -1，交换 arr[0] ↔ arr[1]
  → [1, 4]，完成了！

---

🎯 快排右边 [10, 20, 9, 15] pivot = 15
i = 2（6 已经在前面了） 从 j=3 开始：

• 10 < 15 → i=3, 交换 arr[3] ↔ arr[3]（自交换）
• 20 > 15 → 跳过
• 9 < 15 → i=4, 交换 arr[4] ↔ arr[5]
  → [1, 4, 6, 10, 9, 20, 15] 交换 pivot arr[6]和arr[5]→[1, 4, 6, 10, 9, 15, 20]`

---

🎯 快排 [10, 9] pivot = 9

• 10 > 9 → 跳过 交换 arr[3] ↔ arr[4]
  → [1, 4, 6, 9, 10, 15, 20]

---

✅ 最终结果：

[1, 4, 6, 9, 10, 15, 20]

---

性能：

• 时间复杂度：平均 O(nlogn)，最坏 O(n2) (当序列已基本有序或轴点选择不佳时) 。  
• 空间复杂度 (递归栈深度)：平均 O(logn)，最坏 O(n) 。

归并排序

• 核心思路：基于分治思想，将两个或两个以上的有序序列合并为一个新的有序序列 。  

• 归并次序 ：  

  • 自顶向下：将序列递归拆分到单个元素，然后两两合并。

  • 自底向上：将序列看作n个长度为1的有序子序列，然后两两合并，直到合并为一个序列。

• 二路归并 (Two-Way Merge)：将两个有序序列合并为一个新的有序序列，时间复杂度为 O(m+n)，其中m和n为两个序列的长度 。  

• 性能：

  • 时间复杂度：O(nlogn) (自顶向下和自底向上均为) 。  
  • 空间复杂度：O(n) (需要额外的辅助空间) 。  

• 应用：求逆序对数量 。

分配排序

不基于“比较-移动”的排序方式。

计数排序

• • 假设：输入元素是 0 到 k 之间的一个整数 。  
    • 基本思想：统计每个元素出现的次数，然后根据计数确定每个元素在输出数组中的位置 。  
    • 性能：
      • 时间复杂度：O(n+k)，当 k 为 O(n) 时，复杂度为 O(n) 。  
      • 空间复杂度：O(n+k) 。  

桶排序

• • 基本思想：将元素分配到有限数量的桶中，然后对每个桶内的元素进行排序（通常用插入排序），最后依次连接各桶中的元素得到有序序列 。
    • 与计数排序关系：计数排序可以看作是桶排序的一种特殊情况，其中每个桶只包含相同值的元素 。  
    • 性能：
      • 时间复杂度：平均 O(n+kn2​+k) (假设均匀分配到k个桶)，如果元素能均匀分配，可以达到 O(n) 。最坏 O(n2) 。  
      • 空间复杂度：O(n+k) 。  

基数排序

• 核心思路：将待排序元素看作基于基数（如十进制的10）的元组表示，然后从最低位（LSD）或最高位（MSD）开始，对每一位进行排序（通常使用计数排序作为子排序算法） 。  

• 分类：

  • 最低位优先 (LSD) 基数排序 ：从最低位到最高位，逐位进行稳定排序。  
  • 最高位优先 (MSD) 基数排序 ：从最高位开始，递归地对子序列进行排序。  

• 性能 (设n个元素，每个元素有d位，基数为k)：

  • LSD时间复杂度：O(d(n+k)) 。  
  • MSD时间复杂度：最坏 O(d⋅n⋅k)，平均也类似 。  
  • 空间复杂度：O(n+k) 。  

索引排序

• 核心思路：创建一个索引序列，排序时不直接移动原序列中的元素，而是移动索引。排序完成后，索引序列指明了原序列元素应有的顺序。这在元素移动和拷贝代价很大时非常有用 。  
• 元素顺序调整：得到排序后的索引序列后，可以根据索引将原序列元素调整到正确位置。

---

数据结构-查找

基本查找算法

顺序查找

一个一个查，O(n)

二分查找

中位 middle=(low+high)/2 low 和 high 要随时改成 middle+1 (去右边找)或者 middle-1 （去左边找） 时间复杂度 O(logn)

---

索引查找（分块查找）

• 创建存储数据的表，再根据要求建立相应索引 （如创建字典目录，有点像 unordered_map 建立映射）
• 索引查找需要牺牲空间，从而降低时间复杂度

如何构建索引？

• 表中数据分块，使得内部分块的关键字值都大于或小于下一个块。称为“分块有序”。
• 为每块建立一个索引项，包含 key 和 index 。即关键码字段和指针字段。
• 通过key 找到关键字值的记录块，然后在块内进行 顺序查找或者二分查找

其实时间复杂度也是线性，但是依赖于块数据的大小与块内查找方式。

• O(s)与O(logs)的查找时间，还得看分块的大小。

---

二叉查找树 （BST）

基本定义

二叉查找树或者是一棵空树； 或者是具有如下特性的二叉树：

• 若根结点的左子树不空，则左子树上所有结点的值均小于根结点的值；
• 若根结点的右子树不空，则右子树上所有结点的值均大于根结点的值； 性质：任何二叉查找树的中序遍历都是有序序列 且一般规律是: 任意左子树的值 < 根节点的值 < 对应右子树的值。

查找

如果要在二叉查找树寻找关键值 key ,基本原理和二分查找相同。如果给定值比当前节点小则去当前节点的左子树继续寻找，大则去右子树继续寻找。

时间复杂度为 O(h),h为树的高度。基本也就是进行递归调用。

对于其时间复杂度，性能最差可能会退化到线性查找。

二叉树插入算法

注意：插入位置是节点从根节点比较一步一步确定的，小于该节点移到左侧与左节点比较，反之同理，不是随便写的。 也是利用查找，确定好要进入的树节点，从而插入值。 “插入”操作在查找不成功时才进行。如果树中存在该值，BST 不允许有重复值。

二叉查找树的建立

将根节点设置为一个空集（变成可以设定为一个无限小），然后往下查找往下画即可。

二叉查找树的删除

删除可分三种情况讨论： （1）被删除的结点是叶子 ，不用管孩子，很简单

（2）被删除的结点只有左子树或者只有右子树 ，像链表一样需要删除节点的操作

（3）被删除的结点既有左子树，也有右子树。这个比较复杂，与堆的那个操作不太一样。 相当于在序列里将其往前移动一格，拼起来。

平衡二叉树（AVL树）

基本定义

AVL树或者是一棵空树，或者是具有下列性质的二叉查找树：

• 左、右子树都是平衡二叉树；
• 左、右子树的高度差绝对值不超过1。（这里的高度差左子树高度-右子树高度）

构造AVL树

看个例子。所谓平衡旋转，左旋和右旋，就是：

右旋 = 左子过重时，把左儿子提上来当新根，把原根放到右边；左儿子的右子（如果有）会变成原根的左子。

左旋 = 右子过重时，把右儿子提上来当新根，把原根放到左边；右儿子的左子（如果有）会变成原根的右子。

将BST转化为AVL

平衡化旋转

失衡调整旋转平衡处理

• 第一个字母代表：失衡节点是哪个子树高了（L = 左子树，R = 右子树）

• 第二个字母代表：哪边插入导致了这个子树变高（L = 左边插入，R = 右边插入） 图例

• 单调右旋 （LL）

• 单调左旋（RR）

• 先左后右旋 （LR）

• 先右后左旋转（RL）

插入

AVL树的新结点的插入过程包括两个步骤：

• 结点插入： 按照BST构建方法插入，同时更新平衡因子
• 平衡化：如果插入过程中出现不平衡，采用平衡化调整，以保持AVL的性质

插入有一个递归算法，太长了…

删除

---

散列查找 | 哈希查找

建立映射，unordered_map的伟大无需多言。 散列查找需要建立某种哈希函数，通过某种数学方法将数据转化为哈希地址，建立一个哈希表，映射建立。 由于哈希函数是一个压缩映射，因此在一般情况下容易产生冲突，避免冲突，要么就哈希地址更复杂，要么就哈希函数更复杂。

很难找到一个不产生冲突的散列函数。一般情况下，只能选择恰当的散列函数，使冲突尽可能少地产生。

散列函数 | 哈希函数

一般来说，一个好的散列函数应满足下列两个条件：

• 计算简单
• 冲突少

常见的哈希函数构造方法有：

• 直接地址存储法
• 数字分析法
• 平方取中法
• 折叠法
• 除留余数法
• 随机数法

直接地址存储法

数字分析法

平方取中法

平方取中法思想：以关键字的平方值的中间几位作为存储地址。 关键字的各位都在平方值的中间几位有所贡献，Hash 值中应该有各位影子。

折叠法

除留余数法

随机数法

注意随机一定要真随机，设置好 seed 随机种子。

散列表的绘制之后补充。

红黑树

红黑树的五条核心规则

1. 每个节点要么是红色，要么是黑色。
2. 根节点永远是黑色。
3. 所有叶子节点（NIL/空节点）都是黑色的。
4. 红色节点的子节点必须是黑色的。（即不能有两个连续的红色节点）
5. 从任一节点到其所有后代叶子节点的路径上，黑色节点的数量都相同。

插入策略：新插入的节点总是红色的。然后通过“变色”和“旋转”来修复可能违反的规则。

修复违规的“小抄”

当你插入一个红色新节点 N，发现它的父节点 P 也是红色时（违反了规则4），你只需要看它叔叔节点 U 的颜色：

• 情况1：叔叔 U 是红色
  • 操作：变色。将父节点 P 和叔叔 U 变为黑色，将祖父节点 G 变为红色。然后将祖父节点 G 当作新的插入点，继续向上检查。
• 情况2：叔叔 U 是黑色（或NIL/空节点）
  • 操作：旋转+变色。这又分为两种：
    • 直线型 (LL / RR)：直接对祖父节点 G 进行旋转，然后将 P 和 G 变色。
    • 三角型 (LR / RL)：先对父节点 P 进行旋转，变成直线型，然后再按直线型处理。