tags： 排序
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
参考
首先因为数组可能非常长，所以要定义一个整数类，使得其大小可以容纳所有的数组元素组成的数不大现实。因此我们直接输出这个数组，让其看起来像一个整数，这样我们就可以把问题转化为：如何给这个数组排序，使其看做一个数字的时候最小。 第一个想到的可能是按字典序排序，小的在前面。可惜这个是不可行的，比如32的字典序比322小，但是32322比32232大， 所以在这里自定义一个比较大小的函数，比较两个字符串s1, s2大小的时候，先将它们拼接起来，比较s1+s2,和s2+s1那个大，如果s1+s2大，那说明s2应该放前面，所以按这个规则，s2就应该排在s1前面。
思路：先将整数数组转为字符串数组，然后字符串数组进行排序，最后依次输出字符串数组即可。这里注意的是字符串的比较函数需要重新定义，不是比较a和b，而是比较ab与 ba。如果ab < ba，则a < b；如果ab > ba，则a > b；如果ab = ba，则a = b。比较函数的定义是本解决方案的关键。这道题其实就是希望我们能找到一个排序规则，根据这个规则排出来的数组能排成一个最小的数字。
用于C++中，对给定区间所有元素进行排序。头文件是#include
sort函数进行快速排序，时间复杂度为n*log2n，比冒泡之类的要省时不少
Sort函数使用模板:
Sort(start,end,排序方法)
1.第一个参数是要排序数组的起始地址
2.第二个参数是数组结束地址的下一位
3.第三个是排序的方法，可不填，默认升序
如果你需要自己定义比较函数，你可以把你定义好的仿函数(functor)作为参数传入。每种算法都支持传入比较函数。以下是所有STL sort算法函数的名字列表:
| 函数名 | 功能描述 |
|---|---|
| sort | 对给定区间所有元素进行排序 |
| stable_sort | 对给定区间所有元素进行稳定排序 |
| partial_sort | 对给定区间所有元素部分排序 |
| partial_sort_copy | 对给定区间复制并排序 |
| nth_element | 找出给定区间的某个位置对应的元素 |
| is_sorted | 判断一个区间是否已经排好序 |
| partition | 使得符合某个条件的元素放在前面 |
| stable_partition | 相对稳定的使得符合某个条件的元素放在前面 |
其中nth_element 是最不易理解的，实际上，这个函数是用来找出第几个。例如：找出包含7个元素的数组中排在中间那个数的值，此时，我可能不关心前面，也不关心后面，我只关心排在第四位的元素值是多少。
当你需要按照某种特定方式进行排序时，你需要给sort指定比较函数，否则程序会自动提供给你一个比较函数。
vector < int > vect;
//...
sort(vect.begin(), vect.end());
//此时相当于调用
sort(vect.begin(), vect.end(), less<int>() );
上述例子中系统自己为sort提供了less仿函数。在STL中还提供了其他仿函数，以下是仿函数列表:
| 名称 | 功能描述 |
|---|---|
| equal_to | 相等 |
| not_equal_to | 不相等 |
| less | 小于 |
| greater | 大于 |
| less_equal | 小于等于 |
| greater_equal | 大于等于 |
需要注意的是，这些函数不是都能适用于你的sort算法，如何选择，决定于你的应用。另外，不能直接写入仿函数的名字，而是要写其重载的()函数：
less<int>()
greater<int>()
当你的容器中元素时一些标准类型（int float char)或者string时，你可以直接使用这些函数模板。但如果你时自己定义的类型或者你需要按照其他方式排序，你可以有两种方法来达到效果：一种是自己写比较函数。另一种是重载类型的'<'操作赋
sort()函数接受二元谓词，但是在类内定义的myCompare函数作为成员函数，实际上有三个参数，this指针、m、n。 解决方案： 1、将myCompare()函数挪到类定义的外面，即改为非成员函数； 2、将myCompare()函数定义为静态成员函数，没有this指针。
3、将myCompare()函数定义为类的友元函数，但是此时必须在类外声明该函数，否则，即使在类内定义了该友元函数，该函数仍然是不可见的。
按照C++11的标准，to_string函数对每个基础算术类型均有重载函数
这个函数也可以自己写
template<class T>
string ToString(const T& t)
{
ostringstream oss; // 创建一个流
oss <<t; // 把值传递如流中
return oss.str( ); // 获取转换后的字符转并将其写入result
}
class Solution {
public:
string PrintMinNumber(vector<int> numbers) {
string res="";
int length=numbers.size();
if(length<=0)
return res;
vector<string> temp(length);
for(int i=0;i<length;i++)
temp[i]=to_string(numbers[i]);
sort(temp.begin(),temp.end(),compare);
for(int i=0;i<length;i++)
res=res+temp[i];
return res;
}
static bool compare(const string& str1,const string& str2){
string s1=str1+str2;
string s2=str2+str1;
return s1<s2;
}
};