排序算法是C学习路上绕不开的一堵墙校招笔试会考日常开发中排序也几乎是最高频的基础操作。但十大排序算法放在一起原理容易混、代码容易记串、复杂度更容易背错。这篇内容我把十大经典排序算法用C重写了一遍并逐项分析它们的原理、完整代码实现、时间复杂度推导和排序稳定性最后附上工程实践中的选型经验与排查技巧希望能帮你把这套知识真正串起来。1. 先有个整体框架分类、复杂度与稳定性总览在学习每个算法之前我建议先把十大排序算法按“时间复杂度阵营”和“稳定性”这两个维度分层这样后面读代码时脑子才不乱。1.1 按时间复杂度划分的三个阵营第一个阵营是O(n²)的基础排序包含冒泡排序、选择排序、插入排序。它们的实现最简单适合小规模数据、教学示范以及作为其他算法的内层辅助。第二个阵营是O(n log n)的进阶排序包含希尔排序、归并排序、快速排序、堆排序。它们利用分治或树结构数据量越大优势越明显是工程中的主力。第三个阵营是线性时间排序包含计数排序、桶排序、基数排序。它们不是通过比较元素大小来排序而是利用数据本身的取值范围、分布规律或位特征以空间换时间但限制条件也最多。1.2 稳定性到底指什么为什么重要判定一个排序算法是否稳定只需要看一个问题如果两个元素的值相等排序前谁在前排序后是否仍然谁在前。如果顺序不变就称该算法是稳定的如果可能变化就是不稳定的。为什么要特别在意稳定性举个实际开发场景你有一张学生成绩表先按总分排序再按班级排序。如果第二次排序算法是不稳定的那么同一班级内部的总分顺序就会被“打乱”而稳定排序能保证第二次排序完成后每个班级内部仍然保留着按总分从高到低的相对顺序。这就是为什么很多数据库索引、多关键字排序场景对稳定性有硬性要求。1.3 一张表记住全部关键参数下面是十种排序算法的核心参数总览建议先通读一遍再逐个看细节。排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)左右取决于增量序列O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(k)稳定桶排序O(n k)O(n²)O(n k)稳定基数排序O(d(n k))O(d(n k))O(n k)稳定其中k表示数据范围或桶的数量d表示最大数字的位数。快排的平均空间复杂度为O(log n)原因是递归栈深度。把这些参数放在一起对比选型和笔试答题时一目了然。2. O(n²)序列冒泡、选择、插入谁才是基础里的王者三个算法都简单但各自的特征和使用场景完全不同。我把它们的代码和易错点一起放上来。2.1 冒泡排序不停交换的“气泡浮升”冒泡排序的核心思想是每一轮都从前往后扫描相邻元素如果前一个比后一个大就交换。一轮扫描结束后最大的元素会像气泡一样“浮”到末尾下一轮继续对剩余部分的n-1个元素进行同样操作。void bubbleSort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { std::swap(arr[j], arr[j 1]); swapped true; } } if (!swapped) { break; } } }这里有一个很容易被忽略的优化点swapped标志位。如果某一轮扫描过程中没有任何交换发生说明整个序列已经有序可以提前终止。这个优化让冒泡排序在“近乎有序”的数据上可以降到O(n)的复杂度。冒泡排序只有在arr[j] arr[j1]时才交换相等元素不会被交换位置所以它是稳定的。时间复杂度方面最坏情况和平均情况都是O(n²)但加了提前退出标志后最好情况是O(n)空间复杂度O(1)。注意冒泡排序在n较小时性能尚可但数据量超过几千就会明显变慢。它在工程中的主要价值只剩教学和简单场景比如面试手写、小规模数据排序。2.2 选择排序每一轮挑出最值放到前面选择排序的思想比冒泡更“直接”每轮找到未排序部分的最小值和未排序部分的第一个元素交换。第i轮结束后前i个元素就是全局最小的i个元素。void selectionSort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } if (minIdx ! i) { std::swap(arr[i], arr[minIdx]); } } }注意代码里的minIdx记录的是最小值下标而不是直接把值交换过来。这样每轮只做一次交换比冒泡排序的频繁交换要省操作。但选择排序的关键问题在于它不是稳定的。举个反例数组[5, 3, 5, 1]第一轮找到最小值1下标为3交换arr[0]和arr[3]后数组变成[1, 3, 5, 5]原本在前面的第一个5已经被挪到了后面两个5的相对顺序还是保持的。但换成[3, 5, 3, 1]第一轮交换后数组变为[1, 5, 3, 3]原本在前面的3被换到后面两个3的相对顺序被破坏了。交换操作会把较远的元素移位所以稳定性不成立。选择排序的时间复杂度无论数据是否有序都是O(n²)空间复杂度O(1)但在数据“已经有序”的输入上没有额外收益。2.3 插入排序像整理扑克牌一样插入排序的处理方式和人手动整理扑克牌完全一致从第二张牌开始取一张牌和前面的牌从右往左比较找到正确位置插入。它只移动比当前元素大的元素不会破坏相等元素的相对顺序。void insertionSort(vectorint arr) { int n arr.size(); for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; --j; } arr[j 1] key; } }我写插入排序时常见的一个误区是把arr[j] key写成。一旦写成相等元素会被提前插入到更前面的位置算法就变得不稳定了。所以稳定性完全取决于比较符号。插入排序的时间复杂度最好的情况是数据几乎有序内层循环基本不执行整体降到O(n)最坏和平均情况是O(n²)。这也是为什么许多高级排序算法会在数据规模很小时或者递归分区后的小数组上改用插入排序——因为小规模下它的常数极小甚至可以超过部分O(n log n)算法。2.4 三个O(n²)算法的横向对比三个基础排序里最值得用的其实是插入排序因为它具备两个优势一是数据基本有序时性能优秀二是稳定。选择排序虽然比较次数少但稳定性差性能也没有比插入排序好冒泡排序除了实现简单其他方面基本没有明显优势。实操心得手写排序题如果允许选任意排序我一般选插入排序或快速排序。插入排序代码冗余度最低不容易写错快排则有“平均最优”的理论口碑但细节多容易在partition边界上踩坑。3. 进阶排序希尔、归并、快排、堆排这部分是笔试和开发中的重头戏每个算法都值得花时间拆解。3.1 希尔排序插入排序的跳跃式增强希尔排序的出发点是插入排序在数据基本有序时效率很高。那么能不能先让数据“大致有序”再逐次缩小增量最终变成插入排序希尔排序正是这样做的设定一个增量gap序列对相隔gap的元素进行插入排序不断缩小gap直到gap为1进行一次标准插入排序。void shellSort(vectorint arr) { int n arr.size(); for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key arr[i]; int j i - gap; while (j 0 arr[j] key) { arr[j gap] arr[j]; j - gap; } arr[j gap] key; } } }上面的写法采用最简单的n/2折半增量序列code里每轮实际上做了gap路并行的插入排序。希尔排序的时间复杂度分析比较繁琐因为取决于gap序列的选取。常用的折半序列平均约为O(n^1.3)某些精心设计的序列可以达到O(n^{3/2})甚至更低但最坏情况仍是O(n²)。空间复杂度O(1)。希尔排序是不稳定的。原因在于相等元素距离gap较远时会被移动到不同批次的插入序列中交换过程可能跨越多个位置相等的两个数可能被“插”到对方前面。记住任何“跳跃交换”型排序稳定性基本都保不住。3.2 归并排序分治思想的经典样板归并排序有两步先把数组对半拆直到每个子区间只有一个元素再不断合并两个有序子区间让上层区间重新有序。这种“先拆后合”的思路是典型的分治法。void merge(vectorint arr, int left, int mid, int right) { vectorint temp(right - left 1); int i left, j mid 1, p 0; while (i mid j right) { if (arr[i] arr[j]) { temp[p] arr[i]; } else { temp[p] arr[j]; } } while (i mid) temp[p] arr[i]; while (j right) temp[p] arr[j]; for (int p 0; p temp.size(); p) { arr[left p] temp[p]; } } void mergeSort(vectorint arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); }合并操作里判断条件必须用也就是当左半部分的元素等于右半部分时优先取左半部分。这是归并排序保持稳定性的关键点。如果写成相等元素就会优先取右侧元素稳定性被破坏。时间复杂度分析每一轮递归合并需要扫描整个数组代价为O(n)递归深度是O(log n)所以整体是O(n log n)。无论是最好、最坏还是平均情况都是O(n log n)这是归并排序最大的优点——不存在快排最坏情况退化的风险。代价是需要额外的O(n)辅助数组。归并排序在解决“链表排序”以及“外部排序”场景时极其有用因为它的数据访问是顺序的不需要随机访问索引天然适合链表结构和磁盘块顺序读。这也是我建议重点掌握它的原因。3.3 快速排序平均最快的随机化版本快排的思想是选一个基准值pivot把数组分成两部分左边都小于pivot右边都大于pivot再对左右两个部分递归地执行同样操作。快速排序的实现方式非常多我推荐使用“挖坑法”或“Lomuto分区”。下面这个版本是用“挖坑法”实现的单次partitionint partition(vectorint arr, int left, int right) { int pivot arr[left]; int i left, j right; while (i j) { while (i j arr[j] pivot) --j; if (i j) arr[i] arr[j]; while (i j arr[i] pivot) i; if (i j) arr[j--] arr[i]; } arr[i] pivot; return i; } void quickSort(vectorint arr, int left, int right) { if (left right) return; int pos partition(arr, left, right); quickSort(arr, left, pos - 1); quickSort(arr, pos 1, right); }这段代码有一个极其关键的细节两个内层while循环里使用的是和确保pivot值相等的元素不会无限交换。另一个细节是在递归前可以加入“小区间插入排序”优化当区间长度小于某个阈值比如16时直接调用插入排序。快排平均时间复杂度为O(n log n)空间复杂度为递归栈深度O(log n)。最坏情况发生在每次选择的pivot恰好是区间最小值或最大值例如对完全有序的数组且每次取最左侧为pivot这时递归深度退化为O(n)总时间为O(n²)。解决最坏退化的常规手段是引入随机化在partition前把区间内随机一个位置和left位置元素交换后再取pivot。稳定性方面快排明显是不稳定的。partition过程会把大量元素跨区间交换等值元素的位置完全无法保证。实操心得手写快排最容易出bug的位置是partition里的边界条件。我见过很多次while (i j arr[j] pivot)和while (i j arr[i] pivot)写反或者忘了在内层加i j导致函数陷入死循环或越界。建议写完后用包含大量重复元素和完全有序数组的测试用例验证。3.4 堆排序利用完全二叉树的结构优势堆排序基于二叉堆结构。以大顶堆为例堆顶元素是最大元素把堆顶和堆尾交换堆大小减一再对新的堆顶做下沉调整。持续交换-调整数组尾部就会逐步形成从大到小的有序区。void heapify(vectorint arr, int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) { largest left; } if (right n arr[right] arr[largest]) { largest right; } if (largest ! i) { std::swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(vectorint arr) { int n arr.size(); for (int i n / 2 - 1; i 0; --i) { heapify(arr, n, i); } for (int i n - 1; i 0; --i) { std::swap(arr[0], arr[i]); heapify(arr, i, 0); } }i n / 2 - 1是从最后一个非叶子节点开始建堆。建堆过程是倒序下沉复杂度分析起来比表面看起来有趣每次heapify都从倒数第二层开始越往上的节点下沉次数越少但需要下沉最远的节点位于较高的层。整体建堆代价为O(n)n次取出堆顶后每次需要O(log n)的下沉总复杂度O(n log n)。堆排序的最坏、平均、最好情况都是O(n log n)空间复杂度O(1)这是它最大的优势适合嵌入式环境或对最坏情况有严格要求的场景。堆排序也是不稳定的。堆顶与堆尾交换等值元素时会大幅度改变它们的位置关系稳定性实在无法保证。3.5 四种进阶排序怎么选如果按工程场景选型规律如下平均性能最优、常数小快速排序。数据随机性好时首选。稳定性有硬要求归并排序代价是额外O(n)内存。内存受限或不允许额外空间堆排序。虽然实际常数可能比快排稍大但最坏情况下依然是O(n log n)。排序链表归并排序因为链表不需要额外移动大量数组元素只需要改指针。4. 线性时间排序计数、桶、基数用空间换时间如果数据范围整齐、分布有规律比较排序的O(n log n)下界其实可以被突破。这三个算法就是不走“比较”这条路。4.1 计数排序统计每个值出现的次数计数排序的原理很简单如果所有数据都是整数且范围在[min, max]内那么统计每个值出现的次数再按从小到大的顺序把值依次“放回”数组即可。void countingSort(vectorint arr) { if (arr.empty()) return; int maxVal *max_element(arr.begin(), arr.end()); int minVal *min_element(arr.begin(), arr.end()); int range maxVal - minVal 1; vectorint count(range, 0); for (int num : arr) { count[num - minVal]; } int idx 0; for (int i 0; i range; i) { while (count[i] 0) { arr[idx] i minVal; count[i]--; } } }上面的实现是“简化版”适合数值范围较小、只需要排序值的场景。但它有一个问题只排序了值丢失了稳定性。如需保持稳定例如对结构体按某个整型字段排序则需要使用“累加计数倒序遍历置位”的标准稳定版本void stableCountingSort(vectorpairint, string arr) { int maxVal 0, minVal INT_MAX; for (auto p : arr) { maxVal max(maxVal, p.first); minVal min(minVal, p.first); } int range maxVal - minVal 1; vectorint count(range, 0); for (auto p : arr) { count[p.first - minVal]; } for (int i 1; i range; i) { count[i] count[i - 1]; } vectorpairint, string output(arr.size()); for (int i arr.size() - 1; i 0; --i) { int key arr[i].first - minVal; output[count[key] - 1] arr[i]; count[key]--; } arr output; }第二段代码的原理是先累加count数组让count[key]表示“小于等于该值的元素个数”然后从原数组末尾倒序遍历每遇到一个元素就把它放到output的指定位置同时把对应计数值减一。倒序遍历保证了后面出现的等值元素先放在较后的位置从而维持原来的相对顺序。计数排序的时间复杂度是O(n k)k是range大小空间复杂度O(k)。需要注意如果k远大于n比如n100但值范围是0到10亿这个算法就不适用了。4.2 桶排序把数据分进多个桶再排桶排序假设数据在某个范围内均匀分布把范围切成若干个桶遍历一遍数据把元素分到对应的桶中每个桶再用插入排序或其他方法单独排序最后按桶顺序合并。void bucketSort(vectorfloat arr) { if (arr.empty()) return; int n arr.size(); vectorvectorfloat buckets(n); for (float num : arr) { int idx num * n; if (idx n) idx n - 1; buckets[idx].push_back(num); } for (auto bucket : buckets) { std::sort(bucket.begin(), bucket.end()); } int idx 0; for (auto bucket : buckets) { for (float num : bucket) { arr[idx] num; } } }上面的代码适用于[0,1)区间均匀分布的浮点数。桶的数量和映射规则必须根据数据分布定制这是桶排序的核心难点如果数据分布严重不均匀某些桶中元素数量会很大排序复杂度就会退化。最坏情况下所有数据都进同一个桶桶内排序复杂度就是O(n²)。平均情况下每个桶中的元素数量近似n/k总复杂度为O(n k)空间复杂度O(n k)。桶排序在一个合理的范围内是稳定的取决于桶内使用的排序算法是否稳定以及桶合并时是否保持顺序。只要桶内排序用稳定算法且按桶顺序合并它就是稳定排序。实操心得桶排序写起来不复杂真正需要花心思的是“界定桶的边界”。比如排序一组年龄数据18-60岁可以直接把18到60映射成43个桶但如果是排序压缩图片的像素值桶数就要根据灰度范围重新设计。桶排序不是一个“固定代码”更像一种分治策略。4.3 基数排序按位分批处理基数排序的思路是按数字的每一位从低到高或从高到低依次排序。如果每一位都使用稳定的计数排序作为内部排序那么低位排完之后高位排的时候会保留低位的有序性最终整体有序。void radixSort(vectorint arr) { int maxVal *max_element(arr.begin(), arr.end()); int exp 1; while (maxVal / exp 0) { countingSortByDigit(arr, exp); exp * 10; } } void countingSortByDigit(vectorint arr, int exp) { vectorint count(10, 0); for (int num : arr) { int digit (num / exp) % 10; count[digit]; } for (int i 1; i 10; i) { count[i] count[i - 1]; } vectorint output(arr.size()); for (int i arr.size() - 1; i 0; --i) { int digit (arr[i] / exp) % 10; output[count[digit] - 1] arr[i]; count[digit]--; } arr output; }这里必须强调基数排序内部依赖的count过程必须是稳定的倒序遍历put回output是关键这正是上一小节“稳定版计数排序”的思路。基数排序的时间复杂度是O(d(n k))其中d是最大数字的位数k10为每一位可能的取值数量。空间复杂度O(n k)。基数排序对固定长度的数字类型如int、long效果不错但由于现代处理器的分支和内存访问成本实际运行效率并不一定比快排高。另外它不能直接排序负数需要做偏移处理先把所有数字加上最小值的绝对值排完再减回去。4.4 线性排序的适用边界线性排序是否比O(n log n)更快取决于k相对于n的大小。当值域大而数据量小时如n1000而数字范围是0到20亿计数排序完全不可用当n很大但值域很小时如排序全校几万名学生的年纪范围只有几十计数排序是绝佳选择。桶排序则适合处理均匀分布的浮点数据基数排序适合等宽整数序列。5. 工程实战C里怎么选排序以及避坑经验写完手写排序之后更重要的是知道在真实项目里怎么选现成的排序能力。5.1 系统自带sort、stable_sort内部机制实际开发中不要重复造轮子。C标准库提供了std::sort、std::stable_sort和std::partial_sort它们通常混用了多种排序策略。std::sort在数据量较大时使用快速排序的变体在元素较少或分区小于某一阈值时切换到插入排序在递归深度过深时会切换到堆排序防止退化。这些细节标准没有强制规定但对大多数实现而言“快排插入排序堆排”的组合已经非常稳健。std::stable_sort表面上看是归并排序的包装实际上实现时往往使用“分块插入排序归并”的混合策略在空间充足时使用O(n)额外空间空间不足时退化为O(n log² n)或更复杂的原地归并方案。实操心得如果只是给vector排序直接用std::sort(v.begin(), v.end())即可如果要保持相等元素的原始顺序必须用std::stable_sort。我看到不少项目为了“稳定”把std::sort替换成手写排序完全没必要标准库的稳定版本已经足够成熟。5.2 稳定性是“严重”还是“锦上添花”多重排序实战稳定性只有在进行“多重排序”时才真正体现价值。假设需要先按用户等级降序排列再按注册时间升序排列。正确做法是使用稳定排序先按注册时间排一次再按等级排序因为第二次排序不会打乱注册时间的关系。如果使用不稳定排序就必须把两个字段打包成一个复合比较函数在单次排序中完成。这时复合比较函数才是更稳妥的方案。vectorUser users; std::sort(users.begin(), users.end(), [](const User a, const User b) { if (a.level ! b.level) return a.level b.level; return a.registerTime b.registerTime; });所以在工程里我更推荐直接用复合比较函数替代对稳定性的依赖。稳定性更多是算法知识层面的要求而不是所有场景都用得上。5.3 大数据量场景的取舍与实测建议当数据量超过几百万时内存访问模式比时间复杂度更影响真实速度。快速排序虽然平均复杂度在三种O(n log n)算法中不算最优但它的局部性较好缓存命中率高实际表现通常优于堆排序。归并排序需要额外的内存分配与复制在大数组中会被内存带宽限制运行时间往往高于快排。建议用随机数据集、有序数据集、重复元素数据集分别测试不要只依赖理论复杂度下结论。6. 常见问题与排查技巧实录结合我实际写排序和带团队时遇到的坑这里汇总几个高频问题。6.1 快速排序栈溢出递归快排处理百万级有序数组时如果partition选到的pivot总是极端值递归深度达到O(n)很容易栈溢出。解决办法有三个一是用随机pivot降低最坏情况概率二是递归时先处理短区间再处理长区间强制把最坏递归深度限制在O(log n)级别三是数据量大时改用std::sort内部实现已经做过深度保护。6.2 计数排序负数与数据范围问题直接拿arr[i]作为count下标处理负数是行不通的。处理办法是先遍历一遍数组获取min和max把所有元素映射到value - min后再统计。另一方面要警惕range过大导致内存爆炸例如排序10个int且值域达到2³¹这时不能使用计数排序。6.3 桶排序桶内排序选择桶排序里的每个桶用std::sort处理是最省事的。但如果你在写一个对性能要求极高的模块而且桶内数据近似均匀且元素数量很少用插入排序反而更快因为插入排序常数极小。记住不要为了“高级”盲目选择复杂算法桶内排序选择insertion并不是矛盾的事。6.4 用断言和随机测试来验证排序正确性写完一个排序算法不要只看少量用例。我习惯写一个测试函数生成随机数组先用std::sort得到基准答案再用自写排序得到结果逐元素对比同时额外生成大量重复元素的数组来测试稳定性。这个流程能暴露绝大多数边界问题。以下是简化的验证思路bool isValid(vectorint data, const vectorint expected) { if (data.size() ! expected.size()) return false; for (size_t i 0; i data.size(); i) { if (data[i] ! expected[i]) return false; } return true; }稳定性验证可以借助pair结构给每个元素附带原始下标排序后检查等值元素的下标是否递增。这个测试非常重要因为很多排序算法的“不稳定”问题只有在重复元素较多的场景才会暴露。6.5 性能对比的注意点做性能对比时要防止编译器优化掉排序函数。实际测试中建议传入不恒定的随机数列并把排序结果累加到一个volatile全局变量避免编译器“看穿”结果后直接把排序代码删掉。数据量级至少准备一万、十万、一百万三档每档跑多轮取中位数。只跑一两轮受系统调度影响很大无法反映稳定性能。我个人在实际操作中的体会是排序算法不能只背代码一定要动手实现每一版再用随机用例做正确性校验。十个算法写一遍的时间不超过两小时但带来的理解深度远超看十遍。后续如果继续深入可以研究并行排序、稳定快排的原地实现或者把排序知识迁移到拓扑排序、K路归并这些扩展方向上。