TechnicalNote排序算法速查表：冒泡到基数排序7大算法，时间复杂度一图看懂
【免费下载链接】TechnicalNoteRepository to store what we have studied. :book: We want everyone to get a job through TechnicalNote.项目地址: https://gitcode.com/gh_mirrors/te/TechnicalNote
TechnicalNote 是一个开源技术笔记仓库，把笔试与真实面试中遇到的知识点系统整理成文。本文基于它的排序算法系列笔记，将冒泡排序、选择排序、插入排序、归并排序、快速排序、基数排序、计数排序这 7 大排序算法整理成一张速查表，并逐一讲清核心思想与时间复杂度——面试前 10 分钟过一遍，足够应付"各排序时间复杂度比较"这类高频提问 🎯
7大排序算法时间复杂度一览表
先上核心速查表，把最常被问到的平均时间复杂度、最坏时间复杂度、空间复杂度、稳定性一次对齐：
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 是否稳定 | 所属类别 |
|---|---|---|---|---|---|
| 冒泡排序 Bubble Sort | O(n²) | O(n²) | O(1) | ✅ 稳定 | 比较排序 |
| 选择排序 Selection Sort | O(n²) | O(n²) | O(1) | ❌ 不稳定 | 比较排序 |
| 插入排序 Insertion Sort | O(n²) | O(n²)（近乎有序时接近 O(n)） | O(1) | ✅ 稳定 | 比较排序 |
| 归并排序 Merge Sort | O(n log n) | O(n log n) | O(n) | ✅ 稳定 | 分治法 |
| 快速排序 Quick Sort | O(n log n) | O(n²)（已有序/逆序时） | O(log n) | ❌ 不稳定 | 分治法 |
| 计数排序 Counting Sort | O(n+k) | O(n+k)（k 为最大元素值） | O(n+k) | ✅ 稳定 | 非比较排序 |
| 基数排序 Radix Sort | O(d·n)（d 为最大数字位数） | O(d·n) | O(n+d) | ✅ 稳定 | 非比较排序 |
读表技巧：
- 📌O(n²) 三兄弟（冒泡、选择、插入）适合数据量小或近乎有序的场景，写起来最简单
- 📌O(n log n) 双子星（归并、快速）是大数据量的通用选择，快速排序因 CPU 缓存友好通常更快
- 📌非比较排序（计数、基数）突破了 O(n log n) 下界，但只适用于"取值范围有限"的整数场景
逐个拆解：7大排序算法核心思想
以下每个算法都对应 TechnicalNote 仓库中的一篇笔记（含 C++ / Java / Python 实现），文中以纯文本路径标出，便于对照阅读。
1. 冒泡排序：相邻比较，大的往后"冒泡"
- 思想：每轮比较相邻两个元素，顺序不对就交换，最大（或最小）元素像气泡一样逐渐"冒"到末尾，重复 n-1 轮
- 口诀：相邻比、反了换、每轮定一个终点
- 面试要点：O(n²) 来自两层嵌套循环；可加标志位优化，若某轮没有发生交换则提前结束
- 笔记路径：
algorithm/BubbleSort.md（含 C++、Java 实现）
2. 选择排序：每轮"点名"最小值
- 思想：第 i 轮从未排序部分找出最小值，与第 i 位交换；位置早已预定，只负责"选人"
- 特点：实现最简单、交换次数最少（至多 n 次），在可用内存受限时有一定优势；但不稳定
- 面试要点：无论数据是否有序，比较次数都是 O(n²)，没有任何"提前结束"的运气成分
- 笔记路径：
algorithm/SelectionSort.md
3. 插入排序：像打扑克牌一样"插牌"
- 思想：从第二个元素起，把当前元素往左找位置，一路插入到已排序序列中——从 1 个元素的小序列不断"长"成大序列
- 亮点：数据近乎有序时退化为 O(n)，小数据量下甚至比快速排序更快，因此常被用作快速排序的"收尾"
- 面试要点：是稳定的原地排序算法
- 笔记路径：
algorithm/InsertionSort.md
4. 归并排序：分而治之，合而有序
- 思想：先把数组不断二分直到只剩 1 个元素（1 个元素天然有序），再两两"归并"有序子序列，层层合并回长度为 n 的有序数组
- 特点：时间复杂度稳定在 O(n log n)，不随输入顺序波动；代价是需要 O(n) 额外空间
- 面试要点：典型的分治法（Divide and Conquer）案例，稳定排序
- 笔记路径：
algorithm/MergeSort.md（含 C++、Java、Python、JavaScript 四种实现）
5. 快速排序：选个"哨兵"快速分区
- 思想：选一个 pivot（基准），把比它小的放左边、比它大的放右边，再对两个子区间递归执行
- 复杂度：平均 O(n log n)，最坏 O(n²)——当数组已经有序或逆序、pivot 恰好选到极值时触发
- 三大改进（面试加分项）：
- 随机选 pivot，用概率抹平最坏情况
- 小区间（如 100~200 以下）切换插入排序，降低递归深度
- 三数取中法选 pivot，保证正序/逆序时也能接近中点分割
- 笔记路径：
algorithm/QuickSort.md
6. 基数排序：不看大小，逐位"分桶"
- 思想：从个位开始，把每个数字按当前位投入 0~9 号桶，倒出来再按十位、百位重复，直到最高位——全程不做元素间比较
- 特点：稳定排序，整数排序性能极高；但只支持整数（实数不行），且需要额外桶空间
- 面试要点：时间复杂度 O(d·n)，d 是最长位数；d 很小时可优于 O(n log n)
- 笔记路径：
algorithm/RadixSort.md（含 C++、Java、Python、JavaScript 实现）
7. 计数排序：数一数每个值出现几次
- 思想：不比较，只统计每个值出现了几次，求前缀和后一次性按序回填
- 适用：取值范围有限的数据（如成绩、年龄段、字母频次），k 较小时速度接近线性
- 面试要点：稳定排序，属于Non-Comparison Sort（非比较排序）
- 笔记路径：
algorithm/CountingSort.md
面试实战：3个高频问题这样答
TechnicalNote 的 实际面试题汇总 中，"数据结构、算法"一栏就收录了真实考过的：
- 各排序的时间复杂度比较
- 快速排序的时间复杂度、为什么是这个复杂度、以及改进方法
- 容器排序算法手撕代码
答题模板：
- 先分类：比较排序（O(n log n) 下界）vs 非比较排序（计数、基数）
- 报数字：说出该算法的平均/最坏时间复杂度与稳定性
- 给场景：例如"小数据量或近乎有序用插入排序；通用场景用快速排序；要求稳定且内存充足用归并排序；整数且值域有限用计数/基数排序"
能按这个结构 30 秒内答完，基本就能拿到这道题的满分。
复习路径建议：1天吃透排序算法
- 第 1 小时——对照上面的速查表，把 7 个算法的复杂度与稳定性背下来
- 第 2~4 小时——按
algorithm/目录下的 7 篇笔记逐个读，重点看"实现步骤"部分（每篇都给出 C++ / Java 等多语言代码） - 第 5~6 小时——默写冒泡、插入、快速排序三件套；再默写一次速查表，检验记忆
仓库里还有拓扑排序、Kruskal 最小生成树、坐标压缩等算法笔记，可与 README 目录 搭配，作为算法复习的整体索引 📚
获取完整笔记
若需阅读全部源码级笔记，可将仓库克隆到本地：
git clone https://gitcode.com/gh_mirrors/te/TechnicalNote【免费下载链接】TechnicalNoteRepository to store what we have studied. :book: We want everyone to get a job through TechnicalNote.项目地址: https://gitcode.com/gh_mirrors/te/TechnicalNote
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
