【洛谷排序算法】P1012拼数-详细讲解

洛谷 P1012 拼数这道题本身并非单纯考察某种经典排序算法（如冒泡排序、选择排序、插入排序、快速排序、归并排序等）的实现，而是在排序的基础上，自定义了排序的比较规则，属于自定义排序类型的题目。不过它借助了标准库中排序算法的功能来完成排序操作，下面详细解释：

这道题本质上是通过确定数字的拼接顺序来得到最大拼接数，虽然主要思路是利用字符串及其比较规则来实现，但也可以基于数组结合一些转换操作来解决，以下是大致思路和代码示例：

【算法思路】

• 首先将输入的数字存储在数组中。
• 然后自定义一个比较函数，在比较函数中，将数组的数字转换为字符串进行拼接比较，从而确定数字的排序顺序。
• 最后将排好序的数组中的数字转换为字符串并拼接输出，得到最大的拼接结果。

【代码示例】

#include<iostream>
#include<algorithm>
#include<string>
#include<vector> 
using namespace std;//自定义比较函数
bool compare(int a,int b){string s1=to_string(a);string s2=to_string(b);return s1+s2>s2+s1;
}int main(){int n;cin>>n;vector<int> nums(n);//定义vector数组，用于存放n个整数 for(int i=0;i<n;++i){//循环依次输入n个整数 cin>>nums[i];} //使用自定义比较函数进行排序 sort(nums.begin(),nums.end(),compare);//遍历数组，拼接输出结果 for(int num:nums){//定义一个int类型的num变量来依次存储nums中的每个元素 cout<<num;} cout<<endl;return 0;
}

• 自定义比较函数：函数的返回值类型是bool，返回值将决定在排序过程中a和b的顺序关系。如果返回true，表示a应该排在b前面；如果返回false，表示b应该排在a前面。

• 使用**to_string函数**（来自<string>头文件），将整数a和整数b分别转化为字符串s1和s2。

• 使用**vector数组nums**而不是直接定义一个普通整型数组：vector是动态数组，避免空间浪费或空间不足的情况；vector与C++标准库中的许多算法（如sort）有很好的兼容性。在使用sort函数对vector进行排序时，不需要额外处理数组边界等问题。

• sort排序算法函数：nums 是一个 vector<int> 类型的数组，nums.begin() 返回一个指向 nums 数组第一个元素的迭代器，nums.end() 返回一个指向 nums 数组最后一个元素的下一个位置的迭代器。这样就指定了要排序的元素范围是 nums 数组中的所有元素。sort 函数在排序过程中，会不断调用这个 compare 函数来比较元素之间的大小关系，从而确定元素的最终排序顺序。例如，对于数组中的两个元素 a 和 b，sort 函数会调用 compare(a, b)，如果返回 true，a 会排在 b 前面；如果返回 false，b 会排在 a 前面。通过调用 sort 函数并传入合适的参数，我们可以方便地对 vector 数组中的元素按照自定义的规则进行排序，从而实现得到最大拼接数的目的。

• 范围for循环：

for (declaration : range) {// 循环体
}

范围 for 循环会自动遍历 range 中的每一个元素，将元素的值依次赋给 declaration 中声明的变量，然后执行循环体。每完成一次循环体的执行，就会获取 range 中的下一个元素，直到遍历完所有元素为止。