C++自定义排序算法：解决数字拼接最小数问题

2026/8/13 8:48:21

1. 项目概述与核心价值

最近在带新人，发现很多刚接触C++的朋友，在解决一些看似简单的算法问题时，常常会陷入“想当然”的误区。比如，给你一堆个位数，比如{1, 3, 0, 9, 2}，让你把它们组合成一个最小的数字。很多人的第一反应是：这还不简单？直接排序然后拼起来呗！于是他们可能会写出01329这样的结果。但仔细想想，01329真的是最小的数字吗？作为数字，它的值是1329，而如果我们把0放在开头，它实际上被忽略了。这个问题看似是“排序”，实则是一个关于“自定义排序规则”和“大数处理”的经典入门题，它考察的是对数据本质的理解和C++标准库的灵活运用。

这个项目“n个一位数能够组成的最小数”的核心，就是编写一个C++程序，接收用户输入的一组一位数（0-9），然后输出由这些数字排列组合所能形成的最小数值（以字符串形式输出，避免前导零被忽略）。它麻雀虽小，五脏俱全，涉及了输入处理、排序算法、字符串操作以及自定义比较器这些C++编程的基础核心。对于初学者而言，亲手实现一遍，能深刻理解为什么不能简单地对数字进行升序排列，以及如何利用std::sort和自定义规则来优雅地解决这类“拼接比较”问题。这不仅是刷题，更是培养一种严谨的、符合计算机逻辑的思维方式。

2. 问题深度解析与思路拆解

2.1 为什么不能直接排序数字？

这是理解本题的关键。假设我们有一组数字：[3, 30, 34, 5, 9]。如果按照数值大小升序排列，得到[3, 5, 9, 30, 34]，拼接成字符串是3593034。但这是最小的吗？显然不是。我们可以尝试3033459，它比3593034要小。为什么？因为数字的拼接不是加法，3和30拼接成330，而30和3拼接成303，303 < 330。所以，决定两个数a和b在最终序列中先后顺序的，不是a和b本身的数值大小，而是ab和ba这两种拼接方式所形成的字符串的字典序（或数值）大小。

因此，我们需要一种新的比较规则。对于两个数字字符串a和b，如果a + b < b + a（这里的+是字符串拼接，<是字符串字典序比较），那么a就应该排在b的前面。这样，在最终拼接时，才能保证整体字符串的字典序最小。这就是本题的“自定义排序”思想。

2.2 一位数情况的特殊性

题目明确限定为“一位数”，这实际上简化了问题。因为一位数（0-9）转换成字符串后，长度都是1。在这种情况下，我们自定义比较规则a + b < b + a就退化成了简单的a < b（单个字符比较）。例如，‘2’ + ‘5’ = “25”，‘5’ + ‘2’ = “52”，因为‘2’ < ‘5’，所以“25” < “52”，规则成立。所以，对于纯一位数，直接按字符升序排序，然后拼接，理论上就能得到最小数字字符串。

但是，这里有一个巨大的陷阱：数字0。如果我们排序后得到的字符串以‘0’开头怎么办？例如输入全是{0, 0, 0}，排序拼接后是“000”，但作为数字，它应该输出“0”。更常见的，输入{0, 1, 2}，排序后是“012”，但最小数字应该是“12”吗？不对，应该是“102”吗？让我们用自定义规则验证一下：“0”+“1”=“01”，“1”+“0”=“10”，因为“01” < “10”，所以“0”应该排在“1”前面。同理，“0”也应排在“2”前面。所以排序后确实是“012”。但“012”作为整数是12。然而，“102”的值是102，“012”（即12）显然更小。所以，对于以‘0’开头的字符串，我们需要进行后处理：如果最终拼接后的字符串第一个字符是‘0’，那么说明整个数字就是0，我们应该返回“0”。

2.3 算法流程设计

基于以上分析，我们可以设计出清晰的算法步骤：

输入处理：读取整数n，然后循环读取n个一位数，将它们转换为字符（‘0’到‘9’）并存入一个字符串数组或向量中。
排序：使用标准库的std::sort函数，配合自定义的比较函数（或Lambda表达式）对字符串数组进行排序。比较规则是：对于两个字符串a和b，返回(a + b) < (b + a)。
拼接：将排序后的字符串数组中的所有字符串依次拼接起来，形成一个结果字符串。
处理前导零：检查结果字符串的第一个字符。如果是‘0’，则直接返回“0”；否则，返回结果字符串本身。
输出：输出最终的结果字符串。

