排序算法技术文档

本文系统整理了常见排序算法的核心思想、实现方式、复杂度分析、稳定性与适用场景，适用于算法学习、面试准备以及教学场景。

目录

• 一、插入排序（Insertion Sort）
• 二、希尔排序（Shell Sort）
• 三、归并排序（Merge Sort）
• 四、快速排序（Quick Sort）
• 五、堆排序（Heap Sort）
• 六、排序算法对比总结

---

一、插入排序（Insertion Sort）

1. 基本思想

• 将数组划分为两个逻辑区域：
  • 已排序区
  • 未排序区
• 默认第一个元素在已排序区
• 每次从未排序区取出一个元素
• 从已排序区从后向前比较
• 找到合适位置插入

2. 核心特征

• 类似“打扑克牌插牌”
• 数据基本有序时效率极高
• 属于稳定排序
• 原地排序（不需要额外数组）

3. 时间 & 空间复杂度

情况	复杂度
最好情况（已排序）	O(n)
平均情况	O(n²)
最坏情况（逆序）	O(n²)
空间复杂度	O(1)
稳定性	稳定

4. 适用场景

• 数据量较小
• 数据基本有序
• 作为其他排序（如希尔排序）的基础

---

二、希尔排序（Shell Sort）

1. 基本思想

希尔排序是 插入排序的升级版

• 引入 步长（gap）
• 将原数组按步长拆分为多个子序列
• 对每个子序列执行插入排序
• 步长逐渐缩小，最终为 1

---

2. 排序流程

1. 初始步长：gap = n / 2
2. 对 gap 个子序列分别做插入排序
3. gap /= 2
4. 重复直到 gap = 1

3. 时间 & 空间复杂度

时间复杂度依赖步长序列
| 项目 | 说明 |
| ----- | --------------- |
| 最坏情况 | O(n²) |
| 平均情况 | 介于 O(n) ~ O(n²) |
| 实际表现 | 明显优于插入排序 |
| 空间复杂度 | O(1) |
| 稳定性 | 不稳定 |

4. 适用场景

• 中等规模数据
• 内存受限环境
• 插入排序性能不足时的改进方案

---

三、归并排序（Merge Sort）

1. 基本思想

分治思想 + 递归

• 不断将数组二分
• 直到子数组长度为 1
• 逐层向上合并
• 合并过程保证有序

2. 核心流程

1. 递归拆分数组
2. 左右子数组分别排序
3. 合并两个有序数组

3. 时间 & 空间复杂度

项目	复杂度
最好 / 平均 / 最坏	O(n log n)
空间复杂度	O(n)
稳定性	稳定

4. 特点与应用

• 性能稳定

• 适合处理大数据量

• 常用于：

  • 外部排序
  • 链表排序

• 缺点：额外内存消耗

---

四、快速排序（Quick Sort）

1. 基本思想

• 选择一个 基准值（pivot）
• 小于基准的放左边
• 大于基准的放右边
• 递归处理左右区间

2. 关键步骤

1. 选择基准
2. 左右指针向中间移动
3. 交换不符合条件的元素
4. 基准归位
5. 递归左右区间

3. 时间 & 空间复杂度

情况	复杂度
平均情况	O(n log n)
最坏情况	O(n²)
空间复杂度	O(log n)（递归栈）
稳定性	不稳定

4. 工程实践说明

• 实际项目中常用

• 通常会：

  • 随机选基准
  • 三数取中

• 避免退化为 O(n²)

---

五、堆排序（Heap Sort）

1. 基本思想

• 利用 完全二叉树
• 构建 大顶堆
• 堆顶元素与末尾交换
• 调整堆结构
• 重复直到有序

2. 核心规则

• 父节点 i
• 左子节点 2i + 1
• 右子节点 2i + 2
• 最大非叶子节点：n / 2 - 1

3. 时间 & 空间复杂度

项目	复杂度
最好 / 平均 / 最坏	O(n log n)
空间复杂度	O(1)
稳定性	不稳定

4. 特点

• 原地排序
• 性能稳定
• 不依赖递归
• 常用于对空间要求严格的系统

---

六、排序算法对比总结

算法	时间复杂度	空间复杂度	稳定性	特点
插入排序	O(n²)	O(1)	稳定	小数据、基本有序
希尔排序	~O(n²)	O(1)	不稳定	插入排序优化
归并排序	O(n log n)	O(n)	稳定	大数据、性能稳定
快速排序	平均 O(n log n)	O(log n)	不稳定	实际最快
堆排序	O(n log n)	O(1)	不稳定	空间友好

---