题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。例如输入数组{32, 321}，则输出这两个能排成的最小数字32132。请给出解决问题的算法，并证明该算法。
分析：这是09年6月份百度新鲜出炉的一道面试题，从这道题我们可以看出百度对应聘者在算法方面有很高的要求。
这道题其实是希望我们能找到一个排序规则，根据这个规则排出来的数组能排成一个最小的数字。要确定排序规则，就得比较两个数字，也就是给出两个数字m和n，我们需要确定一个规则m和n哪个更大，而不是仅仅只是比较这两个数字的数值哪个更大。
根据题目的要求，两个数字m和n排成的数字mn和nm，如果mn 接下来我们考虑怎么去拼接数字，即给出数字m和n，怎么得到数字mn和nm并比较它们的大小。直接用数值去计算不难办到，但需要考虑到的一个潜在问题是m和n都在int能表达的范围内，但把它们拼起来的数字mn和nm就不一定能用int表示了。所以我们需要解决大数问题。一个非常直观的方法就是把数字转换成字符串。 另外，由于把数字m和n拼接起来得到的mn和nm，它们所含有的数字的个数肯定是相同的。因此比较它们的大小只需要按照字符串大小的比较规则就可以了。 基于这个思路，我们可以写出下面的代码： // Maxinum int number has 10 digits in decimal system const int g_MaxNumberLength = 10; // String buffers to combine two numbers char* g_StrCombine1 = new char[g_MaxNumberLength * 2 + 1]; char* g_StrCombine2 = new char[g_MaxNumberLength * 2 + 1]; // Given an array, print the minimum number // by combining all numbers in the array void PrintMinNumber(int* numbers, int length) { if(numbers == NULL || length <= 0) return; // Convert all numbers as strings char** strNumbers = (char**)(new int[length]); for(int i = 0; i < length; ++i) { strNumbers[i] = new char[g_MaxNumberLength + 1]; sprintf(strNumbers[i], "%d", numbers[i]); } // Sort all strings according to algorithm in function compare qsort(strNumbers, length, sizeof(char*), compare); for(int i = 0; i < length; ++i) printf("%s", strNumbers[i]); printf("\n"); for(int i = 0; i < length; ++i) delete[] strNumbers[i]; delete[] strNumbers; } // Compare two numbers in strNumber1 and strNumber2 // if [strNumber1][strNumber2] > [strNumber2][strNumber1], // return value > 0 // if [strNumber1][strNumber2] = [strNumber2][strNumber1], // return value = 0 // if [strNumber1][strNumber2] < [strNumber2][strNumber1], // return value < 0 int compare(const void* strNumber1, const void* strNumber2) { // [strNumber1][strNumber2] strcpy(g_StrCombine1, *(const char**)strNumber1); strcat(g_StrCombine1, *(const char**)strNumber2); // [strNumber2][strNumber1] strcpy(g_StrCombine2, *(const char**)strNumber2); strcat(g_StrCombine2, *(const char**)strNumber1); return strcmp(g_StrCombine1, g_StrCombine2); } 上述代码中，我们在函数compare中定义比较规则，并根据该规则用库函数qsort排序。最后把排好序的数组输出，就得到了根据数组排成的最小的数字。 找到一个算法解决这个问题，不是一件容易的事情。但更困难的是我们需要证明这个算法是正确的。接下来我们来试着证明。 首先我们需要证明之前定义的比较两个数字大小的规则是有效的。一个有效的比较需要三个条件：1.自反性，即a等于a；2.对称性，即如果a大于b，则b小于a；3.传递性，即如果a小于b，b小于c，则a小于c。现在分别予以证明。 1. 自反性。显然有aa=aa，所以a=a。 3. 传递性。如果a小于b，则ab 如果b小于c，则bc 所以a/(10l -1)< c/(10n -1)。于是a(10n -1) 所以a小于c。 在证明了我们排序规则的有效性之后，我们接着证明算法的正确性。我们用反证法来证明。 我们把n个数按照前面的排序规则排好顺序之后，表示为A1A2A3…An。我们假设这样排出来的两个数并不是最小的。即至少存在两个x和y（0 由于A1A2…Ax…Ay…An是按照前面的规则排好的序列，所以有Ax 由于Ay-1小于Ay，所以Ay-1Ay 同理由于Ax小于Ax+1，所以AxAx+1 所以A1A2…Ax…Ay…An< A1A2…Ay…Ax…An。这和我们的假设的A1A2…Ay…Ax…An 所以假设不成立，我们的算法是正确的。
2. 对称性。如果a小于b，则ab