【OJ题目】把数组排成最小的数

题目描述：

给输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。

样例输入1：

{2,1}

样例输出1：

12

样例输入2：

{32,321}

样例输出2：

32132

样例输入3：

{4589,101,41425,9999}

样例输出3：

1014142545899999；

接口说明：

intsmallestDigit(inta[],intnCount,char*strRst)

功能：将输入的数组排成最小的数
输入：inta[]:整型数组

intnCount:数组长度

char*strRst返回值
输出：无
返回：成功返回0异常返回-1

这道题目用冒泡排序就能解决，但是判断的条件不是比数值，而是：

如果（（A排在B后面形成的数）> （A排在B前面形成的数））做（A/B交换），巧妙之处，也在于此；

#include <stdlib.h>
#include <string.h>
#include "oj.h"


//判断两个字符串是否需要交换
bool needExchange(char* s1, char* s2) 
{
  char *t1 = (char*)malloc(33);
  char *t2 = (char*)malloc(33);
          strcpy(t1,s1);
  strcat(t1,s2);

  strcpy(t2,s2);
  strcat(t2,s1);
     if(strcmp(t1, t2) > 0)
   return true;
  else
   return false;
}

// 功能：将输入的数组排成最小的数
// 输入： int a[]:整型数组
//        int nCount:数组长度
//        char * strRst 返回值
// 输出：
// 返回：成功返回0  异常返回-1

int  smallestDigit(int a[],int nCount,char * strRst)
{
    char s[100][33];
 char *ss[100]; //用来记录每个字符串的起始指针，实际只需要交换起始指针即可
 int i,j,n;
 char *t;
 n = nCount;
 for(i=0; i<nCount; i++)
 {
  if(a[i]<=0)
   return -1;
  else
         itoa(a[i], s[i], 10);
 }
 for(i=0; i<nCount; i++)
 {
  ss[i] = &s[i][0];
 }
 for(i=0; i<n; i++)
 {
  for(j=0; j<nCount-1; j++)
  {
   if(needExchange(ss[j],ss[j+1]))
   {
    t = ss[j];
    ss[j] = ss[j+1];
    ss[j+1] = t;
    //n = j; 
    /*这里我想当然的还像普通冒泡排序一样，记录最后一次交换的位置；
    实际不是这样的，要把每一个元素都遍历到,比如{1590,24,22}，看似1590沉到底了，但是后来的24和22还是要交换的*/
   }
  }
 }
 for(i=0; i<nCount; i++)
 {
  strcat(strRst, ss[i]);
 }
 return 0;
}

测试用例：

void CExampleTest::TestCase01()
{    
 int a[] = {1234,123,120,11,1540,234,32,321,322,323,324};
 char szRst[100]  = {0};
 char *strExpect = "111201231234154023432132232323324";
 smallestDigit(a,11,szRst);
 CPPUNIT_ASSERT(0 == strcmp(szRst,strExpect));
}

// 在这里添加测试用例实现
void CExampleTest::TestCase02()
{    
 int a[] = {32, 321,324};
 char szRst[100]  = {0};
 char *strExpect = "32132324";
 smallestDigit(a,3,szRst);
 CPPUNIT_ASSERT(0 == strcmp(szRst,strExpect));
}