算法题19 把数组排成最小的数

题目

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

分析

　　对于元素位置排列的问题，如a,b，我们希望找到一种排列规则，来确定我们所要得到的是a,b还是b,a. 题目要求得到所能排出的最小的数，那如a<b，则从常识来看ab<ba。这个比较规则到底正不正确呢？在剑指offer一书中有很好的证明

　　http://zhedahht.blog.163.com/blog/static/25411174200952174133707/

　　一个有效的比较规则需要三个条件：自反性、对称性、传递性。证明过程如下

　　1. 自反性。即a=a.

　　　显然如aa=aa,则a=a

　　2. 对称性。即如果a>b,则b<a.

　　　如果a<b,由规则ab<ba,显然ba>ab,即b>a.

　　3. 传递性。即如果a<b,b<c，则a<c

　　　假设有条件a<b,b<c，则根据规则ab<ba,bc<cb. 假设a,b,c在高位时的10幂数分别为m,n,l

　　　则a*10^m+b<b*10^n+a —》a*(10^m-1)<b*(10^n-1);

　　　　b*10^n+c<c*10^l+b —》b*(10^n-1)<c*(10^l-1);

　　　因此有a*(10^m-1)<c*(10^l-1)

　　　　　即a*10^m+c<c*10^l+a —》ac<ca

　　　所以有a<c

我们也可以用分情况讨论的思路证明这个规则。对于数组中的a,b来说，排出的数字要么a在b前面，要么b在a前面。假设其他元素已经排成一个最小值XXX。有以下三种情况

http://blog.csdn.net/wuzhekai1985/article/details/6704902

　　1. abXXX

　　　显然如果ab<ba，abXXX<baXXX

　　2. XXXab

　　　显然如果ab<ba，abXXX<baXXX

　　3. aXXXb

　　　我们将中间部分看成c,则有acb.我们已知ab<ba,需证明acb<bca。假设a,c,b的位数分别是m,n,l

　　　若acb>bca，则a*10^m+c*10^n+b>b*10^l+c*10^n+a ，两边同时减c*10^n —》a*10^m+b>b*10^l+a 即ab>ba和已知矛盾。由此可证acb<bca

代码

 const int max_digits=10;
 int catstr_max_len=2*max_digits+1;
 char* catstr1=new char[catstr_max_len];
 char* catstr2=new char[catstr_max_len];
 int comp(const void* a,const void* b)
 {
     sprintf(catstr1,"%d%d",*(int*)a,*(int*)b);

     sprintf(catstr2,"%d%d",*(int*)b,*(int*)a);

     return strcmp(catstr1,catstr2);
 }
 void PrintMinNumber(int numbers[],int len)
 {
     if (!numbers||len<=0)
     {
         throw std::exception("Invalid input.");
     }

     //char* strnum=new char[len*max_digits];
     qsort(numbers,len,sizeof(int*),comp);

     for (int i=0;i<len;i++)
     {
         cout<<numbers[i];
     }
     cout<<endl;
 }