多数组排序的三种思路：冒泡、sort自定义比较器与栈

做在线评测题的时候，看到“7-1 多数组排序（12分）”这样的题目，我的第一反应不是马上写代码，而是先问自己三件事：数据规模有多大、输出顺序有没有特殊要求、题目允不允许直接调用排序函数。这个题目很有意思，它把“多数组排序”和“三种做法”写在标题里：冒泡排序、重写sort方法、利用sort和栈。三种做法不是同一段代码换三件马甲，而是代表了三种完全不同的思路层次。

这篇博客我按自己刷题时的真实习惯来写。题目原文没有完整贴出来，我按常见版本理解：输入 n 行 m 列整数，先把每一行内部排序，再把行与行按输入顺序倒序输出。如果你的原题只是要求每组正序输出，那第三种做法里的栈可以直接去掉，前两种做法连输出部分都不用改。如果你刚开始学数据结构，或者准备机考，建议把三种做法都看一遍，它们正好覆盖了“手写基础算法、调用标准库、利用数据结构辅助排序”三个阶段。

1. 先搞清楚“多数组排序”到底想考什么

1.1 题目本质：多个一维数组，而不是一个二维数组

很多初学者看到“多数组”三个字，下意识认为把 n 行数据全部塞进一个 vector，然后整体 sort 一遍就完成了。这是最典型的错误。多数组排序的核心是“组内独立排序，组间可能还要重排”。每一行数据是一个最小处理单元，n 行数据就是 n 个独立的一维数组。

举个例子，输入两行：

2 1 4 3

如果整体排序，输出是 1 2 3 4，但题目如果要求每行分别升序，输出应该是：

1 2 3 4

多数组排序题之所以分值不高（比如这里的 12 分），往往是因为基础操作本身不难，但细节很多。你要处理二维数组的读入、每行排序、行间顺序调整、输出格式控制。最容易被扣分的点不是算法不会，而是行尾多一个空格、逆序方向写反、栈用错了时机。这些我会在后面的问题排查部分单独列出来。

1.2 三种做法对应三种解题境界

第一种做法，冒泡排序，完全不依赖任何库函数，适合课程要求“必须手写排序”的场景。它的时间复杂度是 O(n * m^2)，其中 n 是行数，m 是每行的元素个数。数据量小的时候无所谓，数据量一大就非常吃亏。

第二种做法，重写 sort 方法，本质是使用标准库的 std::sort，但自己写比较函数。很多人觉得 sort 就是默认升序，没什么可讲的。实际上“重写”两个字才是重点：默认排序只能解决最简单的情况，一旦要求按自定义字段排序、按多个关键字排序，你必须学会重写比较规则。

第三种做法，利用 sort 和栈，是把标准库排序和数据结构栈结合起来。sort 负责快速完成组内排序，栈负责处理输出顺序。后进先出这种特性非常适合“反序输出”的需求。如果你遇到的要求不是倒序，而是“先处理完所有行之后再统一输出”，栈同样是一个很顺手的缓存结构。

1.3 输入输出格式先对齐，后续代码才好看懂

我这里定一个统一的样例，后面三种做法全部围绕这个样例实现，方便对照。

输入：

3 4 4 3 2 1 8 6 7 5 12 10 11 9

输出：

9 10 11 12 5 6 7 8 1 2 3 4

解释一下规则：第一行输入 3 4，表示有 3 组数据，每组 4 个数。后面三行是原始数据。每个组内部先升序排列，然后组与组之间按照输入顺序倒序输出。因为输入顺序是“4 3 2 1”行、“8 6 7 5”行、“12 10 11 9”行，倒序输出就是第三行先输出，第二行次之，第一行最后。这三行内部排序之后正好是输出样例的顺序。

2. 做法一：冒泡排序，慢但能帮你建立排序直觉

2.1 都什么年代了，为什么还要手写冒泡

你可能会说，工程里不会有人用冒泡排序。确实不会，生产环境直接上 std::sort 更高效。但刷题和考试不一样，很多课程实验要求不能调用库函数，这时候你只能自己写。另外，冒泡排序是理解“交换排序”思想最直接的方式：每一趟从头到尾比较相邻元素，如果顺序不对就交换，一趟下来最大值沉到末尾。

对于多数组排序，冒泡排序的定位就是把每一行当作一个独立的一维数组，逐个调用自己写的排序函数。它的优点是逻辑简单，不容易写错；缺点是慢。不过 12 分的题目数据规模通常很小，n 和 m 在 100 以内时，O(n * m^2) 的复杂度完全没问题。

2.2 完整 C++ 代码：冒泡排序每行，再逆序输出每组

先看代码，后面我再详细讲为什么这样写能过。

#include <iostream> #include <vector> using namespace std; void bubbleSort(vector<int>& 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]) { swap(arr[j], arr[j + 1]); swapped = true; } } if (!swapped) { break; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin >> n >> m) { if (n == 0 && m == 0) break; vector<vector<int>> rows(n, vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> rows[i][j]; } } for (int i = 0; i < n; i++) { bubbleSort(rows[i]); } for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < m; j++) { if (j > 0) cout << ' '; cout << rows[i][j]; } cout << '\n'; } } return 0; }