这个流程逻辑清晰，且完全遵循了“自定义排序”的核心思想。即使题目简化为一位数，我们依然采用通用解法，这有助于我们理解更一般化的问题（如“把数组排成最小的数”）。

3. 核心代码实现与逐行解析

接下来，我们将用C++实现上述算法。我会提供两个版本的代码：一个是针对本题“一位数”特性的简化实现，另一个是更具通用性和教学意义的完整实现。我们重点讲解后者。

3.1 完整通用实现

#include <iostream> #include <vector> #include <string> #include <algorithm> // 用于std::sort using namespace std; // 自定义比较函数，决定两个字符串在最终序列中的先后顺序 bool compare(const string &a, const string &b) { return (a + b) < (b + a); // 如果 a+b 的字典序小于 b+a，则a应排在b前面 } int main() { int n; cout << "请输入数字的个数 n: "; cin >> n; vector<string> nums(n); // 使用vector存储数字字符串 cout << "请依次输入 " << n << " 个一位数（0-9），用空格或回车分隔: "; // 读取n个整数，并立即转换为字符串存入vector for (int i = 0; i < n; ++i) { int num; cin >> num; // 将数字转换为对应的字符，然后构造为字符串 // 也可以使用 nums[i] = to_string(num); nums[i] = char(num + '0'); // 一位数，直接转换更高效 } // 关键步骤：使用自定义比较规则进行排序 sort(nums.begin(), nums.end(), compare); // 拼接排序后的所有字符串 string result; for (const string &s : nums) { result += s; } // 处理前导零的特殊情况：如果结果第一个字符是'0'，则整个数字就是0 if (result[0] == '0') { result = "0"; } cout << "能够组成的最小数是: " << result << endl; return 0; }

代码逐行解析与关键点：

头文件与命名空间：
- #include <algorithm>：必不可少，提供了std::sort函数。
- using namespace std;：在小型练习项目中可以使用，避免频繁写std::。但在大型项目中建议显式使用std::以避免命名冲突。
自定义比较函数compare：
- bool compare(const string &a, const string &b)：函数接收两个常引用字符串，返回布尔值。
- return (a + b) < (b + a);：这是算法的灵魂。它比较的是两种拼接方式的字典序。注意，这里比较的是字符串，例如a="3",b="30"，则比较"330"和"303"，由于"303" < "330"，所以compare(“3”, “30”)返回false，意味着在排序时“3”不应该排在“30”前面（即“30”应该排在“3”前面）。这与我们之前的分析一致。
输入处理：
- vector<string> nums(n);：使用vector动态数组存储字符串，比原生数组更安全、方便。
- nums[i] = char(num + ‘0’);：这是将一位整数（0-9）转换为对应字符的经典方法。字符‘0’的ASCII码是48，数字num加上48就得到了对应数字字符的ASCII码，再通过char()转换。例如，num=5，5+48=53，ASCII码53对应的字符就是‘5’。这里用这个方法是为了展示原理，实际上用nums[i] = to_string(num);更直观且支持多位数。
排序：
- sort(nums.begin(), nums.end(), compare);：调用标准库排序。nums.begin()和nums.end()定义了排序范围。第三个参数compare是我们自定义的比较规则。sort函数会根据这个规则重新排列nums中的元素。
拼接与后处理：
- 使用for (const string &s : nums)范围for循环遍历排序后的vector，将每个字符串追加到result中。
- if (result[0] == ‘0’)：这是处理前导零的关键。如果排序后第一个字符就是‘0’（这只会发生在所有输入数字都是0的情况下，因为按照我们的比较规则，0会排在最前面），那么最终数字就是0。我们将result置为“0”。

3.2 简化实现（针对纯一位数）

