排序算法这玩意儿写过的人多写对的人少。我最早写快排的时候自以为背下了那十行代码结果在一个全是重复元素的数组上跑了将近两秒——分区函数把相等元素全甩到一边直接退化成冒泡。后来做嵌入式项目栈空间只有几KB递归快排在万级数据上直接把栈撑爆才被迫去啃非递归写法。再往后做数据报表和日志聚合又遇到必须保证相等元素原始顺序不能乱的场景稳定性这个问题才真正从“面试考点”变成了“线上事故”。这篇东西就是把快排、归并的非递归实现连同八大排序的时间空间复杂度与稳定性判定一次讲透。不管你是刚学 C 语言想搞懂指针和数组边界的新手还是写过几年代码想在性能上抠细节的老手下面这些内容应该都能直接用上。1. 先把排序这件事拆开八大排序到底在比什么1.1 从两次真实的翻车说起我第一次对排序算法产生敬畏是给一批传感器采样数据做去重前的排序。数据量不大两万条左右用递归快排跑得飞快我当时还挺得意。换到另一批数据上就出问题了——这批数据里大量采样值完全相同因为采集间隔短、量程小重复率超过七成。快排分区的时候a[j] pivot把所有等于 pivot 的元素全划到右边每次递归只能砍掉一个或者极少数元素递归深度接近 n时间复杂度退化成 O(n²)同时还把调用栈吃穿了一半。第二次翻车是排序一个记录结构体数组按时间戳排结果发现同一毫秒内的几条记录顺序在排序前后对不上。查了半天问题出在用的快排不稳定上原本按采集顺序进来的记录被交换打乱了相对位置导致下游按顺序聚合的时候把时间窗内的数据算错了。这两件事让我明白排序算法从来不是“会写快排就够了”八大排序各自解决的是一类特定问题选错就是给自己挖坑。1.2 八大排序的本质分类抛开具体的代码长相八大排序其实可以按“它们靠什么把数据变有序”分成三大流派靠相邻元素逐步移动的冒泡排序、插入排序。这类算法的核心动作是“交换或移动相邻的两个位置”所以它们天生稳定因为只有严格逆序时才交换相等元素永远不会越过对方。代价是元素要一格一格挪平均 O(n²)。靠拉开间隔大跨度移动的希尔排序、快速排序、堆排序。这类算法为了突破 O(n²)必须让元素做出“远距离跳跃”而一旦跳跃相等元素的相对次序就保不住了所以它们天然不稳定。靠额外空间做归位的归并排序、计数排序。归并是“先递归排好两半再合并”合并时只要左边先取稳定性就能保住计数排序则是“统计每个值出现几次再按值域顺序填回去”如果实现时从后往前填稳定性也能保住。这三种流派的分野解释了后面所有复杂度与稳定性结论的由来。你只要能判断一个算法是“邻位挪动”还是“跨位跳跃”稳定性基本就能猜对八九成。1.3 时空复杂度与稳定性对照表下面这张表是我自己整理后贴在显示器边上的版本括号里标注了关键前提