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/TechnicalNoteTechnicalNote 是一个开源技术笔记仓库把笔试与真实面试中遇到的知识点系统整理成文。本文基于它的排序算法系列笔记将冒泡排序、选择排序、插入排序、归并排序、快速排序、基数排序、计数排序这 7 大排序算法整理成一张速查表并逐一讲清核心思想与时间复杂度——面试前 10 分钟过一遍足够应付各排序时间复杂度比较这类高频提问 7大排序算法时间复杂度一览表先上核心速查表把最常被问到的平均时间复杂度、最坏时间复杂度、空间复杂度、稳定性一次对齐排序算法平均时间复杂度最坏时间复杂度空间复杂度是否稳定所属类别冒泡排序 Bubble SortO(n²)O(n²)O(1)✅ 稳定比较排序选择排序 Selection SortO(n²)O(n²)O(1)❌ 不稳定比较排序插入排序 Insertion SortO(n²)O(n²)近乎有序时接近 O(n)O(1)✅ 稳定比较排序归并排序 Merge SortO(n log n)O(n log n)O(n)✅ 稳定分治法快速排序 Quick SortO(n log n)O(n²)已有序/逆序时O(log n)❌ 不稳定分治法计数排序 Counting SortO(nk)O(nk)k 为最大元素值O(nk)✅ 稳定非比较排序基数排序 Radix SortO(d·n)d 为最大数字位数O(d·n)O(nd)✅ 稳定非比较排序读表技巧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.md3. 插入排序像打扑克牌一样插牌思想从第二个元素起把当前元素往左找位置一路插入到已排序序列中——从 1 个元素的小序列不断长成大序列亮点数据近乎有序时退化为 O(n)小数据量下甚至比快速排序更快因此常被用作快速排序的收尾面试要点是稳定的原地排序算法笔记路径algorithm/InsertionSort.md4. 归并排序分而治之合而有序思想先把数组不断二分直到只剩 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.md6. 基数排序不看大小逐位分桶思想从个位开始把每个数字按当前位投入 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），仅供参考