首页 > 试题广场 >

大整数排序

[编程题]大整数排序
  • 热度指数：18190 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
对N个长度最长可达到1000的数进行排序。

输入描述:
输入第一行为一个整数N，(1<=N<=100)。
接下来的N行每行有一个数，数的长度范围为1<=len<=1000。
每个数都是一个正数，并且保证不包含前缀零。


输出描述:
可能有多组测试数据，对于每组数据，将给出的N个数从小到大进行排序，输出排序后的结果，每个数占一行。
示例1

输入

3
11111111111111111111111111111
2222222222222222222222222222222222
33333333

输出

33333333
11111111111111111111111111111
2222222222222222222222222222222222
算法知识视频讲解
添加回答
RPGzreo头像 RPGzreo
//高精度整数比较大小 
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct bigInt {
	int d[1005];
	int size;
	void init() {//初始化
		for (int i = 0; i < 1005; i++) {
			d[i] = 0;
		}
		size = 0;//目前还没有任何一个单位被使用
	}
	void set(char str[]) {//提取字符串
		init();
		int len = strlen(str);
		for (int i = len - 1; i >= 0; i--) {
			d[size++] = str[i] - '0';
		}
	}
	void output() {//输出函数
		for (int i = size - 1; i >= 0; i--) {
			printf("%d", d[i]);
		}
		if (size == 0) printf("0");
		printf("\n");
	}
}list[101];

bool cmp(bigInt a, bigInt b) {
	for (int i = 1005 - 1; i >= 0; i--) {
		if (a.d[i] < b.d[i]) return true;
		else if (a.d[i] > b.d[i]) return false;
	}
	return false;
}

int main() {
	int n;
	char str[1002];
	while (scanf("%d", &n) != EOF) {
		for (int i = 1; i <= n; i++) {
			scanf("%s", str);
			list[i].set(str);
		}
		sort(list + 1, list + 1 + n, cmp);
		for (int i = 1; i <= n; i++) {
			list[i].output();
		}
	}
	return 0;
}


编辑于 2019-09-01 21:30:54 回复(0)
更多回答
C/C++
Aldrichヾ头像 Aldrichヾ 
//感觉利用sort函数就ok了，先按照字符串长度比较
//再利用strcmp去比较字符串字典序。
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct node{
    char str[1100];
    int len;
}num[110];
bool cmp(node a,node b){
    if(a.len!=b.len) return a.len<b.len;
    else return strcmp(a.str,b.str)<0;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
      for(int i=0;i<n;i++){
        scanf("%s",num[i].str);
        num[i].len=strlen(num[i].str);
        }
        sort(num,num+n,cmp);
        for(int i=0;i<n;i++){
            printf("%s\n",num[i].str);
        }
    }
    return 0;
}

发表于 2019-01-10 15:46:11 回复(0)
Python
华科平凡头像 华科平凡

python 3 lines solution:

while True:
    try:
        a, arr = int(input()), []
        for i in range(a): arr.append(int(input()))
        for i in sorted(arr): print(i)

    except:
        break
发表于 2017-10-01 16:55:46 回复(2)
C/C++
Senjie头像 Senjie 
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(string a,string b)
{
    if(a.length()!=b.length())
        return a.length()<b.length();
    else
        return a<b;
}
int main()
{
    int N;
    while(cin>>N)
    {
        getchar();
        string a[N];
        for(int i=0;i<N;getline(cin,a[i++]));
        sort(a,a+N,cmp);
        for(int i=0;i<N;cout<<a[i++]<<endl);
    }
}

发表于 2018-08-15 16:32:42 回复(2)
哆啦不爱梦爱美食头像 哆啦不爱梦爱美食
#include <stdio.h>
#include <string.h>
int main(){
    int N,i,a,b,j;
    char s[100][1000],temp[1000];
    while(scanf("%d",&N)!=EOF){
        for(i=0;i<N;i++){
            scanf("%s",s[i]);
        }
        for(i=0;i<N;i++){
            for(j=i;j<N;j++){
                a=strlen(s[i]);
                b=strlen(s[j]);
                if(a>b){
                    strcpy(temp,s[i]);
                    strcpy(s[i],s[j]);
                    strcpy(s[j],temp);
                }
                if(a==b){
                    if(strcmp(s[i],s[j])>0){
                    strcpy(temp,s[i]);
                    strcpy(s[i],s[j]);
                    strcpy(s[j],temp);
                    }
                }
            }
        }
        for(i=0;i<N;i++)
            printf("%s\n",s[i]);
    }
}

