把數組排成最小（大）的數-創新互聯

這是一道經典的面試題，初次看到這道題我們可能會想到全排列，然后把每個排列拼起來，最后我們求出拼出來的最小值就可以了，下面我們說一種更快的算法。

目前創新互聯公司已為1000多家的企業提供了網站建設、域名、虛擬空間、網站托管、服務器托管、企業網站設計、徐州網站維護等服務，公司將堅持客戶導向、應用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協力一起成長，共同發展。

其實我們可以找出一種排序規則，數組根據這個排序規則就能排成一個最小的數。我們要確定排序規則，就要比較兩個數字，比如m和n，我們需要一個規則判斷m和n哪個應該排在前面，并不僅僅是比較這兩個數的大小。

關于這道題我們還需要考慮的一個潛在問題是假如m和n都在int的表達范圍內，那么它們拼接之后呢？超出int的范圍怎么辦？這些都是我們需要考慮的問題，這是一個隱藏的大數問題。我們都知道，我們可以通過把數字轉換成字符串的形式來解決大數問題，這樣多大的位數我們都能裝下，裝換成字符串后，比較他們拼接成的數字的大小就直接按照字符串的大小比較規則來就可以了。下面我們看看具體的代碼。

#include<stdio.h>
#include <stdlib.h>
#include <string.h>
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下運行結果如下：

把數組排成最小（大）的數