核心逻辑非常直白：先用 vector 把整个二维数据存下来，然后对每一行调用 bubbleSort，排序完成之后用倒序的 for 循环从最后一行往前输出。输出的时候用 j > 0 判断是否是行内第一个数，避免行尾出现多余空格。

2.3 冒泡排序的几个容易被忽略的细节

第一个细节，内层循环的边界是 n - 1 - i。第 i 趟排序结束后，末尾的 i 个元素已经就位，不需要再比较。如果你写成 n - 1，虽然结果可能也对，但多了很多无效比较。第二个细节，我加了一个 swapped 标志位。如果某趟从头到尾没有任何交换，说明数组已经有序，直接跳出外层循环。这个优化在近乎有序的数据上能大幅减少时间。第三个细节，函数参数用的是vector<int>&引用。如果不加引用，传值会复制整个数组，排序结果不会带出来，白白浪费 O(m) 空间和时间。

输出部分也有讲究。题目要求组间倒序输出，所以我直接从第 n - 1 行开始往回遍历。也可以用 reverse 函数把行顺序翻转之后正序输出，但那样多一次 O(n) 的复制操作，没必要。

3. 做法二：重写 sort 方法，把自定义比较器玩明白

3.1 这里的“重写”到底是什么意思

“重写 sort 方法”不是让你自己再造一个排序算法，而是重写 sort 的比较规则。C++ 标准库的 std::sort 默认按升序排序，用的是operator<。但当你要实现降序、按某一行某个字段排序、按输入序号倒序排序时，默认规则就不够了。

std::sort 的第三个参数可以传函数指针、函数对象或 lambda 表达式。这个参数就是“重写”的地方。它的作用不是替代排序，而是告诉 sort：两个元素比较时，谁该排在前面。理解了这一点，你就能应对绝大多数排序变形题。

3.2 自定义比较器的核心：严格弱序

写比较器有一条铁律：它必须满足严格弱序。通俗讲就是，对于任意两个元素 a 和 b，如果compare(a, b)返回 true，意思是 a 排在 b 前面；如果compare(b, a)返回 true，意思是 b 排在 a 前面；如果两者都返回 false，则认为它们等价，顺序无所谓。

最容易犯的错误是写成return a.idx <= b.idx。这里的问题在于，当 a.idx 等于 b.idx 时，两个方向都会返回 true，破坏了严格弱序，可能导致 sort 出现未定义行为，轻则顺序异常，重则程序崩溃。正确的写法永远是用小于号，比如return a.idx < b.idx，或者降序用大于号return a.idx > b.idx。

3.3 完整代码：sort 每行，再用自定义比较器做行间倒序

#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Row { vector<int> data; int idx; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin >> n >> m) { if (n == 0 && m == 0) break; vector<Row> rows; rows.reserve(n); for (int i = 0; i < n; i++) { vector<int> tmp(m); for (int j = 0; j < m; j++) { cin >> tmp[j]; } sort(tmp.begin(), tmp.end()); rows.push_back({tmp, i}); } sort(rows.begin(), rows.end(), [](const Row& a, const Row& b) { return a.idx > b.idx; }); for (auto& r : rows) { for (int j = 0; j < m; j++) { if (j > 0) cout << ' '; cout << r.data[j]; } cout << '\n'; } } return 0; }

这段代码的思路比冒泡先进在哪？组内排序直接用 sort，一行一个 sort，O(m log m) 就完成了，不用自己写嵌套循环。组间排序再把所有 Row 结构体看作一个整体，用比较器按 idx 倒序排序。这里我故意把 idx 存进结构体，就是为了保留“输入顺序”这个信息，否则排序完的数组行无法还原它原本在第几行。

3.4 进阶：如果题目要求按最大值、最小值或总和排序

比较器最大的优势是灵活。要求按每组最大值升序输出，可以这样写：

sort(rows.begin(), rows.end(), [](const Row& a, const Row& b) { return a.data.back() < b.data.back(); });

因为组内已经升序，最后一个元素就是最大值。要求按每组总和降序输出，可以这样写：

sort(rows.begin(), rows.end(), [](const Row& a, const Row& b) { int sumA = 0, sumB = 0; for (int x : a.data) sumA += x; for (int x : b.data) sumB += x; return sumA > sumB; });

但要注意，如果比较器里每次都比较总和，而 n 比较大，这个总量会变成 O(n^2 log n)。更好的做法是在读入时先计算好 sumA，存在 Row 结构体里，比较器直接比较两个成员变量。这个优化思维在真实项目中尤为重要：不要在排序比较器里做重复且昂贵的计算。

4. 做法三：利用 sort 和栈，正着排，反着出

4.1 栈在这道题里到底“多”用在哪

第三种做法的关键词是栈。题目要求组内升序、组间倒序输出。正着排好每一行后，如果直接输出，行顺序还是原来的。为了让行顺序倒过来，你需要一个“后进先出”的容器把所有行缓存起来：先到的行先入栈，后到的行后入栈。当所有行都处理完后，依次 pop 并输出，pop 出来的顺序恰好就是入栈顺序的逆序。