发表于 2018-04-14 11:13:12 回复(0)
C/C++
My_C头像 My_C 
//AC代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool cmp(string s1,string s2);
bool cmp(string s1,string s2){   
    if(s1.length()>s2.length()) return false;
    else if(s1.length()<s2.length()) return true;
    else if(s1.length()==s2.length()){
        for(int i=0;i<s1.length();i++){
            if(s1[i]>s2[i]) return false;
            else if(s1[i]<s2[i]) return true;
        }
    }
    return true;
}

int main(){
    int n,i;
    string num[100];
    while(cin>>n){
        for(i=0;i<n;i++){
            cin>>num[i];
        }
        sort(num,num+n,cmp);
        for(i=0;i<n;i++){
            cout<<num[i]<<endl;
        }
    }
    return 0;
}


//自己写的，测试没问题
#include <iostream>
#include <string>
using namespace std;
int main(){
    int k,n,i,j,len1,len2;
    string num[1000];
    while(cin>>n){
        for(i=0;i<n;i++){
            cin>>num[i];
        }
        for(i=0;i<n;i++){
            for(k=i+1;k<n;k++){
                len1=num[i].size();
                len2=num[k].size();
                if(len1>len2){
                    string temp=num[i];
                    num[i]=num[k];
                    num[k]=temp;
                }else if(len1==len2){
                    for(j=0;j<len1;j++){
                        if(num[i][j]>num[k][j]){
                            string temp1=num[i];
                            num[i]=num[k];
                            num[k]=temp1;
                            break;
                        }
                    }
                }
            }           
        }
        for(i=0;i<n;i++){
            cout<<num[i]<<endl;
        }
    }
    return 0;
}

发表于 2017-12-04 11:26:05 回复(5)
dragonlogin头像 dragonlogin 
import java.util.*;
import java.math.*;
public class Main{
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		while(s.hasNext()){
			int n = s.nextInt();
			BigInteger[] bg = new BigInteger[n];
			for(int i=0; i<n; i++)
				bg[i] = s.nextBigInteger();
			Arrays.sort(bg);
			for(int i=0; i<n; i++)
				System.out.println(bg[i]);
		}
	}
}

发表于 2017-03-14 22:25:23 回复(2)
HENRY58头像 HENRY58
将每个大数当作字符串进行储存，然后再对字符串数组进行排序
排序的方法：
1、长度越长的字符串所代表的数值越大
2、长度相同的字符串再从最高字符位到最低字符位逐字符比较，两个数字的大小关系与第一个不相同的字符位的大小关系相同，如果每个字符位的数值都相同，则两个数相同。 
#include <iostream>
#include <string> 

using namespace std;

int main()
{
     int test_case;
     while (cin >> test_case)
     {
          string num[100];
          for (int i = 0; i < test_case; i++)
          {
               cin >> num[i];
          }
          int min;
          int j, i;
          string temp;
          for (i = 0; i < test_case-1; i++)
          {
               min = i;
               for (j = i + 1; j < test_case; j++)
               {
                    if (num[min].size()> num[j].size())
                   {
                       min = j;
                   }
                   else if (num[min].size()==num[j].size()&&num[min]>num[j])
                  {
                       min = j;
                  }
               }
               temp = num[i];
               num[i] = num[min];
               num[min] = temp;
          }
          for (int i = 0; i < test_case; i++)
          {
               cout << num[i] << endl;
          }
 }
 return 0;
}

编辑于 2017-01-14 23:12:08 回复(0)
C/C++
KDDA十三尧十三头像 KDDA十三尧十三 
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
//采用自定义排序的思想，我写了两个函数
typedef struct number
{
    int len;
    char s[1001];
};

bool operator<(const number n_1,number n_2)
{
    if(n_1.len == n_2.len)
        return strcmp(n_1.s, n_2.s) < 0;
    else
        return n_1.len < n_2.len;
}
int len(char * a)
{
    int count;
    int i = 0;
    
    while(a[i] != '\0')
    {
        count++;
        i++;
    }
    
    return count;
}

