1. 二维数组为啥不能直接套一维排序模板先认清内存布局这问题我接过不少次几乎每次都是从同一个困惑开始的一维数组的qsort或者std::sort明明写得好好的换成二维数组就报错、乱序、编译不过或者排出来只有第一行变了后面的行根本不动。先说结论二维数组在许多语言里不是一个数组这么简单它可能是数组的数组C/C 的int a[3][4]、Python 的嵌套列表也可能是一块连续内存C 语言严格意义下的二维数组本质上是连续存放的还可能是一个装着好几个列表的容器std::vectorstd::vectorint。你用什么方式定义它决定了排序时交换一次到底交换了什么。1.1 二维数组的两种面貌连续内存 vs 嵌套容器C 语言里写int a[3][4]这 12 个 int 在内存里是紧紧挨着的就像一个拉平的一维数组。所以理论上你甚至可以把a强转成int*再用一维排序的思路处理。很多教材不提这件事导致不少初学者以为二维数组就一定是三行四列的逻辑表格忘了底层是连续内存。C 里写std::vectorstd::vectorint情况就完全不同了。外层 vector 存了三个内层 vector 的指针每个内层 vector 自己又单独在堆上申请一块连续内存。也就是说三行数据可能分散在内存的不同角落压根不连续。这时候你没法把整个二维 vector 当一段连续内存去排序只能把每一行当成一个整体元素来交换。这两种不同的内存布局直接决定了排序代码长什么样。C 语言里你可以让qsort把一整行比如 3 个 int、12 个字节当作基本单元交换C 里你只能通过容器的迭代器和比较器来告诉排序算法这一行怎么和下一行比大小。这也是为什么后面要反复强调重定义大小比较符号——因为排序算法只知道怎么比较单个整数不知道你要拿哪一列、哪条规则来比较两个行。1.2 排序的本质比较加上交换规则由你定义任何基于比较的排序扒掉外壳就两步比较两个元素的先后顺序决定是否交换位置。快速排序、归并排序、堆排序底层都是这么干的。一维数组排序时a[i] a[j]这种比较规则是语言内置的但二维数组的元素是一行语言并不知道两行之间怎么算谁大谁小。是按第一列比按最后一列比还是按整行总和比这都得你说了算。重定义大小比较符号这句话在 C/C 语境里翻译过来就是给排序算法提供一个自定义的比较函数C 语言用函数指针C 用 lambda 或者重载operator告诉它按什么规则判断先后。你说得越清楚排序结果越符合预期你说不清楚编译器就用默认规则猜通常要么编译报错要么排出来的结果根本不是你要的。我对初学者的建议永远是**先写比较规则再写排序调用。**不少人一上来就写qsort(arr, rows, cols*sizeof(int), cmp)结果 cmp 没写或者写到一半忘了返回值的含义。先把比较函数单独写好、单独测试确认它能让两个元素正确分出先后再塞进排序函数里十个有九个坑都能提前躲过去。2. 重定义大小比较符号到底在定义什么从C语言函数指针到C运算符重载这是整个标题里水分最大、也最容易理解偏的一句。重定义大小比较符号在 C 里可能指重载operator在 C 语言里其实只是写一个比较回调函数在 Python 里是传入key参数。你得先搞明白每种语言里自定义比较的真实机制才不会被qsort返回值和std::sort的 comp 参数搞晕。2.1 C语言里没有运算符重载但有函数指针比较器先说 C 语言的qsort卖相难看但概念最干净。函数原型长这样void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));四个参数首地址、元素个数、每个元素占多少字节、比较函数。重点是最后一个它要求你传一个函数指针这个函数接收两个const void*返回一个 int。返回值的约定是返回负数第一个参数排在第二个前面返回 0两个参数相等谁前谁后无所谓返回正数第一个参数排在第二个后面很多人把这个背反了我提供一个记忆方式你写的数组从小到大排if (a b) return -1;就是升序if (a b) return -1;就是降序。也就是说你脑子里想的是我希望哪个元素排在前面就在 a 和 b 的对应关系里让那个元素当第一个参数、并且返回负数。举一个最典型的例子二维数组按第一列降序排序#include stdio.h #include stdlib.h #define ROWS 5 #define COLS 3 // 按第一列降序比较两个行 int cmp_by_col0_desc(const void *pa, const void *pb) { const int *rowA (const int *)pa; const int *rowB (const int *)pb; if (rowA[0] rowB[0]) return 1; // a 第一列小但我们要降序所以让 a 往后排 if (rowA[0] rowB[0]) return -1; // a 第一列大降序要让 a 往前排 return 0; } int main(void) { int arr[ROWS][COLS] { {12, 5, 7}, {3, 9, 1}, {20, 2, 8}, {5, 11, 6}, {14, 4, 10} }; qsort(arr, ROWS, COLS * sizeof(int), cmp_by_col0_desc); for (int i 0; i ROWS; i) { for (int j 0; j COLS; j) { printf(%4d, arr[i][j]); } printf(\n); } return 0; }这段代码里容易迷糊的点就一个qsort第三个参数为什么要传COLS * sizeof(int)因为排序交换的基本单元是一整行。qsort不知道你处理的是二维数组它只知道每个元素占 12 个字节交换时按 12 字节整体搬动。这也解释了为什么 C 语言的二维数组能直接扔给qsort而不用自己做下标换算——内存连续base指向首地址size给对一切就顺了。2.2 C 的运算符重载你真的把重新定义了C 的std::sort默认用。对内置类型没问题int天生知道怎么比大小。但vectorvectorint没有定义运算符直接写sort(v.begin(), v.end())编译器会报一堆模板错误中心意思就一句话不知道怎么比较。解法之一是给自定义结构体重载operator这正是标题里重定义大小比较符号最字面的含义。比如#include bits/stdc.h using namespace std; struct Row { int data[3]; // 重定义小于号按第二列比较升序 bool operator(const Row other) const { return data[1] other.data[1]; } }; int main() { Row rows[5] { {12, 5, 7}, {3, 9, 1}, {20, 2, 8}, {5, 11, 6}, {14, 4, 10} }; sort(rows, rows 5); for (const auto r : rows) { cout r.data[0] r.data[1] r.data[2] \n; } return 0; }注意这里sort用的是数组形式rows 5相当于迭代器范围。重载了operator之后std::sort内部比较两个Row时就会调用你的规则。想改成降序也不难把operator里换成data[1] other.data[1]。但我得提醒你重载operator后这个结构体的语义就变了以后任何地方对Row做、sort、set这类操作都会继承这套规则。如果你只是想用一次排序代价有点大现代 C 更推荐用 lambda。2.3 现代 C 的正解lambda 比较器一行搞定降序如果是容器我几乎不推荐为它重载运算符而是直接用std::sort的第三个参数传 lambda#include bits/stdc.h using namespace std; int main() { vectorvectorint v { {12, 5, 7}, {3, 9, 1}, {20, 2, 8}, {5, 11, 6}, {14, 4, 10} }; int col 1; // 按第二列降序 sort(v.begin(), v.end(), [col](const vectorint a, const vectorint b) { return a[col] b[col]; }); for (const auto row : v) { for (int x : row) cout x ; cout \n; } return 0; }lambda 的参数就是两个行的引用函数体里写a[col] b[col]意思是我们判断 a 是否应该排在 b 前面条件是 a 的第 col 列比 b 的第 col 列大。这个规则正好把大数往前提实现了降序。如果你想要升序把改成就行。这里要理解一个关键点std::sort的比较器返回的是bool语义是第一个参数是否应该排在第二个之前和 C 语言的int三态返回不一样。很多人从 C 转 C 时会把习惯带过来写一个返回 -1、0、1 的比较函数想传给std::sort这是不行的——C 的 comp 只回答 yes/no不需要、也不应该返回三态数值。3. 三种真实场景按列排、行内排、按总和排代码逐个给到理论说完了上实战。我选了三个出现频率最高的场景按列降序、每行内部降序、按整行总和自定义排序。前两个写 C 版本第三个写 C 语言版本顺便演示不同内存模型下的不同写法。3.1 场景一按某一列降序整行跟着走这是学生成绩表、排行榜最常见的需求第一列是学号第二列是分数你想按分数从高到低排但每行数据不能拆散。实现思路就是让比较器只盯着指定的那一列然后让排序算法把整行当成一个整体交换。#include bits/stdc.h using namespace std; int main() { vectorvectorint scores { {101, 85, 76}, {102, 92, 81}, {103, 67, 90}, {104, 78, 72}, {105, 95, 88} }; // 按第二列下标1降序 int sortCol 1; sort(scores.begin(), scores.end(), [sortCol](const vectorint left, const vectorint right) { return left[sortCol] right[sortCol]; }); cout 按第二列降序\n; for (const auto stu : scores) { cout 学号 stu[0] 分数 stu[1] 平时分 stu[2] \n; } return 0; }跑出来的顺序会是105、102、101、104、103。每行跟着排序索引走没有把列拆散。如果你希望分数相同时再按学号升序作为次级规则也很简单if (left[sortCol] ! right[sortCol]) return left[sortCol] right[sortCol]; return left[0] right[0]; // 分数相同学号小的在前这种主规则 次规则的写法在实际业务里非常常用基本取代了踩坑的先排一次再排一次做法。3.2 场景二每一行内部做降序排序这个需求说起来更简单二维数组有 n 行每行有 m 个数字希望每一行从大到小排好但行与行之间的顺序不动。有人会想着再套一层什么高级操作其实就是一个循环#include bits/stdc.h using namespace std; int main() { vectorvectorint v { {3, 9, 1, 7}, {12, 5, 8, 2}, {6, 4, 11, 3} }; for (auto row : v) { sort(row.begin(), row.end(), greaterint()); } for (const auto row : v) { for (int x : row) cout x ; cout \n; } return 0; }greaterint()是标准库自带的一个函数对象作用就是让排序按降序执行。你也可以写成 lambda[](int a, int b) { return a b; }效果一样。这个小需求没什么难度但往往藏着另一个问题如果你想按照每一行的最大值来给整行排序比如哪一行的最大值大哪一行就排在前面那又是另一个比较规则了。这种情况要放到场景三里做。3.3 场景三按整行总和排序C语言完整实践有些业务会要求按权重求和后降序比如每行是三次实验的数据最终按三次实验之和排名。用 C 语言实现就得在比较函数里把两个行指针拿出来逐列累加再比较#include stdio.h #include stdlib.h #define ROWS 5 #define COLS 3 int cmp_by_sum_desc(const void *pa, const void *pb) { const int *rowA (const int *)pa; const int *rowB (const int *)pb; int sumA rowA[0] rowA[1] rowA[2]; int sumB rowB[0] rowB[1] rowB[2]; if (sumA sumB) return -1; // 降序总和大的往前 if (sumA sumB) return 1; return 0; } int main(void) { int arr[ROWS][COLS] { {3, 9, 1}, {12, 5, 2}, {6, 4, 11}, {7, 8, 3}, {1, 2, 20} }; qsort(arr, ROWS, COLS * sizeof(int), cmp_by_sum_desc); for (int i 0; i ROWS; i) { printf(第%d行: %d %d %d %d\n, i, arr[i][0], arr[i][1], arr[i][2], arr[i][0] arr[i][1] arr[i][2]); } return 0; }输出顺序中最后一行{1, 2, 20}总和 23 排第一{6, 4, 11}总和 21 排第二。这里比较函数完全没管行号概念只知道自己在比较两个未知数据块的首地址用const int*强转后按列取值。这种自由度就是 C 语言 qsort 的核心魅力排序算法只负责比较和交换具体业务规则全塞在比较函数里。4. 容易翻车的边界条件指针退化、严格弱序、稳定性标题里带了很简单但实际动手时最容易让人崩溃的反而不是主要逻辑而是几个边角问题。它们不解决代码要么编译不过要么运行结果无规律。我把这两年答疑中高频出现的坑集中列一下。4.1 二维数组参数传递的降维打击指针退化C/C 里把二维数组传给函数时第一维会退化成指针。比如void sort_matrix(int arr[][3], int rows);看起来像是传了一个二维数组实际上等价于void sort_matrix(int (*arr)[3], int rows);arr是一个指向含 3 个 int 数组的指针。很多初学者在这里卡住在函数内部用arr[i][j]访问没问题但一旦想把arr传给qsortsizeof 就算错了。sizeof(arr)不再是整个二维数组的大小而是int (*)[3]这个指针的大小通常是 8 字节。此时再按原来的行数乘列数去算 qsort 参数结果必然崩。正确做法是在函数外面或者提前算好把总字节数交给 qsort或者在函数里重新从rows和COLS推导。如果你用的是std::vector这个问题就自动消失了因为 vector 自己知道 sizev.size()随时可取。这也是我为什么建议 C 新手优先用 vector 做二维数组练习——先把逻辑跑通再回头啃指针。4.2 比较器必须满足严格弱序否则排序结果未定义这是 STL 排序里相当重要又极少被提到的规则。你的比较函数无论叫 cmp 也好、lambda 也罢必须一致地回答谁在前这个问题。具体要求包括任何一个元素和自身比较必须返回 falsecomp(a, a)为 false如果comp(a, b)为 true那么comp(b, a)必须为 false传递性不能被破坏a 比 b 靠前b 比 c 靠前则 a 必须比 c 靠前违反这些规则的后果很隐蔽排序结果可能乱序极端情况下程序直接崩。最常见的错误是把当作比较器传进去sort(v.begin(), v.end(), [](int a, int b) { return a b; });这句的逻辑错误在于a 和 b 相等时返回 trueb 和 a 相等时也返回 true两个方向都成立谁在谁前面自相矛盾。编译器不会报错但排序结果完全不可预期。正确的写法和 C 语言类似降序就用a b升序就用a b不要加等号。等值元素之间的先后顺序由排序算法的稳定性决定不由比较器决定。4.3 稳定性没搞懂二次排序越排越乱稳定这个概念在面试里常考在工程里也踩过不少坑。如果排序算法是稳定的那么两个元素在比较规则下相等时它们的相对顺序会保持原样。也就是说你先按第一列升序排一次再按第二列升序排一次第二列相等的一组内部依然保持着第一列的升序关系。std::sort不保证稳定std::stable_sort保证稳定。C 语言自带的qsort也不保证稳定。所以先按辅助列排再按主列排这种复合排序在std::sort和qsort下都可能得出意外的顺序。我的建议是**不要依赖两次排序实现多级排序直接在比较器里写下级规则。**如果横向排序稳定性对你有用就用stable_sort但要注意它通常比sort慢数据量大时要评估一下。另外提醒一下 qsort 的另一个性格它底层是快速排序的实现变体最坏情况时间复杂度是 O(n²)。虽然标准库实现通常会做优化避免最坏输入但如果你处理的是上千万行的数据还是优先考虑 C 的std::sort内省排序最坏也是 O(n log n)或者自己实现稳定的归并排序。二维数组自定义排序这件事拆开看其实就三个知识点知道二维数组在内存里长什么样会写比较函数或者 lambda记住排序算法对比较器的一些底层要求。我把上面内容按先理解内存 → 再写比较规则 → 再落代码 → 最后处理边界的顺序过一遍确实也就这些了。2025年7月整理这版笔记时我顺手把常见的几种写法都跑了一遍包括 C 的 qsort、C 的 sort 加 lambda、结构体运算符重载最后自己都感叹一句排序本身确实很简单复杂的是你如何跟语言解释谁大谁小。如果你也是初学者建议先动手写场景一那个按列降序的例子把它改造成按第三列排、按最大值排跑通了这块内容就算真正吃透了。