非常好，《数据结构初阶》系列中“八大排序——巅峰决战”可以做成一章极具冲击力的知识点合集。下面是本章节的详细内容结构，适合写成讲义、教学 PPT 或视频脚本，涵盖 八种经典排序算法 的原理、实现、复杂度比较与适用场景。
《数据结构初阶》
八大排序——巅峰决战 🥇
🧭 目录
- 冒泡排序（Bubble Sort）
- 选择排序（Selection Sort）
- 插入排序（Insertion Sort）
- 希尔排序（Shell Sort）
- 归并排序（Merge Sort）
- 快速排序（Quick Sort）
- 堆排序（Heap Sort）
- 计数排序（Counting Sort）
- 巅峰对比分析表
- 排序算法选择指南
1️⃣ 冒泡排序（Bubble Sort）
- 核心思想：两两比较，较大（或较小）元素逐步“冒泡”到末尾
- 时间复杂度：最坏 O(n²)，最好 O(n)（已排序 + 优化）
- 空间复杂度：O(1)
- 稳定性：稳定
- 适用场景：数据量小、基本有序时简单高效
def bubble_sort(arr):
n = len(arr)
for i in range(n):
flag = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
flag = True
if not flag:
break
2️⃣ 选择排序（Selection Sort）
- 核心思想：每轮从未排序区间选出最小元素放到前面
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 适用场景：交换次数较少要求的场合
3️⃣ 插入排序（Insertion Sort）
- 核心思想：将每个元素插入到前面已排序子数组的合适位置
- 时间复杂度：O(n²)，最好 O(n)
- 空间复杂度：O(1)
- 稳定性：稳定
- 适用场景：数据量小或局部有序
4️⃣ 希尔排序（Shell Sort）
- 核心思想：将数组按间隔分组，对每组进行插入排序，逐步缩小间距
- 时间复杂度：平均约 O(n^1.3)，最坏 O(n²)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 适用场景：插入排序的优化版本，适用于中等规模数据
5️⃣ 归并排序（Merge Sort）
- 核心思想：分而治之，递归拆分 + 合并有序子序列
- 时间复杂度：O(n log n)
- 空间复杂度：O(n)
- 稳定性：稳定
- 适用场景：大数据量、要求稳定排序时的首选
6️⃣ 快速排序（Quick Sort）
- 核心思想：分区法，选一个“基准”，左边比它小，右边比它大，递归处理
- 时间复杂度：平均 O(n log n)，最坏 O(n²)
- 空间复杂度：O(log n)（递归栈）
- 稳定性：不稳定
- 适用场景：最常用，适合大多数实际场景，效率极高
7️⃣ 堆排序（Heap Sort）
- 核心思想：构造最大堆，每次取堆顶元素（最大值）放到末尾
- 时间复杂度：O(n log n)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 适用场景：不要求稳定排序但内存敏感时适合使用
8️⃣ 计数排序（Counting Sort）
- 核心思想：统计每个元素出现次数，通过“桶”来计数排序
- 时间复杂度：O(n + k)，k为数值范围
- 空间复杂度：O(k)
- 稳定性：稳定
- 适用场景：数据范围小，且是整数
9️⃣ 巅峰对比分析表 🔥
| 排序算法 | 时间复杂度（最坏） | 时间复杂度（平均） | 空间复杂度 | 稳定性 | 是否原地 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | ✅ | ✅ |
| 选择排序 | O(n²) | O(n²) | O(1) | ❌ | ✅ |
| 插入排序 | O(n²) | O(n²) | O(1) | ✅ | ✅ |
| 希尔排序 | O(n²) | O(n^1.3) | O(1) | ❌ | ✅ |
| 归并排序 | O(n log n) | O(n log n) | O(n) | ✅ | ❌ |
| 快速排序 | O(n²) | O(n log n) | O(log n) | ❌ | ✅ |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ❌ | ✅ |
| 计数排序 | O(n + k) | O(n + k) | O(k) | ✅ | ❌ |
🔟 排序算法选择指南 🧠
| 场景/需求 | 推荐算法 |
|---|---|
| 数据量小 | 插入排序、冒泡排序 |
| 数据基本有序 | 插入排序 |
| 要求稳定性 | 归并排序、计数排序 |
| 数据量大、效率优先 | 快速排序 |
| 内存限制、稳定性无要求 | 堆排序 |
| 元素范围窄为整数 | 计数排序 |
📌 总结一句话：
“没有最强的排序，只有最适合的排序！”
发表回复