如果你已经会写冒泡排序甚至能磕磕绊绊写出一版快速排序再看这篇文章可能会觉得有点低水平重复。但请回想一个场景面试官让你把一组对象按某个字段排序并解释std::sort为什么比自己手写的快排还快或者面对上千万个取值集中在 0~1000 的整数你会选哪个算法十大经典排序算法之所以值得从头过一遍不是为了背代码而是为了在原理、复杂度、稳定性、内存占用之间建立一套属于自己的决策网络。这篇文章就用 C 落地逐个拆解这十个算法的原理、代码、执行过程示意和性能对比再补上我在手写和选型中踩过的一些坑适合正在学 C、准备算法面试或者想真正看懂排序库实现细节的人。1. 先弄懂衡量排序的尺子复杂度、稳定性、原地性1.1 别只背复杂度符号最好、平均、最坏分别代表什么评判一个排序算法第一步永远是对复杂度的理解。这个大家都知道但很多人只记住了O(n²)O(n log n)这样的平均复杂度忽略了最坏和最坏之间的差距而这恰恰是选型时最容易翻车的地方。以冒泡排序为例最好情况是 O(n)因为一趟扫描后发现没有任何交换可以直接终止但平均和最坏情况都是 O(n²)。选择排序则完全不同无论输入是否有序它的比较次数都固定为 n(n-1)/2所以最好、平均、最坏清一色 O(n²)。插入排序又不一样面对几乎有序的数据时平均接近 O(n)面对逆序数据时又退化为 O(n²)。所以在看复杂度表的时候一定要关注三个值分别对应什么样的输入最好情况通常是数据已经基本有序有利于提前终止或快速定位最坏情况往往是数据逆序或分区极度不均衡这也是算法能否用于生产环境的关键平均情况一般指随机排列下的期望值工程上最常参考。空间复杂度同样容易被低估。归并排序时间上非常优秀但需要 O(n) 辅助空间1 亿个int就是 400MB 额外内存堆排序和快速排序能做到原地排序但快速排序的递归栈在极端情况下会到 O(n)这在大数据量、内存受限的场景里是致命的。1.2 为什么存在 O(n) 的排序算法比较排序与非比较排序的分界十个经典排序可以分成两大阵营比较排序和非比较排序。冒泡、选择、插入、希尔、归并、快排、堆排都是通过比较两个元素的大小来做决策而计数、基数、桶排序则是利用数据本身的分布特征直接放到位绕开了比较。这不是巧合而是有一个信息论下限在起作用任意比较排序的最坏情况复杂度不可能低于 O(n log n)。因为 n 个不同元素的排列有 n! 种排序的过程本质上是在决策树中定位其中一种排列而比较一次最多产生两个分支所以至少需要 log₂(n!) 次比较约等于 n log₂n。这意味着什么如果你写的排序算法时间复杂度能做到 O(n)那它一定不是基于通用比较的。计数排序的快本质上是拿范围换时间基数排序的快是拿位数换时间桶排序的快是拿分布均匀度换时间。理解了这个分界就不会问出为什么计数排序比快速排序快这么多这种问题了——它根本不是同一类武器。2. 第一梯队 O(n²) 三兄弟冒泡、选择、插入2.1 冒泡排序教学价值远高于工程价值冒泡排序的核心逻辑很简单每轮从开头相邻比较如果前一个比后一个大就交换最大的元素会像气泡一样浮到末尾。代码写出来大概是这样void bubbleSort(vectorint a) { int n a.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j 1 n - i; j) { if (a[j] a[j 1]) { swap(a[j], a[j 1]); swapped true; } } if (!swapped) break; } }我加了一个提前终止的标记如果某一轮没有发生任何交换说明序列已经完全有序直接结束。这个优化能把最好情况从 O(n²) 拉到 O(n)也是面试中常被追问的细节。看一个执行过程数组[4, 2, 7, 1]第一轮比较 4 和 2交换得到[2, 4, 7, 1]比较 4 和 7不动得到[2, 4, 7, 1]比较 7 和 1交换得到[2, 4, 1, 7]第二轮下来[2, 1, 4, 7]第三轮[1, 2, 4, 7]。整个过程很直观但缺陷也很明显相邻交换的效率太低每个元素可能要被搬运很多次随机数据下比较和交换次数都接近 n²/2。工程上几乎没有理由用它我一般建议把它当作排序思想入门的第一课来学而不是当作可复用的工具。2.2 选择排序交换次数少但稳定性这个坑必须知道选择排序的思路更直接第 i 轮在未排序区间[i, n-1]里找到最小元素和位置 i 交换。代码如下void selectionSort(vectorint a) { int n a.size(); 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) swap(a[i], a[minIdx]); } }它在某些场景下有一个独特优势每轮最多交换一次总共最多 n-1 次交换。如果排序对象不是int而是体积很大的对象且移动对象比比较对象昂贵很多选择排序的交换开销就比冒泡有吸引力。但注意它仍然有 O(n²) 的比较次数所以这个优势也没有想象中那么大。选择排序最大的问题是不稳定。看一个例子数组[5a, 5b, 3]两个 5 相等我们用下标区分它们。第一轮找到最小值 3然后把它和位置 0 的 5a 交换得到[3, 5b, 5a]。原本在前面的 5a 跑到了后面两个相等元素的相对顺序被翻转了。如果排序对象中包含多个字段后续要用另一个关键字继续排序这个不稳定性就会产生连锁问题。2.3 插入排序小数组场景下被严重低估的王者插入排序很容易和打牌联系起来每次把新摸到的牌插入到手里已经排好的牌中。代码实现template typename T void insertionSort(vectorT a) { int n a.size(); for (int i 1; i n; i) { T key a[i]; int j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; --j; } a[j 1] key; } }别看它也是 O(n²) 复杂度它的真实价值体现在两点。第一它是在线排序不需要一次性拿到所有数据可以一边读取一边保持有序。比如系统日志按时间顺序不断到达插入排序天然适合这种场景。第二它对基本有序的数据极度友好复杂度可以降到 O(n)。这也是为什么标准库的排序实现会在小区间里切到插入排序。std::sort这种工业级实现并不是一直用快排而是分层策略n 很小常见阈值在 16 到 32 左右时直接用插入排序n 大时用快速排序继续切分。为什么因为 O(n log n) 只是渐近复杂度忽略了常数因子。当 n 只有二十几时插入排序的常数小、内存访问局部性好实测往往比递归式的快排更快。这个思路我在后面第 6 节会展开。3. 进阶 O(n log n) 四将希尔、归并、快排、堆排3.1 希尔排序把插入排序的短板用增量跳转补上希尔排序是插入排序的改进版思路是先按一定间隔 gap 把数组分成多个子序列分别做插入排序然后逐步缩小 gap最后 gap1 时做一次完整的插入排序。为什么这样有效因为普通插入排序每次只能把元素往后移一位遇到一个大数在开头、一个小数在末尾的逆序数组时搬运成本极高。希尔排序通过大步长提前把小元素跳跃式地挪到前面减少了后续移动量。void shellSort(vectorint a) { int n a.size(); for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key a[i]; int j i; while (j gap a[j - gap] key) { a[j] a[j - gap]; j - gap; } a[j] key; } } }这里gap n/2; gap / 2是最容易理解的增量序列但它的最坏情况仍然是 O(n²)。如果采用 Hibbard、Sedgewick 等精心设计的增量序列平均复杂度可以降到 O(n^1.3) 左右。希尔排序不稳定因为相同元素可能在跨越多个 gap 的移动中交换次序。工程上单独用希尔排序的不多但它训练了一个很重要的思维通过预处理让数据基本有序再把精细活交给插入排序。3.2 归并排序稳定性与可预测性的代表归并排序是典型的分治思想把数组从中间一分为二分别排序再把两个有序子数组合并成一个。复杂度永远稳定在 O(n log n)最好最坏一个样而且它是 O(n log n) 家族里少有的稳定排序。void merge(vectorint a, int l, int m, int r) { vectorint tmp(r - l 1); int i l, j m 1, k 0; while (i m j r) { tmp[k] (a[i] a[j]) ? a[i] : a[j]; } while (i m) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int t 0; t (int)tmp.size(); t) { a[l t] tmp[t]; } } void mergeSort(vectorint a, int l, int r) { if (l r) return; int m l (r - l) / 2; mergeSort(a, l, m); mergeSort(a, m 1, r); merge(a, l, m, r); }有个 C 实操细节一定要提不要在merge函数里每次递归都 new 一个 vector。如果数组规模是 10 万递归深度大约 17 层每一层有多个 merge 调用频繁分配释放内存会让归并排序慢到怀疑人生。正确做法是提前分配一个和原数组等长的辅助数组在合并时不断复用。归并排序的空间复杂度是 O(n)同时又依赖递归栈但它有一项不可替代的能力可以改造为外部排序。当数据量大到内存装不下时分段读取到内存里排好序再不断合并磁盘上的有序段这个过程就是归并思想的工程化。std::stable_sort的底层思路也偏向归并因为它需要保证相等元素的相对顺序。3.3 快速排序平均最快但最怕有序和重复快速排序的平均复杂度优秀、常数小、内存访问局部性好是绝大多数通用排序库的默认主力。核心在于 partition选一个基准值 pivot把数组分成小于 pivot和大于等于 pivot两半然后分别递归。我给出最常用来教学的 Lomuto 分区int partition(vectorint a, int l, int r) { int pivot a[r]; int i l; for (int j l; j r; j) { if (a[j] pivot) { swap(a[i], a[j]); i; } } swap(a[i], a[r]); return i; } void quickSort(vectorint a, int l, int r) { if (l r) return; int p partition(a, l, r); quickSort(a, l, p - 1); quickSort(a, p 1, r); }用一个例子看分区过程数组[4, 2, 7, 1, 3]选末尾 3 作为 pivotj043 不成立i 不动j123 成立交换a[0]和a[1]得到[2, 4, 7, 1, 3]i 变为 1j273 不成立j313 成立交换a[1]和a[3]得到[2, 1, 7, 4, 3]i 变为 2最后交换a[2]和a[4]得到[2, 1, 3, 4, 7]pivot 3 落在了正确位置左右两个子区间分别是[2,1]和[4,7]。快速排序不稳定因为互相交换时可能把相等的值越过对方。快排最经典的坑是退化。如果每次都选末尾作为 pivot而输入已经有序那么每次划分只能排除一个元素递归深度变成 O(n)时间复杂度退化成 O(n²)。解决思路有三个常用方案随机选 pivot让最坏输入难以稳定触发代价是随机数开销三点取中取首、中、尾三个位置的中间值作为 pivot对有序数据特别有效三路切分把等于 pivot 的值单独放中间大幅缓解大量重复元素的退化问题。这些优化在第三节后面会给出代码视角。std::sort的典型实现正是综合了这些手段先三点取中或随机选基准小区间切到插入排序再配合检测递归深度如果递归太深会自动切换到堆排序来兜底保证最坏情况仍然维持在 O(n log n)。3.4 堆排序最坏情况也很稳但缓存命中率让人头疼堆排序的思路是先把数组构建成一个大顶堆然后反复把堆顶也就是最大值交换到数组末尾再缩小堆的范围重新调整堆。复杂度稳定在 O(n log n)而且完全原地不需要额外内存。void heapify(vectorint a, int n, int i) { int largest i; int l 2 * i 1; int r 2 * i 2; if (l n a[l] a[largest]) largest l; if (r n a[r] a[largest]) largest r; if (largest ! i) { swap(a[i], a[largest]); heapify(a, n, largest); } } void heapSort(vectorint a) { int n a.size(); for (int i n / 2 - 1; i 0; --i) { heapify(a, n, i); } for (int i n - 1; i 0; --i) { swap(a[0], a[i]); heapify(a, i, 0); } }堆排序让我印象最深的问题不是正确性而是性能视觉欺骗。理论上它和快排、归并同为 O(n log n)实际跑随机大数组时往往明显慢于快排甚至输给归并。原因在于内存访问的跳跃性堆化时访问下标 2i1、2i2元素之间跨度随机CPU 缓存扫描的效率不如快排那样线性和连续。所以堆排序的实际定位是当最坏情况不能被接受、又必须原地排序时它是快排的兜底方案。需要部分排序时std::partial_sort这类接口底层也是堆排序思路来维护一个 k 大小的堆。4. 打破 O(n log n) 上限计数、基数、桶排序4.1 计数排序范围小、值域集中的大杀器计数排序的思想是做统计而不是比较。它要求数据是有限范围内的整数比如成绩 0~100 分或者 ID 集中分布在 1 万以内。核心是建立一个计数数组统计每个值出现的次数再通过前缀和确定每个元素的最终位置。vectorint countingSort(const vectorint a, int K) { vectorint cnt(K 1, 0); vectorint res(a.size()); for (int x : a) cnt[x]; for (int i 1; i K; i) cnt[i] cnt[i - 1]; for (int i (int)a.size() - 1; i 0; --i) { res[--cnt[a[i]]] a[i]; } return res; }为什么最后一步要从后往前遍历为了让计数排序保持稳定。cnt[x]在累加后表示小于等于 x 的元素个数从后往前扫时最后一个遇到的 x 会被放到所属区间的末尾这样相同值的相对顺序就被保留住了。如果数据范围里有负数不能直接拿负数当下标。常见做法是整体平移比如数值范围是 [-100, 100]就统一加 100 映射到 [0, 200]排序完再减回去。计数排序的时间复杂度是 O(n k)其中 k 是值域宽度。当 k 远大于 n 时就非常浪费比如 100 个数分布在 0 到 1 亿之间建一个 1 亿大小的计数数组显然不划算。4.2 基数排序把多轮计数排序串成一条链基数排序是计数排序按位扩展的版本。以整数为例从最低位开始按当前位的数字做一次稳定的计数排序然后依次处理十位、百位、千位……只要每轮排序保持稳定低位之间的关系就会被保留最终整体有序。void countingSortByDigit(vectorint a, int exp) { vectorint cnt(10, 0), res(a.size()); for (int x : a) cnt[(x / exp) % 10]; for (int i 1; i 10; i) cnt[i] cnt[i - 1]; for (int i (int)a.size() - 1; i 0; --i) { int digit (a[i] / exp) % 10; res[--cnt[digit]] a[i]; } a res; } void radixSort(vectorint a) { int maxVal *max_element(a.begin(), a.end()); for (int exp 1; maxVal / exp 0; exp * 10) { countingSortByDigit(a, exp); } }从执行过程来看比如数组[321, 245, 130, 12]按个位排[130, 321, 12, 245]按十位排[12, 321, 130, 245]按百位排[12, 130, 245, 321]每一轮都稳住了前面的低位顺序百位相等时十位依然有序这就是基数排序能稳住整体的原因。它的复杂度是 O(d × (n k))d 是最大数的位数。如果数字位数很多或者每位取值空间很大效率会打折。不过它同样适用于定长字符串排序逻辑完全一致。需要特别注意负数。上面这段代码在遇到负数时会漏排。一种做法是先分离负数和正数分别做基数排序最后把负数部分反转再拼接另一种做法是把所有数统一偏移到非负区间。4.3 桶排序数据分布才是它的命根子桶排序的思路是把数据按大小均匀切分成 k 个桶每个桶内部再用插入排序等算法排好最后按桶顺序依次输出。它最典型的应用场景是范围清晰的浮点数比如[0, 1)区间内均匀分布的数据void bucketSort(vectorfloat a) { int n a.size(), k n; vectorvectorfloat buckets(k); for (float x : a) { int idx (int)(x * k); if (idx k) idx k - 1; buckets[idx].push_back(x); } for (auto b : buckets) insertionSort(b); int idx 0; for (auto b : buckets) { for (float x : b) a[idx] x; } }桶排序的复杂度高度依赖分布。如果数据均匀分布在[0,1)每个桶里的元素大约只有一两个总复杂度趋近 O(n)。但如果数据全挤在一个桶里桶排序就退化成一个桶里的插入排序复杂度直逼 O(n²)。真实数据不一定均匀所以工程中很少直接拿桶排序做通用方案但在处理类似大规模均匀分布的随机数、按时间戳分桶统计再排序这类场景时它的思路非常实用。真正关键的是桶的划分要结合数据分布特征而不是硬套公式。5. 十大排序横向对比与 C 工程选型策略5.1 一张表看清全部关键指标排序算法最坏时间平均时间空间复杂度稳定性一句话定位冒泡排序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)稳定小范围整数排序基数排序O(d·(nk))O(d·(nk))O(n k)稳定定长数字/字符串桶排序O(n²)O(n k)O(n k)稳定均匀分布数据冒泡的平均 O(n²)和希尔那行我在表格里做了简化。工程上真正值得优先记住的是结论追求稳定就考虑归并或插入追求通用就选快排害怕最坏情况可选堆排序数据有明确范围或分布特性时非比较排序会有决定性的速度优势。5.2 面对真实需求怎么挑排序我总结一套简单粗暴的决策流程面试和开发初期都非常好用n 很小几十到上百直接插入排序常数小且代码简单n 很大没有特殊限制默认选基于快排思想的通用排序比如std::sort要求稳定选归并排序思路没有排序库可用时就用std::stable_sort内存极紧且不允许额外分配考虑堆排序数据是取值范围较小的整数比如 0~10000优先计数排序数据是定长整数或字符串位数不多适合基数排序数据疑似均匀分布比如大量[0,1)浮点数可以试桶排序需要实时保持有序只有数据一个接一个到达插入排序的在线特性很有用。实际的排序需求通常没有你想的那么抽象。比如对用户 ID 排序ID 往往是连续整数段计数排序可以秒杀快排对浮点数做科学计算则大概率还是快排和插入排序的组合。选型永远要看数据长什么样而不是哪个算法名字更高级。5.3 C 标准库里的排序sort、stable_sort、partial_sort 怎么用C 标准库已经提供了非常成熟的接口但很多人没有完全弄清楚它们之间的差异。std::sort通常被实现为内省排序IntroSort表现形式上是快排但会在递归过深时切换到堆排序在小区间切换到插入排序综合了稳定性和性能。它的最大限制是不稳定而且要求迭代器是随机访问迭代器。std::stable_sort保证相等元素顺序不变但代价是有额外的内存需求性能通常也不如sort。std::partial_sort用于只关心前 k 小或前 k 大的场景底层维护一个小堆复杂度接近 O(n log k)而不是把整个数组完整排一遍。在 C 工程里还需要注意两个容易被忽视的点。第一排序对象如果是结构体尽量用移动而非拷贝swap对大对象代价很高可以给类型定义移动构造函数或直接使用std::move辅助。第二浮点数的比较默认按数值序但 NaN 的存在会让比较规则很不直观必须先约定 NaN 怎么处理。这些细节往往比选哪个算法更早地决定程序是否正确。6. 手写排序前的自我体检常见错误、测试套路与优化三板斧6.1 你以为写对了其实这些地方最容易翻车手写排序最大的错觉是能跑通不等于写对了。我见过很多次看似正常的快排换到逆序数组就死循环换到大量重复元素就超时。常见错误集中在这几个位置快排递归边界写错if (l r)和if (l r)只差一个条件结果完全不同前者可能导致无限递归partition 返回的位置不准确导致基准元素被重复排序或漏排序插入排序内部用a[j] a[i]而不是先保存key当元素被后移后a[i]已经变了结果错乱归并排序合并时把m 1写成m数组越界或丢元素堆排序的heapify没有检查左右孩子是否越界小数组上直接访问越界内存计数排序忘了处理负数偏移或者把计数数组的大小写成 n 而不是 k。这些问题有一个共同特征代码在随机小数组上不容易暴露一上大数据或特殊数据就现原形。所以写完算法之后必须用多种输入做验证。6.2 一个能帮你兜底的 C 自测框架我习惯在练习时写一个很小的自测函数把每种排序都丢进去跑一遍。基本形式是这样template typename Func void checkSort(const string name, Func func) { srand(42); vectorint sizes {0, 1, 2, 10, 100, 10000}; for (int n : sizes) { vectorint a(n); for (int x : a) x rand() % 1000; vectorint b a; func(a); sort(b.begin(), b.end()); if (a ! b) { cout name failed at size n \n; return; } } cout name passed\n; }这个框架虽然简单但很实用。第一它覆盖了空数组、单元素、小数组、随机大数组。第二srand(42)固定随机种子保证每次跑出来是同一批数据方便复现问题。第三直接用std::sort的结果当参考答案避免自己手动人工排序出错。这只是第一层测试。第二层要加入极端数据完全有序、完全逆序、大量重复、几乎有序、全部相等。很多算法在这些数据上的行为截然不同。第三层是稳定性测试用make_pair这样的结构体同时携带原始位置信息排序后检查相等元素的原始位置是否保持递增。不要觉得这些测试麻烦它们能在你手滑写错边界时直接报错节省的时间远比写测试框架的时间多。6.3 从教科书快排走向工程级快排的优化三板斧如果只是应付笔试上面那段 Lomuto 快排已经够用。但想理解工程实现或者想让自己的手写快排在 10 万级数据上依然出色三板斧必须熟练掌握。第一斧小区间切到插入排序。递归快排在处理小数组时函数调用开销占比极高常见的做法是当r - l 1 16时不再递归而是调用插入排序。这个阈值不需要精确到具体某个数经验值大概在 16 到 32 之间标准库也基本落在这个范围。原因是小规模下 O(n²) 的插入排序常数比递归函数调用和栈帧开销小得多。第二斧三点取中选 pivot。取a[l]、a[m]、a[r]三者的中间值作为基准值。这个优化的直接效果是让有序数组这种最容易造成快排退化的输入不再稳定地触发最坏情况。它不保证数学上的绝对最优但工程上收益明显。第三斧三路切分。经典的 partition 会把相等的元素分散到两侧大量重复元素时递归区间仍然很大。三路切分把数组切成小于 pivot、等于 pivot、大于 pivot三段递归只处理小于和大于两部分。以纯重复数组为例三路快排走完一轮就直接结束时间从 O(n²) 变成 O(n)。void quickSort3way(vectorint a, int l, int r) { if (l r) return; int lt l, gt r, i l 1; int pivot a[l]; while (i gt) { if (a[i] pivot) swap(a[lt], a[i]); else if (a[i] pivot) swap(a[i], a[gt--]); else i; } quickSort3way(a, l, lt - 1); quickSort3way(a, gt 1, r); }我实际练习中的一个体会是写完排序后不要急着跑性能先跑三种脏数据——反序、全相等、递增加尾部乱序。这三种输入基本能覆盖掉 90% 以上的边界错误。如果这三关都过了再拿大数据测时间才有意义。最后再分享一个小技巧把边界判断和交换逻辑尽量拆成独立的函数或小步骤一旦出错你打印中间状态时能立刻定位问题是出在分区、合并还是堆调整上。排序算法是练基本功最好的场地但也最容易让人以为自己会了之后才发现还差得远。