int main(void)
{
    int n;
    vector<number> arr;
    
    while(cin >> n)
    {
        arr.clear();
        char c[1001] = {0};
        for(int i = 0;i < n;i++)
        {
            number temp;
            cin >> temp.s;
            int lenth = len(temp.s);
            temp.len = lenth;
            arr.push_back(temp);
        }
        
        sort(arr.begin(),arr.end());
        
        for(int i = 0;i < arr.size();i++)
            cout << arr[i].s << endl;
    }
    return 0;
}

发表于 2021-03-26 23:30:23 回复(0)
用户抉择头像 用户抉择 
#include <stdio.h>
#include <string.h>
typedef struct{
    char s[1000];
    int len;
}Num;
int cmp(const void *a,const void *b)
{
    if((*(Num *)a).len!=(*(Num *)b).len) return (*(Num *)a).len-(*(Num *)b).len;
    else return strcmp((*(Num *)a).s,(*(Num *)b).s);
}
int main()
{
    int n,i;
    while(scanf("%d",&n)!=EOF)
    {
        Num num[n];
        for(i=0;i<n;i++)
        {
            scanf("%s ",&num[i].s);
            num[i].len=strlen(num[i].s);
        }
        qsort(num,n,sizeof(num[0]),cmp);
        for(i=0;i<n;i++) printf("%s\n",num[i].s);
    }
}

发表于 2021-03-12 11:15:06 回复(0)
sSTtaArR头像 sSTtaArR 
/*
*差一点就用高精度实现了 。string 支持比较运算。
*
*/

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e3;
string a[maxn+5];

bool cmp(const string& a, const string& b)
{
    if(a.length() == b.length()) return a < b;
    else return a.length() < b.length();
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n)
    {
        for(int i = 0;i < n; i++) cin >> a[i];
        sort(a,a+n, cmp);
        for(int i = 0;i < n; i++) cout << a[i] << '\n';
    }
    return 0;
}

发表于 2021-01-20 16:03:35 回复(0)
月哟头像 月哟 
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(const string& s1,const string& s2){
    if(s1.size()!=s2.size())
        return s1.size()<s2.size();
    else
        return s1<s2;
}
int main(){
    int n;
    while(cin>>n){
        vector<string> list(n);
        while(n--)
            cin>>list[n];
        sort(list.begin(),list.end(),cmp);
        for(const auto& x:list)
            cout<<x<<endl;
    }
    return 0;
}
C++11，要多短有多短🤣
编辑于 2020-05-03 16:26:38 回复(0)
C/C++
YhX.头像 YhX. 
#include<stdio.h>//1.建立二维字符串数组2.先按照字符串长度排序
#include<string.h>//3.字符串长度相同的时候再按照strcmp排序
int main()
{
    int n,len,i,j;char a[100][1000],b[1000];
    scanf("%d",&n);//输入
    for(i=0;i<n;i++)
        scanf("%s",a[i]);
    for(i=0;i<n-1;i++)//1.首先按照字符长度排序
        for(j=0;j<n-1-i;j++)
            if(strlen(a[j])>strlen(a[j+1]))//字符串长度比较
            {//交换
                strcpy(b,a[j]);strcpy(a[j],a[j+1]);strcpy(a[j+1],b);}
    for(i=0;i<n-1;i++)//2.字符串长度相等的时候按照strcmp排序
        for(j=0;j<n-1-i;j++)
            if(strlen(a[j])==strlen(a[j+1]))
                if(strcmp(a[j],a[j+1])>0)
                {//交换
                    strcpy(b,a[j]);strcpy(a[j],a[j+1]);strcpy(a[j+1],b);}
    for(i=0;i<n;i++)//输出
        printf("%s\n",a[i]);
}

编辑于 2020-03-30 17:40:16 回复(0)
虎牙招聘内推官头像 虎牙招聘内推官 
#include <bits/stdc++.h>
using namespace std;
bool cmp(string a,string b){
	if(a.size()==b.size()){
		return a<b;
	}
	else return a.size()<b.size();
}
int main(){
	int n;
	while(cin>>n){
		string str[n+10];
		for(int i=0;i<n;++i){
			cin>>str[i];
		}
		sort(str,str+n,cmp);
		for(int i=0;i<n;++i){
			cout<<str[i]<<endl;
		}
	}
	return 0;
}

