把数组排成最小（大）的数-创新互联

这是一道经典的面试题，初次看到这道题我们可能会想到全排列，然后把每个排列拼起来，最后我们求出拼出来的最小值就可以了，下面我们说一种更快的算法。

目前创新互联公司已为1000多家的企业提供了网站建设、域名、虚拟空间、网站托管、服务器托管、企业网站设计、徐州网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

      其实我们可以找出一种排序规则，数组根据这个排序规则就能排成一个最小的数。我们要确定排序规则，就要比较两个数字，比如m和n，我们需要一个规则判断m和n哪个应该排在前面，并不仅仅是比较这两个数的大小。

      关于这道题我们还需要考虑的一个潜在问题是假如m和n都在int的表达范围内，那么它们拼接之后呢？超出int的范围怎么办？这些都是我们需要考虑的问题，这是一个隐藏的大数问题。我们都知道，我们可以通过把数字转换成字符串的形式来解决大数问题，这样多大的位数我们都能装下，装换成字符串后，比较他们拼接成的数字的大小就直接按照字符串的大小比较规则来就可以了。下面我们看看具体的代码。

#include
#include 
#include 
const int g_MaxNumberLength = 10;  //×××所能表示的大位数
char *g_StrCombine1 = new char[g_MaxNumberLength*2 + 1];  //用来存放超过×××位数的字符串
char *g_StrCombine2 = new char[g_MaxNumberLength*2 + 1];
int compare(const void* strNumber1, const void* strNumber2)//自定义比较函数，比较两个字符串大小
{
 strcpy(g_StrCombine1, *(const char**)strNumber1);
 strcat(g_StrCombine1, *(const char**)strNumber2);
 strcpy(g_StrCombine2, *(const char**)strNumber2);
 strcat(g_StrCombine2, *(const char**)strNumber1);
 return strcmp(g_StrCombine1, g_StrCombine2)>0;//注意这里大于0默认升序排列，小于0降序
}
void PrintfMinNumber(int* number, int length)
{
 if (number == NULL || length < 0)
 {
  return;
 }
 char** strNumbers = (char**)(new int[length]);  //定义一个二维数组
 int i = 0;
 for (; i < length; ++i)
 {
  strNumbers[i] = new char[g_MaxNumberLength + 1]; // 数组里面每个元素都是char类型的指针
  sprintf(strNumbers[i], "%d", number[i]);
 }
 qsort(strNumbers, length, sizeof(char*), compare);
 i = 0;
 for (; i < length; i++)
 {
  printf("%s", strNumbers[i]);
 }
 printf("\n");
 i = 0;
 for (; i < length; ++i)
 {
  delete[] strNumbers[i];
 }
 delete[] strNumbers;
}
int main()
{
 int arr[3] = { 12, 3, 4};//这里数组内容自己随便给就可以
 int len = sizeof(arr) / sizeof(arr[0]);
 PrintfMinNumber(arr, len);
 return 0;
}

假如是上面数组的内容，我在vs2013下运行结果如下：

        我们可以看到，正如我们预期的那样，把数组内容排成了我们需要的最小的整数。

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

本文标题：把数组排成最小（大）的数-创新互联
网页URL：http://6mz.cn/article/cssejp.html