这就是栈的价值。没有栈的话，你得手动从最后一组往前遍历，或者先翻转行顺序。用栈之后，代码结构非常统一：读一行、排一行、入栈一行。所有行读完后，循环 pop 输出。这个模式很常见，它把“先处理完所有输入，再统一输出”的需求变成了一套固定套路。

4.2 完整代码：sort 负责内部排序，stack 负责输出顺序

#include <iostream> #include <vector> #include <algorithm> #include <stack> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin >> n >> m) { if (n == 0 && m == 0) break; stack<vector<int>> st; for (int i = 0; i < n; i++) { vector<int> v(m); for (int j = 0; j < m; j++) { cin >> v[j]; } sort(v.begin(), v.end()); st.push(v); } while (!st.empty()) { vector<int> v = st.top(); st.pop(); for (int j = 0; j < m; j++) { if (j > 0) cout << ' '; cout << v[j]; } cout << '\n'; } } return 0; }

这段代码每次读入一行，立刻 sort，然后 push 到栈里。等 n 行全部处理完，栈顶自然是最后一行，第一次 pop 输出的就是最后一行排序后的结果。一直 pop 到栈空，输出顺序正好与输入顺序相反。

4.3 sort 和栈还能配合做什么

栈在排序里的应用远远不止倒序输出。一个非常经典的例子是用栈模拟递归快速排序的核心流程：递归快排本质上靠系统调用栈保存左右子区间，你可以显式地用一个 stack 保存待排序区间 [left, right]，每次弹出区间，用 partition 分区，再把新产生的左右区间压入栈。这样就把递归写成了迭代，避免了栈溢出风险。

另一个例子是单调栈。先 sort 把数据排好，再用单调栈处理“下一个更大元素”之类的问题。比如在一个排序后的数组上，想要快速找出每个元素右侧第一个比它大的元素，单纯 sort 帮不上忙，但结合单调栈就能在线性时间内完成。这些组合技巧在面试和竞赛中经常出现，所以不要觉得 sort 和栈放在一起是题目故意刁难，它其实是在提醒你数据结构不是孤立存在的。

5. 常见错误与调试实录

5.1 问题速查表：错误、原因、解决方案

我把刷这类题时比较高频的问题整理成表格，你可以直接保存下来对照检查。

5.2 我踩过的坑：输入读取、输出格式、比较器

我第一次写这道题的时候，犯过一个非常低级的错误：直接用sort(rows.begin(), rows.end())对整个二维数组排序。这样会把所有行按整体字典序排列，而不是每行独立排序。排出来的结果在数据不规律时完全不是题目要的。从那以后，我养成了一个习惯：先问自己“排序的最小单元是哪一维”，再动手写代码。

另一个坑是输出格式。在线评测系统比对字符串时，行尾多一个空格也算错。我刚开始经常写cout << v[j] << " "，结果最后总会多一个空格。后来我统一改成“第一个元素前面什么都不输出，后面的元素前面输出一个空格”，也就是if (j > 0) cout << ' ';。这个写法在任何题目里都不会错。

第三个坑是自定义比较器。很多人会写return a.idx <= b.idx;，以为多一个等号无所谓。实际上这会导致严格的排序关系被破坏。C++ 标准要求比较器是严格弱序，违反后 sort 的行为是未定义的。我在本地测试小数据看不出问题，一到大数据就随机崩溃，排查了很久才找到原因。

5.3 一个 12 分题的性价比分析

如果你在考试或机考现场看到这道题，我建议至少会用第二种做法。它代码短、性能好、不容易出错。冒泡适合课程要求，但如果你只是为了拿分，没必要在 12 分题上花时间去写一个 O(n^2) 的排序。第三种做法略偏数据结构，适合题目明确考察栈的场合。

三种做法的复杂度对比：

注意这里的额外空间复杂度描述是针对组间顺序处理的辅助空间。冒泡那行没有额外存组间顺序，所以是 O(1)；sort 比较器需要存 Row 结构体，所以有 O(n) 量级的额外空间；栈做法把每一行的 vector 全部压栈，所以是 O(n * m)。对 12 分题来说，这些空间开销都可以接受，但你要心里有数。

6. 一点个人体会

这类题看起来简单，但它把“排序”和“数据结构”这两个主题紧紧地绑在了一起。如果只会默认 sort，遇到行间规则变化就会卡住；如果只背冒泡，数据规模稍微变大就会超时；如果不知道栈能当缓存，就不容易想到第三种解法。我在实际刷题过程中，习惯把同一个基础题至少用两种方式写一遍。不是为了跟别人比代码数量，而是为了让自己在面对变体题的时候，能快速反应出有哪几条路可以走。

最后再分享一个小技巧：遇到“多数组排序”这类题，先不要急着写代码。拿出草稿纸，把输入样例手动排一遍，看清行内和行间的顺序规则。这一步做到位，后面不管选哪种做法都不会跑偏。排序题真正拉分的往往不在算法本身，而在你对“排序对象”和“排序顺序”的理解是否准确。