发表于 2020-03-29 13:11:12 回复(0)
Java
LHC0512头像 LHC0512
Java 解法 
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<BigInteger> list = new ArrayList<>();
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) list.add(new BigInteger(scanner.next()));
        Collections.sort(list);
        for (BigInteger i : list) System.out.println(i);
    }
}


发表于 2020-03-18 13:22:39 回复(0)
不屠鸭不改名头像 不屠鸭不改名 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
	int num;
	char s[100];
}str;

int cmp(const void *a, const void *b) {
	if((*(str*)a).num != (*(str*)b).num) {
		return (*(str*)a).num - (*(str*)b).num;
	}
	return strcmp((*(str*)a).s, (*(str*)b).s);
}

int main() {
	int N;
	scanf("%d", &N);
	str s[N];
	for(int i = 0; i < N; i++) {
		scanf("%s", s[i].s);
		s[i].num = strlen(s[i].s);
	}
	qsort(s, N, sizeof(str), cmp);
	for(int i = 0; i < N; i++) {
		printf("%s\n", s[i].s);
	}
	return 0;
}
编辑于 2020-03-14 16:44:13 回复(0)
C/C++
tttddd头像 tttddd 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
bool sortFun(const string& s1,const string& s2){
    return  s1.size()<s2.size()||(s1.size()==s2.size()&&s1<s2);
}
int main(){
    int n;
    string str;
    while(cin>>n){
        vector<string> all;
        for(int i=0;i<n;i++){
            cin>>str;
            all.push_back(str);
        }
        sort(all.begin(),all.end(),sortFun);
        for(string s:all){
            cout<<s<<endl;
        }
    }
    return 0;
}

编辑于 2020-03-11 22:28:08 回复(0)
lllx123头像 lllx123 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

bool cmp(string a, string b)
{
    if(a.size() != b.size())
        return a.size() < b.size();
    else
        return a < b;
}

int main()
{
    int n; cin >> n;
    vector <string> v(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];
    sort(v.begin(), v.end(), cmp);
    for(int i = 0; i < n; i++)
        cout << v[i] << endl;
}    

发表于 2020-02-07 21:16:58 回复(0)
小陈也只是想要一个实习罢了头像 小陈也只是想要一个实习罢了 
//字典序真的不知道怎么搞，还是自带的函数比较好用QAQ
#include<bits/stdc++.h>
using namespace std;
bool cmp(char a[], char b[]) {
	int len1 = strlen(a), len2 = strlen(b);
	if (len1 < len2) return 1;
	else if (len1 == len2)
		return strcmp(a, b) < 0;
	else return 0;
}
int main() {
	int n;
	while (cin >> n) {
		char **ch = new char*[n];
		for (int i = 0; i<n; i++) {
			ch[i] = new char[1001];
			cin >> ch[i];
		}
		sort(ch, ch + n, cmp);
		for (int i = 0; i<n; i++)
			cout << ch[i] << endl;
	}
}

发表于 2020-01-16 11:01:05 回复(0)
C/C++
算法小屁孩头像 算法小屁孩 
#include<bits/stdc++.h>
using namespace std;
struct num{
    char ss[1001];
    int len;
}number[100];
bool cmp(num a,num b){
    if(a.len!=b.len)return a.len<b.len;
    else return strcmp(a.ss,b.ss)<0;
}
int main(){
    int n;
    while(scanf("%d ",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%s ",number[i].ss);
            number[i].len=strlen(number[i].ss);
        }
        stable_sort(number,number+n,cmp);
        for(int i=0;i<n;i++)
            printf("%s\n",number[i].ss);
    }
}
发表于 2019-03-28 15:37:23 回复(0)
C/C++
保洁大哥头像 保洁大哥 
#include <iostream>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;
string Str[100];
bool cmp(string str1,string str2){
if(str1.length()==str2.length()){//长度相等比较字符序列
 return str1<str2;
}
else return str1.length()<str2.length();//不等就比较长度
}
int main()
{
 int n;
 while(cin>>n){
 for(int i=0;i<n;i++)cin>>Str[i];
 sort(Str,Str+n,cmp);
 for(int i=0;i<n;i++){
 cout<<Str[i]<<endl;
 }
 }
 return 0;
}

编辑于 2019-03-15 09:27:01 回复(0)
提交观点

问题信息

字符串 排序
难度：
191条回答 19714浏览

热门推荐

通过挑战的用户

查看代码

相关试题

大整数排序

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号