【算法17】把数组排成最小的数

　　【题目】输入一个正整数数组，将他们连接起来排成一个数，输出所有排出的数字中最小的一个。例如：输入数组『32，321』，输出所能排出的最小数为：32132.请给出该问题的算法。

　　【思路】我们希望能够找到一种规则，按照这种规则排列出来的数是最小的数。要确定排序的规则，我们就必须知道，对于任意两个正整数a和b，如果确定一个规则，使得按照该问题进行排序能得到最小的数，也就是要比较a和b的值，而这种比较不是普通的数值的大小。

　　对于数字a和b，排列的结果为ab和ba，如果ab小于ba，应该输出ab，即a排在b的前面，也就是a<b。反之，如果ba小于ab，即b排在a前面，也就是b<a。如果ab等于ba，那么a=b。

　　接下里的问题是：给出数字a和b，如果拼接得到ab或者ba，然后比较他们的大小？如果直接用数值进行拼接当然是可以的，但是我们考虑到a和b都是int型的，如果拼接后得到数字超出int型的范围导致结果溢出该怎么办？很自然我们想到可以现将整数都转换成字符串类型，然后在连接。

　　如何比较ab和ba的大小？很显然按字典序直接比较ab字符串和ba字符串的值就可以了。根据这个思路，我们可以写出如下的代码：

 1 #include<iostream>
 2 #include<string>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 
 7 //每个整数最长有10个数字组成；
 8 const int maxDigits = 10;
 9 
10 //两个临时字符串用于存放ab和ba
11 char* strCombine1 = new char[2*maxDigits+1];
12 char* strCombine2 = new char[2*maxDigits+1];
13 
14 //定义a和b的比较规则；
15 //定义如果ab<ba，则a<b；
16 //定义如果ba<ab，则b<a；
17 //定义如果ab=ba，则a=b；
18 int comp(const void* a,const void* b)
19 {
20     //得到ab
21     strcpy(strCombine1,*(const char**)a);
22     strcat(strCombine1,*(const char**)b);
23     
24     //得到ba
25     strcpy(strCombine2,*(const char**)b);
26     strcat(strCombine2,*(const char**)a);
27 
28     return strcmp(strCombine1,strCombine2);
29 }
30 
31 void printMinNumber(int numbers[],int length)
32 {
33     if(numbers == NULL || length < 0)
34         return;
35 
36     //建立新的字符串数组
37     char **strNumbers = (char**)(new int[length]);
38 
39     //每个字符串数组的元素建立新的字符串，并复制为numbers中的值
40     for(int i = 0;i < length;++i)
41     {
42         strNumbers[i] = new char[maxDigits + 1];
43         sprintf(strNumbers[i],"%d",numbers[i]);
44     }
45 
46     //按照定义的规则进行快速排序
47     qsort(strNumbers,length,sizeof(char*),comp);
48 
49     //输出结果
50     for(i = 0;i < length;++i)
51     {
52         printf("%s",strNumbers[i]);
53     }
54     printf("\n");
55 
56     //delete
57     for(i = 0;i < length;++i)
58     {
59         delete[] strNumbers[i];
60     }
61     //delete
62     delete[] strNumbers;
63 }
64 
65 int main()
66 {
67     cout<<"Please Enter your arraylenth:"<<endl;
68     int n =0;
69     cin>>n;
70 
71     cout<<"please Enter your array elements:"<<endl;
72     int* array = new int[n];
73     for(int k =0;k < n;++k)
74     {
75         cin>>array[k];
76     }
77 
78     cout<<"the minNumber from your array is:"<<endl;
79     printMinNumber(array,n);
80 
81     delete[] array;
82     return 0;
83 }

　　运行结果如下：

　　其实该问题还有一问，是要求证明该算法是正确的，笔者窃以为对于我们找出的排序规则来说这是显然的。这就好比如果我们定义了比较两个数大小的规则，比如就是最简单的数值比较规则，然后有一个数组，要按照这个比较规则进行排序，它排出来的序是违反这个规则的？显然是不可能的。所以只需确定这个比较的规则是正确的就可以了，而比较规则的正确性，这里是借助字符串的比较规则来实现的，完全没有问题。所以个人感觉这个证明是不必要的。当然如果对这个说法有疑问，要看证明过程，请移步这里。

References:　　

程序员面试题精选100题：http://zhedahht.blog.163.com/blog/static/25411174200952174133707/

注：

1）本博客所有的代码环境编译均为win7+VC6。所有代码均经过博主上机调试。

2）博主python27对本博客文章享有版权，网络转载请注明出处http://www.cnblogs.com/python27/。对解题思路有任何建议，欢迎在评论中告知。