题目1190：大整数排序
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：4694
解决：2108
-
题目描述：
-
对N个长度最长可达到1000的数进行排序。
-
输入：
-
输入第一行为一个整数N，(1<=N<=100)。
接下来的N行每行有一个数，数的长度范围为1<=len<=1000。
每个数都是一个正数，并且保证不包含前缀零。
-
输出：
-
可能有多组测试数据，对于每组数据，将给出的N个数从小到大进行排序，输出排序后的结果，每个数占一行。
-
样例输入：
-
3 11111111111111111111111111111 2222222222222222222222222222222222 33333333
-
样例输出：
-
33333333 11111111111111111111111111111 2222222222222222222222222222222222
-
来源：
- 2006年华中科技大学计算机研究生机试真题
-
-
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define MAX_N 105 using namespace std; struct bigInteger{int digit[260];int size;void init(){for(int i=0;i<260;i++)digit[i]=0;size=0;}void set(string &x){init();int maxs=x.size();int count=0;for(int i=maxs-1;i>=0;i--){switch(count){case 0:size++;digit[size-1]=x[i]-'0';count++;break;case 1:digit[size-1]=digit[size-1]+(x[i]-'0')*10;count++;break;case 2:digit[size-1]=digit[size-1]+(x[i]-'0')*100;count++;break;case 3:digit[size-1]=digit[size-1]+(x[i]-'0')*1000;count=0;break;default:break;}}} void output(){for(int i=size-1;i>=0;i--){if(i==size-1)printf("%d",digit[i]);else printf("%04d",digit[i]);}cout<<endl;} }number[MAX_N];bool cmp(const struct bigInteger &a,const struct bigInteger &b){if(a.size!=b.size)return a.size<b.size;else{int pos=a.size;for(int i=pos-1;i>=0;i--){if(a.digit[i]!= b.digit[i]){return a.digit[i]<b.digit[i];}}} }int main(){int n;while(scanf("%d",&n)!=EOF){string a;for(int i=0;i<n;i++){cin>>a;//将字符串处理为大整数number[i].set(a); //number[i].output();}sort(number,number+n,cmp);for(int i=0;i<n;i++){number[i].output();}}return 0; }
将字符串处理为大整数：大整数从最低位开始存储，在struct bigInteger 里面的digit[ ]数组从零开始存储。每一个digit[ ]存储最多四位整数。 -
- cmp( ) 判断思路：如果整数的数位不同，则直接返回数位比较结果。
- 如果整数的数位相同，从高位开始比较，如果数字相同则继续遍历，如果不相同就返回比较结果。