如果我们确信输入严格是一位数，并且想写更简洁的代码，可以利用一位数排序即字符排序的特性：

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<char> digits(n); // 直接存储字符 for (int i = 0; i < n; ++i) { int tmp; cin >> tmp; digits[i] = tmp + '0'; } // 直接对字符进行升序排序 sort(digits.begin(), digits.end()); string result; for (char c : digits) result += c; // 处理前导零 if (!result.empty() && result[0] == '0') { // 但这里有个问题：如果输入是{0, 1}，排序后是"01"，我们希望输出"01"吗？ // 不，作为最小数字，应该是“10”。所以简化版其实有缺陷！ // 正确的通用解法必须用自定义比较。 result = (result.back() == '0') ? "0" : result.substr(1) + result[0]; // 这个处理是错的，仅作演示 // 实际上，对于{0,1}，自定义比较规则下，排序结果是["0","1"]，因为"01"<"10"。 // 拼接后是"01"，然后我们检查首字符是'0'，但此时不能简单输出"0"，因为还有非零数字。 // 所以，简化版无法正确处理包含0和非0数字的情况！这印证了必须使用通用解法。 } cout << result << endl; return 0; }

请注意：这个简化版本在处理像{0, 1}这样的输入时会得到错误结果。它说明了为什么即使是一位数，也需要用“自定义拼接比较”的通用思路来思考，否则就会掉入陷阱。因此，强烈推荐掌握并始终使用通用实现方法。

4. 从项目延伸：常见问题与深度思考

4.1 为什么使用字符串而不是整数进行比较和存储？

这是为了避免整数溢出和方便拼接。假设数字很大，a=121，b=12，ab=12112，ba=12121，这个拼接后的数字可能超出int甚至long long的范围。而用字符串拼接和字典序比较，则完全没有这个问题。字典序比较规则与数值比较规则在非负整数拼接的场景下是一致的，这为我们提供了极大的便利。

4.2 自定义比较函数的严格弱序要求

std::sort要求比较函数必须满足“严格弱序”。我们的compare(a, b)定义是(a+b) < (b+a)。它需要满足：

非自反性：compare(a, a)必须为false。
不对称性：如果compare(a, b)为true，则compare(b, a)必须为false。
可传递性：如果compare(a, b)为true且compare(b, c)为true，则compare(a, c)必须为true。

我们的函数满足这些条件吗？前两条显然满足。第三条可传递性需要证明，在数学上，如果定义a ≺ b为a+b < b+a（字符串比较），那么这个关系是可传递的。这保证了sort函数能够正确工作。这是一个重要的知识点，在面试中可能会被问到。

4.3 处理前导零的另一种思路

我们在通用代码中，是在排序拼接完成后检查result[0]。还有一种思路是在排序前就处理：如果排序后第一个字符串是“0”，那么我们需要找到第一个非“0”的字符串，将其与开头的“0”交换。但这种方法实现起来稍显复杂，且不如后处理直观。我们的后处理方法简单有效，且易于理解。

4.4 性能考虑与优化

时间复杂度：主要耗时在排序，std::sort的平均时间复杂度是 O(N log N)，其中 N 是数字个数。每次比较需要拼接字符串，拼接操作的时间复杂度是 O(k)，k 是字符串长度。在本项目中，k=1，所以每次比较是 O(1)，总时间仍是 O(N log N)。对于通用情况（数字位数不定），k 是数字的平均长度，总时间约为 O(N log N * k)。
空间复杂度：我们使用了vector<string>存储所有数字的字符串形式，空间复杂度为 O(N * k)。对于本题，k=1，所以是 O(N)。
优化点：在比较函数中，a+b和b+a会创建临时字符串。如果数字很长且数量很多，频繁创建临时字符串可能影响性能。一种优化是重写比较函数，在不拼接的情况下进行比较，例如像比较字典序一样，交替比较a和b的字符。但这会提高代码复杂度。对于入门练习和一般场景，当前的实现清晰且足够高效。

5. 项目扩展与变体思考

掌握了这个核心算法后，你可以尝试解决一些变体问题，这能极大地锻炼你的思维：

最大数：如何排列这些数字使其组成的数最大？很简单，只需将自定义比较规则中的<改为>即可，即return (a + b) > (b + a);。
包含负数和/或小数：如果数字可以是负数或小数，规则就完全不同了。这需要更复杂的分类讨论和比较逻辑，是一个很好的进阶挑战。
LeetCode原题：在LeetCode上有一道几乎一样的题目“179. 最大数”，不过它要求的是排列成最大的数。我们的解法稍作修改即可通过。尝试去刷一下这道题，检验自己的学习成果。
输入验证：在工业级代码中，我们需要对输入进行验证。例如，检查输入的数字是否确实是一位数（0-9），处理非数字输入等。可以尝试为你的程序增加健壮性。
使用其他数据结构：能否使用list或deque来存储？排序算法是否依然适用？思考不同数据结构的适用场景。