題目連結 : http://zerojudge.tw/ShowProblem?problemid=a528
本題是做大數的排序，用正整數的型態去儲存數字在做排序，保證爆炸
所以這邊是要用到「字串排序這東西」
在這邊要介紹一個神奇的東西 叫做qsort
它是C語言內建的排序，定義在#include <stdlib.h> 裡面
但要使用它必須新增函數，
int cmp(const void *s1 , const void *s2)
{
return *(int*)s2 - *(int*)s1;
}
qsort(Array_name,wantsort_number,sizeof(int),cmp);
上面是整數 型態的大到小排序。
字串型態的在範例程式碼內。
而qsort有個很方便的功能，
它可以排字串，而且很簡單，因此本題本人是用qsort做排序
但qsort做本題有個問題：
以正整數來說，位數最多的一定最大，
但若使用排序，則是ASCII越大的會排在上面(若以大排到小的話)，
他是不會管位數的大小的。
像是：
1111111111111111111111
2222222222222
4444444444444444444444444444444444444444444
3
這樣看來 排出來應該是
4444444444444444444444444444444444444444444
1111111111111111111111
2222222222222
3
但實際上，使用qsort 結果會是
4444444444444444444444444444444444444444444
3
2222222222222
1111111111111111111111
這是沒有照數字大小排的。
那麼該怎麼做?
本人的寫法是這樣：
先把最大的數字找出來， 其長度假設成max好了
max = 最大的數字的長度
全部的字串都輸入完之後，
再利用迴圈，從最大的位數找到1位數 (max--)
如果中間有符合的，則將符合的字串放入另一個陣列內，在繼續往下找。
這時候我們已經找出所以依照位數排的全部字串了，
但還不夠，因為也有可能有多個同位數出現，且數字皆不相等，
這時候就要使用qsort做排序，
方法如下：
把相同位數的字串抓出來，做排序，做完後再依序放回去
如此一來，就可以得到最終結果，
至於負數，本人是與正整數分開做的，如果有其他更好的想法，可以自行試之
範例程式碼如下 另外我覺得本人的寫法爛透了
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char num[1002][150];
char pl[1002][150];
char ans[1002][150];
char ans2[1002][150];
int cmp(const void *s1 , const void *s2)
{
return(strcmp((char *)s1,(char *)s2) );
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int i;
memset(num,'\0',sizeof(num));
memset(pl,'\0',sizeof(pl));
memset(ans,'\0',sizeof(ans));
memset(ans2,'\0',sizeof(ans2));
int max=-1,s;
for(i=0;i<n;i++)
{
scanf("%s",num[i]);
s=strlen(num[i]);
if(s>max)
max=s;
}
int k=0;
int t=1;
int ak=0;
int ak2=0;
while(t<=max)
{
for(i=0;i<n;i++)
{
if(num[i][0]=='-'||num[i][0]=='\0')
continue;
s=strlen(num[i]);
if(t==s)
{
strcpy(pl[k],num[i]);
k++;
num[i][0]='\0';
}
}
qsort(pl,k,sizeof(*pl),cmp);
for(i=0;i<k;i++)
{
strcpy(ans[ak],pl[i]);
ak++;
}
memset(pl,'\0',sizeof(pl));
k=0;
t++;
}
t=0;
while(max>0)
{
for(i=0;i<n;i++)
{
if(num[i][0]=='\0')
continue;
s=strlen(num[i]);
if(max==s)
{
strcpy(pl[k],num[i]);
k++;
}
}
qsort(pl,k,sizeof(*pl),cmp);
for(i=k-1;i>=0;i--)
{
strcpy(ans2[ak2],pl[i]);
ak2++;
}
memset(pl,'\0',sizeof(pl));
k=0;
max--;
}
for(i=0;i<ak2;i++)
{
printf("%s\n",ans2[i]);
}
for(i=0;i<ak;i++)
{
printf("%s\n",ans[i]);
}
}
return 0;
}
創作內容
【程式語言新手】ZeroJudge-a528: 大數排序
超高校級の校園日誌 (98)