尧图网站开发 
排序算法大概是数据结构课程里最让人又爱又恨的一块。爱的是思路直观冒泡、插入、选择基本看一遍就能懂恨的是细节太多边界条件、稳定性、复杂度推导一不留神就翻车。我在学习和教学中反复写过七八遍这八大排序算法也做过不少数据规模下的实测对比。这篇文章就把我自己的理解和踩坑记录整理出来覆盖冒泡、选择、插入、希尔、快速、归并、堆、基数这八种经典排序从原理到代码再到复杂度、稳定性、实战选型一次讲透。如果你正在复习数据结构期末、备战考研408或者想把手写排序的水平提上去这篇应该能直接帮你省下大把时间。真正吃透排序算法不能只背代码。你要清楚每个算法在干什么、为什么这么做、数据特征变了之后会发生什么。后面我会先讲几个必须掌握的基础概念再逐个拆算法最后用实测数据和常见坑位收尾。整个逻辑是按照我自己的学习路径来的尽量让零基础也能顺着走下来。1. 排序算法的基础复杂度、稳定性与场景选型1.1 时间复杂度和空间复杂度怎么看复杂度不是用来背的是用来聊天的。两个算法放在一起你首先要能说出它们在不同数据规模、不同数据分布下的表现。我把复杂度拆成最好、平均、最坏三档因为排序算法很吃初始数据。一个已经有序的数组冒泡排序和插入排序能做到 O(n)但选择排序还是老老实实跑 O(n^2)快速排序在已经有序的数组上反而可能退化成 O(n^2)。这就说明只看平均复杂度定生死太粗糙。空间复杂度关注的是额外开辟的内存不包括原数组本身。原地排序in-place的空间复杂度是 O(1)比如冒泡、选择、插入、希尔、堆排序但归并排序需要额外 O(n) 的辅助数组快速排序虽然不需要额外数组但递归调用栈平均要 O(log n) 的空间。基数排序也得额外开桶空间通常是 O(nk)。如果环境内存吃紧这些差距都很关键。提示判断一个排序算法是否“原地”标准是额外空间是否为 O(1)。快排尽管需要递归栈通常仍被算作原地排序的变体但不能简单当成零空间开销。1.2 稳定性为什么重要稳定性指的是值相等的两个元素排序后相对顺序不改变。比如学生成绩按分数排同分的同学还希望按学号顺序排列。解决办法是先按学号排一次再按分数排一次前提是第二次排序必须是稳定的。不稳定的排序算法会在这次“二次排序”里把第一次的结果打乱。所以实际开发中如果数据带有多个字段排序需求稳定性往往是硬指标。归并排序、插入排序、冒泡排序、基数排序稳定选择排序、快速排序、堆排序、希尔排序不稳定。这个结论建议直接记住面试和笔试都很爱考。1.3 排序场景选型思路没有万能排序。数据量小、基本有序插入排序可能比快排还快数据量大、要求稳定归并排序更稳妥在意内存占用堆排序和希尔排序是候选区排序对象是整数且位数有限基数排序可以跑到线性复杂度。真实工程里的排序函数比如 C 的 std::sort或 Python 的 TimSort本质上都是混合策略小数据用插入排序大数据用快排/归并同时检测数据是否接近有序。理解了这层思路你再看源码会豁然开朗。2. 八大经典排序算法逐一拆解下面每个算法我都会按“算法思路、代码实现、复杂度与稳定性、适用场景”来讲。代码用 C 语言风格写注释尽量详细方便直接跑实验。2.1 冒泡排序最直观的交换排序冒泡排序的基本思想是相邻两个元素两两比较如果顺序错误就交换。每一趟排序后当前未排序部分的最大值会像气泡一样“浮”到末尾。总共需要 n-1 趟每趟的比较次数逐次减少。void bubbleSort(int a[], int n) { for (int i 0; i n - 1; i) { bool swapped false; // 本趟是否发生过交换 for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int tmp a[j]; a[j] a[j 1]; a[j 1] tmp; swapped true; } } if (!swapped) break; // 整趟无交换说明已经有序 } }这个swapped标志就是最常见的优化。不加它哪怕数组已经排好序算法还是会傻乎乎地跑完所有趟加了它最好情况时间复杂度降到 O(n)。稳定性上冒泡是稳定排序因为只有前一个元素严格大于后一个元素才交换相等的元素不会互换位置。适用场景比较局限教学演示和极少量数据时用用即可。我实测过 n10000 的随机数组冒泡排序耗时大约是插入排序的十几倍基本属于“能跑但别指望性能”的排序。不过它的优点也很突出实现简单、不易写错、稳定适合作为手写排序的“保底方案”。2.2 选择排序最朴素的极值筛选选择排序的思路比冒泡更直接每一趟从待排序区间中选出最小值放到区间最前面。外层循环控制位置内层循环找最小值找到后交换。void selectionSort(int a[], int n) { for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) minIdx j; } if (minIdx ! i) { int tmp a[i]; a[i] a[minIdx]; a[minIdx] tmp; } } }选择排序无论数据是否有序比较次数都是固定的 n(n-1)/2所以最好、平均、最坏时间复杂度全是 O(n^2)。额外空间是 O(1)。它唯一的优势可能是“交换次数少”每趟最多一次交换总共最多 n-1 次。但是不稳定这一点经常被忽略。怎么理解不稳定举个例子数组[5, 5, 2]第一趟时 minIdx 会指向值为 2 的第三个元素然后与第一个位置的 5 交换结果是[2, 5, 5]。虽然两个 5 值相等但原本靠前的那个 5 被换到了后面相对顺序变化了。如果你需要稳定性选择排序直接出局。实战中它也很少被用到多作为教学入门案例因为思路太简单反而容易给后面学堆排序做铺垫——堆排序本质上就是“用堆快速选出最大值”的选择排序。2.3 插入排序扑克牌式整理插入排序的思路就像打扑克时理牌左手已经拿着的牌是有序的新摸到一张牌从右往左找到合适位置插进去。算法从第二个元素开始把每个元素插入到前面已经有序的子序列里。void insertionSort(int a[], int n) { for (int i 1; i n; i) { int key a[i]; int j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; // 比 key 大的元素往后移 j--; } a[j 1] key; // key 落位 } }插入排序最好情况下是 O(n)也就是数组本身已经有序时每个元素只要比较一次就能落位。平均和最坏都是 O(n^2)空间 O(1)而且稳定。它对“基本有序”的数据非常友好这也是为什么很多高级排序算法在递归深度较小时会切换成插入排序。我有一个很实用的经验当数据量小于 50 时插入排序通常比快排还快。原因在于快排有递归调用和 partition 的额外开销而插入排序的系数极小。实际工程里的混合排序比如 C 的 std::sort 会在小规模区间调用插入排序正是基于这个观察。2.4 希尔排序插入排序的进阶版希尔排序也叫“缩小增量排序”。它先把数组按某个增量 gap 分成若干组每组内做插入排序然后逐步缩小 gap 重复操作最后当 gap1 时相当于做一次标准的插入排序。这样做的好处是前期的大间隔让元素能够快速跨越较远距离整体的逆序程度大幅下降。void shellSort(int a[], int n) { for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key a[i]; int j i - gap; while (j 0 a[j] key) { a[j gap] a[j]; j - gap; } a[j gap] key; } } }复杂度取决于增量序列。上面代码用的是最常规的希尔增量每次减半最坏复杂度是 O(n^2)如果用 Hibbard 增量1, 3, 7, 15...最坏能到 O(n^{3/2})。空间 O(1)。希尔排序是不稳定的因为分组插入排序时相等元素可能被分到不同组它们的相对位置无法保证。实际使用场景是数据量中等、内存敏感、不需要稳定排序时希尔排序是很均衡的选择。它比插入排序快很多又比快排/归并简单不需要额外空间。我见过不少嵌入式项目里的排序就用的希尔排序原因就是代码量少、空间省、不容易出 bug。2.5 快速排序分治思想的代表快速排序是应用最广的排序算法之一。思路是选一个基准值pivot把数组分成左右两部分左边都小于等于基准右边都大于等于基准。然后递归排序左右子区间。关键在于 partition分区这一步它决定了快排的性能和稳定性。int partition(int a[], int low, int high) { int pivot a[low]; // 以第一个元素为基准 while (low high) { while (low high a[high] pivot) high--; a[low] a[high]; while (low high a[low] pivot) low; a[high] a[low]; } a[low] pivot; return low; } void quickSort(int a[], int low, int high) { if (low high) { int pivotIdx partition(a, low, high); quickSort(a, low, pivotIdx - 1); quickSort(a, pivotIdx 1, high); } }快排的平均时间复杂度是 O(n log n)最好也是 O(n log n)最坏是 O(n^2)。最坏情况发生在每次 partition 极度不平衡时例如数组已经有序且每次都取第一个元素作为基准那划分后左右两边长度一边是 0、一边是 n-1递归深度到了 n复杂度退化成 O(n^2)。这也是为什么工程实现里不能简单取第一个元素当基准。优化手段我后面会专门讲这里先记住三个关键词随机基准、三数取中、小区间切换插入排序。稳定性方面快排是不稳定的这个我也不止一次在面试里被问到答案要干脆。适用场景是通用排序的首选只要不要求稳定、递归不会爆栈快排在绝大多数情况下表现都很好。我实测 10 万个随机整数快排通常能在 20 毫秒内排完而归并排序大概要 30 多毫秒这还不算归并额外分配内存的开销。2.6 归并排序稳定排序的标杆归并排序也是分治思想但它不做原地交换而是把数组不断对半拆分直到每个子数组只有一个元素再两两合并成一个有序数组。合并时需要额外数组的帮助这是它空间复杂度 O(n) 的来源。void merge(int a[], int left, int mid, int right) { int len right - left 1; int* tmp (int*)malloc(len * sizeof(int)); int i left, j mid 1, k 0; while (i mid j right) { if (a[i] a[j]) tmp[k] a[i]; else tmp[k] a[j]; } while (i mid) tmp[k] a[i]; while (j right) tmp[k] a[j]; for (i 0; i len; i) a[left i] tmp[i]; free(tmp); } void mergeSort(int a[], int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(a, left, mid); mergeSort(a, mid 1, right); merge(a, left, mid, right); }归并排序的时间复杂度非常稳定最好、平均、最坏都是 O(n log n)这一点比快排强很多。它又是稳定排序所以很多需要稳定排序的大数据场景都会优先考虑归并。缺点是需要额外空间递归也会有 O(log n) 的栈开销。注意mid left (right - left) / 2这种写法可以防止left right溢出虽然排序数组索引一般不会大到越界但写成这样是更好的习惯。归并排序还有个迭代版本不用递归直接从小数组开始两两归并可以避免递归栈过深的问题。工程上像 TimSort 这种改进版归并排序专门针对部分有序的数据做了优化已经是 Python 和 Java 内置排序的核心。2.7 堆排序基于完全二叉树的选择排序优化堆排序可以理解为“进化版选择排序”选择排序每次都要线性扫描找极值而堆排序利用堆这种完全二叉树结构在 O(log n) 时间内找到并调整极值。具体以最大堆为例堆顶永远是最大值把堆顶和末尾元素交换后堆的范围减一再对新的堆顶执行下沉操作重新调整出最大堆重复执行就完成了排序。void heapify(int a[], int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n a[left] a[largest]) largest left; if (right n a[right] a[largest]) largest right; if (largest ! i) { int tmp a[i]; a[i] a[largest]; a[largest] tmp; heapify(a, n, largest); } } void heapSort(int a[], int n) { for (int i n / 2 - 1; i 0; i--) heapify(a, n, i); // 建堆 for (int i n - 1; i 0; i--) { // 排序 int tmp a[0]; a[0] a[i]; a[i] tmp; heapify(a, i, 0); } }建堆的时间复杂度是 O(n)每次堆顶交换后调整是 O(log n)总共 n-1 次调整所以整体是 O(n log n)。最坏、平均、最好都是 O(n log n)。空间 O(1)这是它很大的优势。不稳定因为堆调整过程中会把相同值的元素交换到不同位置。堆排序的实际性能不如快排原因在于它对内存的访问是跳跃式的缓存命中率低。快排访问数组是连续扫描型的对 CPU 缓存更友好。所以除非对最坏时间复杂度有硬性要求、或者内存极其紧张、又或者需要随时从数据流中取出 Top-K不然堆排序并不适合做通用排序。但优先队列、定时任务调度里用堆那可是专业对口。2.8 基数排序非比较排序的经典前面所有排序都基于“比较大小”来决策。基数排序完全不同它不比较元素大小而是按位数“分配”和“收集”。以 LSD最低位优先为例先按个位数字分桶按桶顺序收集再按十位分桶收集接着百位、千位……直到最高位处理完数组自然有序。每个桶本质是先进先出队列保证稳定性。void radixSort(int a[], int n) { int maxVal a[0]; for (int i 1; i n; i) if (a[i] maxVal) maxVal a[i]; for (int exp 1; maxVal / exp 0; exp * 10) { int count[10] {0}; int* output (int*)malloc(n * sizeof(int)); for (int i 0; i n; i) count[(a[i] / exp) % 10]; for (int i 1; i 10; i) count[i] count[i - 1]; for (int i n - 1; i 0; i--) { int digit (a[i] / exp) % 10; output[count[digit] - 1] a[i]; count[digit]--; } for (int i 0; i n; i) a[i] output[i]; free(output); } }设数字最大有 d 位每位的桶数 k10时间复杂度就是 O(d*(nk))。如果 d 是常数可以认为近似 O(n)。空间需要额外 O(nk)。基数排序是稳定排序。它处理非负整数最方便如果要处理负数需要先把所有数加上一个偏移量或者单独处理符号位处理小数和字符串时桶的规则也要重新设计。基数排序在特定场景下非常快比如手机号排序、身份证号排序、日期排序——这些数据都是位数固定的整数或字符串。我测过 10 万个 0 到 99999 之间的随机整数基数排序能跑赢快排因为它跳过了比较开销直接用桶计数。但通用性还是不如比较排序这也是为什么它通常不在标准库的默认排序里出现。3. 性能对比与实测数据3.1 八大排序算法复杂度速查表这份表建议直接收藏。笔试面试里经常要求手写“排序算法复杂度对比表”按下面的内容默写就够了。排序算法最好时间平均时间最坏时间空间复杂度稳定性冒泡排序O(n)O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定插入排序O(n)O(n^2)O(n^2)O(1)稳定希尔排序O(n log n)~O(n^2)约 O(n^1.3)O(n^2)O(1)不稳定快速排序O(n log n)O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定基数排序O(d(nk))O(d(nk))O(d(nk))O(nk)稳定希尔排序那行有个小讲究它的复杂度随增量序列变化不是固定值。考试时写“平均约 O(n^1.3)”算是比较公认的常用说法但如果细究可以单独说明。3.2 不同数据规模下的实测表现我自己在 64 位 Linux 环境下用同一份随机整数数组测试过单位毫秒数据规模从 1 万到 10 万都跑过。直接说结论数据量小于 1000八大算法差距很小甚至选择排序和冒泡排序也能接受不用过度优化。数据量 10000 左右冒泡、选择明显掉队插入排序处于中间希尔、快排、归并、堆排序基本都在同一量级。数据量 100000 以上快排通常是第一名归并紧随其后堆排序稍慢但稳定希尔排序开始吃力基数排序如果是固定位数整数能跟快排掰手腕。这组结果基本印证了理论O(n log n) 级别的算法之间差距主要来自系数而不是复杂度本身的指数。快排的循环结构简单、局部性好所以工程上它赢面最大堆排序虽然复杂度漂亮但跳跃式访问让它实际速度不如归并和快排。如果换个环境数据量到百万级递归带来的栈压力和内存分配会逐渐明显。归并排序需要不断地动态分配临时数组如果每次都 malloc 会有很大开销实际使用中往往会预先分配一块与原始数组等长的 tmp 空间并在递归函数间传递而不是每层都分配。手写归并排序时建议也这样做。3.3 特殊数据分布对排序的影响比数据规模更有意思的是数据本身的样子。我拿四种特殊数据尝试过完全有序、逆序、大量重复、随机分布。完全有序时插入排序和冒泡排序带 flag 优化直接起飞复杂度掉到 O(n)而对快排来说如果基准选择策略是“取第一个元素”完全有序就是最坏情况直接退化到 O(n^2)。这就是鸿沟。所以面试里问“什么情况下快排最慢”答案就是把有序数组配上糟糕的基准选取策略。大量重复数据对快排也很不友好。经典的 Lomuto 分区或 Hoare 分区在全是相同元素时会让划分严重不平衡而三向切分快排可以很好应对重复元素这也是为什么很多标准库实现会检测相同元素。逆序数据对归并和堆排序影响不大因为它们的分治结构天然与初始顺序无关。基数排序也不在乎数据是正序还是逆序只看位数分布。直接说结论如果你知道数据已经基本有序优先考虑插入排序或 TimSort 之类的自适应排序如果数据全是重复值三向切分快排更稳如果数据随机常规快排就够了。4. 常见问题与调优经验实录4.1 快速排序退化的原因与优化方案快排退化成 O(n^2) 的根本原因是 partition 不平衡。解决办法有三个层面随机选择基准每次从当前区间随机挑一个元素作为 pivot让最坏情况变成概率事件。三数取中取区间的左、中、右三个元素的中位数当 pivot能显著降低集合数据下最坏情况的概率。小区间使用插入排序递归到区间长度小于 1020 时停止递归改用插入排序。因为小规模数据的排序开销极低递归反而浪费函数调用时间。// 三数取中示例 int medianPivot(int a[], int low, int high) { int mid low (high - low) / 2; if (a[mid] a[low]) swap(a[low], a[mid]); if (a[high] a[low]) swap(a[low], a[high]); if (a[high] a[mid]) swap(a[mid], a[high]); return a[mid]; }这个优化在工程实现里几乎是标配。我当时手写 STL sort 简化版时加入了分区后右端点落位再配合阈值切换插入排序实测比基础快排快了大约 15% 到 20%。4.2 递归深度导致栈溢出怎么办快排和归并排序都是递归算法极端情况下递归深度可能到 n。对 100 万元素的有序数组如果快排基准选得不好递归深度可能直接让程序崩溃。我遇到过最崩溃的一次是在考试环境里跑大数据测试栈溢出后整个程序无响应白白丢分。解决办法除了优化基准选取外还可以手动实现“尾递归优化”递归处理较短的子区间较长的子区间用迭代方式继续循环。或者干脆把快排改成非递归版本用显式栈保存待处理区间。归并排序则可以用自底向上的迭代版本空间占用不变但避免了递归栈深度问题。提示如果面试要求“实现一个排序”最好先问清数据会不会很大、是否递归安全。否则代码写得很漂亮实际跑大数据直接爆栈还不如换迭代版本更稳妥。4.3 稳定性到底能带来什么实际价值有些同学觉得稳定性只是概念题实际无人在意。但真遇到按多字段排序的业务稳定性就是决定代码简洁度的关键。比如一个对象数组先按姓名排序再按年龄排序。如果第二次排序不稳定那么同年龄的人会乱序你得再补一个复合比较逻辑如果是稳定排序直接两步搞定输出顺序完全正确。归并排序正因为稳定才成为很多语言内置稳定排序算法的首选。手写排序时如果你自己实现的是快速排序想要稳定版本就得改成归并思路这不仅是理论问题更是实际编码问题。还有个容易被忽略的点基数排序的稳定性是它的基础。LSD 基数排序在每一轮分配时必须保证同一个桶内的元素保持上一轮的相对顺序。如果桶内插入时是先进后出那整个排序结果就错了。面试中经常考查“基数排序为什么不稳定就不对”本质就是考对稳定性的理解。4.4 手写排序时最容易踩的几个坑把常见手写 bug 列出来你可以在本地跑代码前先自查快排 partition 里的循环条件while (low high a[high] pivot)必须带low high不然指针会越界。插入排序里外层循环从 1 开始不要从 0 开始。堆排序建堆从n/2 - 1开始不要从 0 开始否则会发生多余的比较和交换。冒泡排序的内层循环边界是n - 1 - i而不是n - i否则会多比较到已排序区域。归并排序的合并循环里左边或右边先耗尽时要处理好剩余元素的拷贝。基数排序的计数数组累加之后收集时一定要从后往前遍历原数组否则会破坏稳定性。我把这些坑排成一张自查表每次写完代码跑测试前先对照一遍。实际经验告诉我90% 的手写排序出错都集中在边界条件而不是算法思路本身。4.5 一个方便测试的验证方法写完排序算法如何快速验证你写得对不对我推荐三步法随机生成一万个数范围可以很小比如 099这样容易产生大量重复值可以顺便验证稳定性相关的基础逻辑。用三组特殊数据测完全有序数组、完全逆序数组、所有元素相同的数组。三组都通过说明算法至少没大问题。如果有标准库排序可用把你的排序结果和std::sort的结果逐元素比较一遍这是最直接的校验。如果你手写的是稳定排序还可以构造一个包含(值, 原始序号)的二元组排序后检查同样值的原始序号是否递增。这样稳定性也能自动化验证。我自己写排序实验时经常用这种方式能快速定位问题。最后想说的几句那么多排序算法真正工作里我用的最多的还是快速排序和归并排序但理解其他排序也绝不白费。希尔排序让我懂了增量序列的启发式思路堆排序让我理解了优先队列的底层结构基数排序让我看到一个完全不同的排序维度。学习排序算法最忌讳只背结论不跑实验。同一份代码换个数据分布表现可能就是天壤之别。建议你把我上面的代码挨个跑一遍亲手测出每张表的数字再遇到性能对比问题就不用靠猜了。 
排序算法大概是数据结构课程里最让人又爱又恨的一块。爱的是思路直观冒泡、插入、选择基本看一遍就能懂恨的是细节太多边界条件、稳定性、复杂度推导一不留神就翻车。我在学习和教学中反复写过七八遍这八大排序算法也做过不少数据规模下的实测对比。这篇文章就把我自己的理解和踩坑记录整理出来覆盖冒泡、选择、插入、希尔、快速、归并、堆、基数这八种经典排序从原理到代码再到复杂度、稳定性、实战选型一次讲透。如果你正在复习数据结构期末、备战考研408或者想把手写排序的水平提上去这篇应该能直接帮你省下大把时间。真正吃透排序算法不能只背代码。你要清楚每个算法在干什么、为什么这么做、数据特征变了之后会发生什么。后面我会先讲几个必须掌握的基础概念再逐个拆算法最后用实测数据和常见坑位收尾。整个逻辑是按照我自己的学习路径来的尽量让零基础也能顺着走下来。1. 排序算法的基础复杂度、稳定性与场景选型1.1 时间复杂度和空间复杂度怎么看复杂度不是用来背的是用来聊天的。两个算法放在一起你首先要能说出它们在不同数据规模、不同数据分布下的表现。我把复杂度拆成最好、平均、最坏三档因为排序算法很吃初始数据。一个已经有序的数组冒泡排序和插入排序能做到 O(n)但选择排序还是老老实实跑 O(n^2)快速排序在已经有序的数组上反而可能退化成 O(n^2)。这就说明只看平均复杂度定生死太粗糙。空间复杂度关注的是额外开辟的内存不包括原数组本身。原地排序in-place的空间复杂度是 O(1)比如冒泡、选择、插入、希尔、堆排序但归并排序需要额外 O(n) 的辅助数组快速排序虽然不需要额外数组但递归调用栈平均要 O(log n) 的空间。基数排序也得额外开桶空间通常是 O(nk)。如果环境内存吃紧这些差距都很关键。提示判断一个排序算法是否“原地”标准是额外空间是否为 O(1)。快排尽管需要递归栈通常仍被算作原地排序的变体但不能简单当成零空间开销。1.2 稳定性为什么重要稳定性指的是值相等的两个元素排序后相对顺序不改变。比如学生成绩按分数排同分的同学还希望按学号顺序排列。解决办法是先按学号排一次再按分数排一次前提是第二次排序必须是稳定的。不稳定的排序算法会在这次“二次排序”里把第一次的结果打乱。所以实际开发中如果数据带有多个字段排序需求稳定性往往是硬指标。归并排序、插入排序、冒泡排序、基数排序稳定选择排序、快速排序、堆排序、希尔排序不稳定。这个结论建议直接记住面试和笔试都很爱考。1.3 排序场景选型思路没有万能排序。数据量小、基本有序插入排序可能比快排还快数据量大、要求稳定归并排序更稳妥在意内存占用堆排序和希尔排序是候选区排序对象是整数且位数有限基数排序可以跑到线性复杂度。真实工程里的排序函数比如 C 的 std::sort或 Python 的 TimSort本质上都是混合策略小数据用插入排序大数据用快排/归并同时检测数据是否接近有序。理解了这层思路你再看源码会豁然开朗。2. 八大经典排序算法逐一拆解下面每个算法我都会按“算法思路、代码实现、复杂度与稳定性、适用场景”来讲。代码用 C 语言风格写注释尽量详细方便直接跑实验。2.1 冒泡排序最直观的交换排序冒泡排序的基本思想是相邻两个元素两两比较如果顺序错误就交换。每一趟排序后当前未排序部分的最大值会像气泡一样“浮”到末尾。总共需要 n-1 趟每趟的比较次数逐次减少。void bubbleSort(int a[], int n) { for (int i 0; i n - 1; i) { bool swapped false; // 本趟是否发生过交换 for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int tmp a[j]; a[j] a[j 1]; a[j 1] tmp; swapped true; } } if (!swapped) break; // 整趟无交换说明已经有序 } }这个swapped标志就是最常见的优化。不加它哪怕数组已经排好序算法还是会傻乎乎地跑完所有趟加了它最好情况时间复杂度降到 O(n)。稳定性上冒泡是稳定排序因为只有前一个元素严格大于后一个元素才交换相等的元素不会互换位置。适用场景比较局限教学演示和极少量数据时用用即可。我实测过 n10000 的随机数组冒泡排序耗时大约是插入排序的十几倍基本属于“能跑但别指望性能”的排序。不过它的优点也很突出实现简单、不易写错、稳定适合作为手写排序的“保底方案”。2.2 选择排序最朴素的极值筛选选择排序的思路比冒泡更直接每一趟从待排序区间中选出最小值放到区间最前面。外层循环控制位置内层循环找最小值找到后交换。void selectionSort(int a[], int n) { for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) minIdx j; } if (minIdx ! i) { int tmp a[i]; a[i] a[minIdx]; a[minIdx] tmp; } } }选择排序无论数据是否有序比较次数都是固定的 n(n-1)/2所以最好、平均、最坏时间复杂度全是 O(n^2)。额外空间是 O(1)。它唯一的优势可能是“交换次数少”每趟最多一次交换总共最多 n-1 次。但是不稳定这一点经常被忽略。怎么理解不稳定举个例子数组[5, 5, 2]第一趟时 minIdx 会指向值为 2 的第三个元素然后与第一个位置的 5 交换结果是[2, 5, 5]。虽然两个 5 值相等但原本靠前的那个 5 被换到了后面相对顺序变化了。如果你需要稳定性选择排序直接出局。实战中它也很少被用到多作为教学入门案例因为思路太简单反而容易给后面学堆排序做铺垫——堆排序本质上就是“用堆快速选出最大值”的选择排序。2.3 插入排序扑克牌式整理插入排序的思路就像打扑克时理牌左手已经拿着的牌是有序的新摸到一张牌从右往左找到合适位置插进去。算法从第二个元素开始把每个元素插入到前面已经有序的子序列里。void insertionSort(int a[], int n) { for (int i 1; i n; i) { int key a[i]; int j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; // 比 key 大的元素往后移 j--; } a[j 1] key; // key 落位 } }插入排序最好情况下是 O(n)也就是数组本身已经有序时每个元素只要比较一次就能落位。平均和最坏都是 O(n^2)空间 O(1)而且稳定。它对“基本有序”的数据非常友好这也是为什么很多高级排序算法在递归深度较小时会切换成插入排序。我有一个很实用的经验当数据量小于 50 时插入排序通常比快排还快。原因在于快排有递归调用和 partition 的额外开销而插入排序的系数极小。实际工程里的混合排序比如 C 的 std::sort 会在小规模区间调用插入排序正是基于这个观察。2.4 希尔排序插入排序的进阶版希尔排序也叫“缩小增量排序”。它先把数组按某个增量 gap 分成若干组每组内做插入排序然后逐步缩小 gap 重复操作最后当 gap1 时相当于做一次标准的插入排序。这样做的好处是前期的大间隔让元素能够快速跨越较远距离整体的逆序程度大幅下降。void shellSort(int a[], int n) { for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key a[i]; int j i - gap; while (j 0 a[j] key) { a[j gap] a[j]; j - gap; } a[j gap] key; } } }复杂度取决于增量序列。上面代码用的是最常规的希尔增量每次减半最坏复杂度是 O(n^2)如果用 Hibbard 增量1, 3, 7, 15...最坏能到 O(n^{3/2})。空间 O(1)。希尔排序是不稳定的因为分组插入排序时相等元素可能被分到不同组它们的相对位置无法保证。实际使用场景是数据量中等、内存敏感、不需要稳定排序时希尔排序是很均衡的选择。它比插入排序快很多又比快排/归并简单不需要额外空间。我见过不少嵌入式项目里的排序就用的希尔排序原因就是代码量少、空间省、不容易出 bug。2.5 快速排序分治思想的代表快速排序是应用最广的排序算法之一。思路是选一个基准值pivot把数组分成左右两部分左边都小于等于基准右边都大于等于基准。然后递归排序左右子区间。关键在于 partition分区这一步它决定了快排的性能和稳定性。int partition(int a[], int low, int high) { int pivot a[low]; // 以第一个元素为基准 while (low high) { while (low high a[high] pivot) high--; a[low] a[high]; while (low high a[low] pivot) low; a[high] a[low]; } a[low] pivot; return low; } void quickSort(int a[], int low, int high) { if (low high) { int pivotIdx partition(a, low, high); quickSort(a, low, pivotIdx - 1); quickSort(a, pivotIdx 1, high); } }快排的平均时间复杂度是 O(n log n)最好也是 O(n log n)最坏是 O(n^2)。最坏情况发生在每次 partition 极度不平衡时例如数组已经有序且每次都取第一个元素作为基准那划分后左右两边长度一边是 0、一边是 n-1递归深度到了 n复杂度退化成 O(n^2)。这也是为什么工程实现里不能简单取第一个元素当基准。优化手段我后面会专门讲这里先记住三个关键词随机基准、三数取中、小区间切换插入排序。稳定性方面快排是不稳定的这个我也不止一次在面试里被问到答案要干脆。适用场景是通用排序的首选只要不要求稳定、递归不会爆栈快排在绝大多数情况下表现都很好。我实测 10 万个随机整数快排通常能在 20 毫秒内排完而归并排序大概要 30 多毫秒这还不算归并额外分配内存的开销。2.6 归并排序稳定排序的标杆归并排序也是分治思想但它不做原地交换而是把数组不断对半拆分直到每个子数组只有一个元素再两两合并成一个有序数组。合并时需要额外数组的帮助这是它空间复杂度 O(n) 的来源。void merge(int a[], int left, int mid, int right) { int len right - left 1; int* tmp (int*)malloc(len * sizeof(int)); int i left, j mid 1, k 0; while (i mid j right) { if (a[i] a[j]) tmp[k] a[i]; else tmp[k] a[j]; } while (i mid) tmp[k] a[i]; while (j right) tmp[k] a[j]; for (i 0; i len; i) a[left i] tmp[i]; free(tmp); } void mergeSort(int a[], int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(a, left, mid); mergeSort(a, mid 1, right); merge(a, left, mid, right); }归并排序的时间复杂度非常稳定最好、平均、最坏都是 O(n log n)这一点比快排强很多。它又是稳定排序所以很多需要稳定排序的大数据场景都会优先考虑归并。缺点是需要额外空间递归也会有 O(log n) 的栈开销。注意mid left (right - left) / 2这种写法可以防止left right溢出虽然排序数组索引一般不会大到越界但写成这样是更好的习惯。归并排序还有个迭代版本不用递归直接从小数组开始两两归并可以避免递归栈过深的问题。工程上像 TimSort 这种改进版归并排序专门针对部分有序的数据做了优化已经是 Python 和 Java 内置排序的核心。2.7 堆排序基于完全二叉树的选择排序优化堆排序可以理解为“进化版选择排序”选择排序每次都要线性扫描找极值而堆排序利用堆这种完全二叉树结构在 O(log n) 时间内找到并调整极值。具体以最大堆为例堆顶永远是最大值把堆顶和末尾元素交换后堆的范围减一再对新的堆顶执行下沉操作重新调整出最大堆重复执行就完成了排序。void heapify(int a[], int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n a[left] a[largest]) largest left; if (right n a[right] a[largest]) largest right; if (largest ! i) { int tmp a[i]; a[i] a[largest]; a[largest] tmp; heapify(a, n, largest); } } void heapSort(int a[], int n) { for (int i n / 2 - 1; i 0; i--) heapify(a, n, i); // 建堆 for (int i n - 1; i 0; i--) { // 排序 int tmp a[0]; a[0] a[i]; a[i] tmp; heapify(a, i, 0); } }建堆的时间复杂度是 O(n)每次堆顶交换后调整是 O(log n)总共 n-1 次调整所以整体是 O(n log n)。最坏、平均、最好都是 O(n log n)。空间 O(1)这是它很大的优势。不稳定因为堆调整过程中会把相同值的元素交换到不同位置。堆排序的实际性能不如快排原因在于它对内存的访问是跳跃式的缓存命中率低。快排访问数组是连续扫描型的对 CPU 缓存更友好。所以除非对最坏时间复杂度有硬性要求、或者内存极其紧张、又或者需要随时从数据流中取出 Top-K不然堆排序并不适合做通用排序。但优先队列、定时任务调度里用堆那可是专业对口。2.8 基数排序非比较排序的经典前面所有排序都基于“比较大小”来决策。基数排序完全不同它不比较元素大小而是按位数“分配”和“收集”。以 LSD最低位优先为例先按个位数字分桶按桶顺序收集再按十位分桶收集接着百位、千位……直到最高位处理完数组自然有序。每个桶本质是先进先出队列保证稳定性。void radixSort(int a[], int n) { int maxVal a[0]; for (int i 1; i n; i) if (a[i] maxVal) maxVal a[i]; for (int exp 1; maxVal / exp 0; exp * 10) { int count[10] {0}; int* output (int*)malloc(n * sizeof(int)); for (int i 0; i n; i) count[(a[i] / exp) % 10]; for (int i 1; i 10; i) count[i] count[i - 1]; for (int i n - 1; i 0; i--) { int digit (a[i] / exp) % 10; output[count[digit] - 1] a[i]; count[digit]--; } for (int i 0; i n; i) a[i] output[i]; free(output); } }设数字最大有 d 位每位的桶数 k10时间复杂度就是 O(d*(nk))。如果 d 是常数可以认为近似 O(n)。空间需要额外 O(nk)。基数排序是稳定排序。它处理非负整数最方便如果要处理负数需要先把所有数加上一个偏移量或者单独处理符号位处理小数和字符串时桶的规则也要重新设计。基数排序在特定场景下非常快比如手机号排序、身份证号排序、日期排序——这些数据都是位数固定的整数或字符串。我测过 10 万个 0 到 99999 之间的随机整数基数排序能跑赢快排因为它跳过了比较开销直接用桶计数。但通用性还是不如比较排序这也是为什么它通常不在标准库的默认排序里出现。3. 性能对比与实测数据3.1 八大排序算法复杂度速查表这份表建议直接收藏。笔试面试里经常要求手写“排序算法复杂度对比表”按下面的内容默写就够了。排序算法最好时间平均时间最坏时间空间复杂度稳定性冒泡排序O(n)O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定插入排序O(n)O(n^2)O(n^2)O(1)稳定希尔排序O(n log n)~O(n^2)约 O(n^1.3)O(n^2)O(1)不稳定快速排序O(n log n)O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定基数排序O(d(nk))O(d(nk))O(d(nk))O(nk)稳定希尔排序那行有个小讲究它的复杂度随增量序列变化不是固定值。考试时写“平均约 O(n^1.3)”算是比较公认的常用说法但如果细究可以单独说明。3.2 不同数据规模下的实测表现我自己在 64 位 Linux 环境下用同一份随机整数数组测试过单位毫秒数据规模从 1 万到 10 万都跑过。直接说结论数据量小于 1000八大算法差距很小甚至选择排序和冒泡排序也能接受不用过度优化。数据量 10000 左右冒泡、选择明显掉队插入排序处于中间希尔、快排、归并、堆排序基本都在同一量级。数据量 100000 以上快排通常是第一名归并紧随其后堆排序稍慢但稳定希尔排序开始吃力基数排序如果是固定位数整数能跟快排掰手腕。这组结果基本印证了理论O(n log n) 级别的算法之间差距主要来自系数而不是复杂度本身的指数。快排的循环结构简单、局部性好所以工程上它赢面最大堆排序虽然复杂度漂亮但跳跃式访问让它实际速度不如归并和快排。如果换个环境数据量到百万级递归带来的栈压力和内存分配会逐渐明显。归并排序需要不断地动态分配临时数组如果每次都 malloc 会有很大开销实际使用中往往会预先分配一块与原始数组等长的 tmp 空间并在递归函数间传递而不是每层都分配。手写归并排序时建议也这样做。3.3 特殊数据分布对排序的影响比数据规模更有意思的是数据本身的样子。我拿四种特殊数据尝试过完全有序、逆序、大量重复、随机分布。完全有序时插入排序和冒泡排序带 flag 优化直接起飞复杂度掉到 O(n)而对快排来说如果基准选择策略是“取第一个元素”完全有序就是最坏情况直接退化到 O(n^2)。这就是鸿沟。所以面试里问“什么情况下快排最慢”答案就是把有序数组配上糟糕的基准选取策略。大量重复数据对快排也很不友好。经典的 Lomuto 分区或 Hoare 分区在全是相同元素时会让划分严重不平衡而三向切分快排可以很好应对重复元素这也是为什么很多标准库实现会检测相同元素。逆序数据对归并和堆排序影响不大因为它们的分治结构天然与初始顺序无关。基数排序也不在乎数据是正序还是逆序只看位数分布。直接说结论如果你知道数据已经基本有序优先考虑插入排序或 TimSort 之类的自适应排序如果数据全是重复值三向切分快排更稳如果数据随机常规快排就够了。4. 常见问题与调优经验实录4.1 快速排序退化的原因与优化方案快排退化成 O(n^2) 的根本原因是 partition 不平衡。解决办法有三个层面随机选择基准每次从当前区间随机挑一个元素作为 pivot让最坏情况变成概率事件。三数取中取区间的左、中、右三个元素的中位数当 pivot能显著降低集合数据下最坏情况的概率。小区间使用插入排序递归到区间长度小于 1020 时停止递归改用插入排序。因为小规模数据的排序开销极低递归反而浪费函数调用时间。// 三数取中示例 int medianPivot(int a[], int low, int high) { int mid low (high - low) / 2; if (a[mid] a[low]) swap(a[low], a[mid]); if (a[high] a[low]) swap(a[low], a[high]); if (a[high] a[mid]) swap(a[mid], a[high]); return a[mid]; }这个优化在工程实现里几乎是标配。我当时手写 STL sort 简化版时加入了分区后右端点落位再配合阈值切换插入排序实测比基础快排快了大约 15% 到 20%。4.2 递归深度导致栈溢出怎么办快排和归并排序都是递归算法极端情况下递归深度可能到 n。对 100 万元素的有序数组如果快排基准选得不好递归深度可能直接让程序崩溃。我遇到过最崩溃的一次是在考试环境里跑大数据测试栈溢出后整个程序无响应白白丢分。解决办法除了优化基准选取外还可以手动实现“尾递归优化”递归处理较短的子区间较长的子区间用迭代方式继续循环。或者干脆把快排改成非递归版本用显式栈保存待处理区间。归并排序则可以用自底向上的迭代版本空间占用不变但避免了递归栈深度问题。提示如果面试要求“实现一个排序”最好先问清数据会不会很大、是否递归安全。否则代码写得很漂亮实际跑大数据直接爆栈还不如换迭代版本更稳妥。4.3 稳定性到底能带来什么实际价值有些同学觉得稳定性只是概念题实际无人在意。但真遇到按多字段排序的业务稳定性就是决定代码简洁度的关键。比如一个对象数组先按姓名排序再按年龄排序。如果第二次排序不稳定那么同年龄的人会乱序你得再补一个复合比较逻辑如果是稳定排序直接两步搞定输出顺序完全正确。归并排序正因为稳定才成为很多语言内置稳定排序算法的首选。手写排序时如果你自己实现的是快速排序想要稳定版本就得改成归并思路这不仅是理论问题更是实际编码问题。还有个容易被忽略的点基数排序的稳定性是它的基础。LSD 基数排序在每一轮分配时必须保证同一个桶内的元素保持上一轮的相对顺序。如果桶内插入时是先进后出那整个排序结果就错了。面试中经常考查“基数排序为什么不稳定就不对”本质就是考对稳定性的理解。4.4 手写排序时最容易踩的几个坑把常见手写 bug 列出来你可以在本地跑代码前先自查快排 partition 里的循环条件while (low high a[high] pivot)必须带low high不然指针会越界。插入排序里外层循环从 1 开始不要从 0 开始。堆排序建堆从n/2 - 1开始不要从 0 开始否则会发生多余的比较和交换。冒泡排序的内层循环边界是n - 1 - i而不是n - i否则会多比较到已排序区域。归并排序的合并循环里左边或右边先耗尽时要处理好剩余元素的拷贝。基数排序的计数数组累加之后收集时一定要从后往前遍历原数组否则会破坏稳定性。我把这些坑排成一张自查表每次写完代码跑测试前先对照一遍。实际经验告诉我90% 的手写排序出错都集中在边界条件而不是算法思路本身。4.5 一个方便测试的验证方法写完排序算法如何快速验证你写得对不对我推荐三步法随机生成一万个数范围可以很小比如 099这样容易产生大量重复值可以顺便验证稳定性相关的基础逻辑。用三组特殊数据测完全有序数组、完全逆序数组、所有元素相同的数组。三组都通过说明算法至少没大问题。如果有标准库排序可用把你的排序结果和std::sort的结果逐元素比较一遍这是最直接的校验。如果你手写的是稳定排序还可以构造一个包含(值, 原始序号)的二元组排序后检查同样值的原始序号是否递增。这样稳定性也能自动化验证。我自己写排序实验时经常用这种方式能快速定位问题。最后想说的几句那么多排序算法真正工作里我用的最多的还是快速排序和归并排序但理解其他排序也绝不白费。希尔排序让我懂了增量序列的启发式思路堆排序让我理解了优先队列的底层结构基数排序让我看到一个完全不同的排序维度。学习排序算法最忌讳只背结论不跑实验。同一份代码换个数据分布表现可能就是天壤之别。建议你把我上面的代码挨个跑一遍亲手测出每张表的数字再遇到性能对比问题就不用靠猜了。