ベースソートテンプレート

Tyvjのクイックソートでテストしてみましたが、1 s AC、データは水のようで、前の4点は1000個以下(どうやって試したのか聞かないでください)
時間の複雑さはO(nm)と言われていますが、まあまあのようです
コード実装

package radixSort;

import java.util.Scanner;

public class radixSort {
    static int N=10000;
    public void print(int[] a,int n){
        for(int i=0;i<=n;i++)
            System.out.print(a[i]+" ");
        /*for(int i=n;i>=0;i--) System.out.print(a[i]+" ");*/
    }
    public int getNum(int x,int t){
        for(int i=1;i<t;i++)
            x/=10;
        return x%10;
    }
    public void radixSort(int[] a,int begin,int end,int maxBit){
        int[] cnt=new int[10];
        int[] buc=new int[end-begin+1];
        for(int d=1;d<=maxBit;d++){
            for(int i=0;i<10;i++)
                cnt[i]=0;
            for(int i=begin;i<=end;i++)
                cnt[getNum(a[i],d)]++;
            for(int i=1;i<10;i++)
                cnt[i]+=cnt[i-1];
            for(int i=end;i>=begin;i--)
                buc[--cnt[getNum(a[i],d)]]=a[i];
            for(int i=0;i<=end;i++)
                a[i+begin]=buc[i];
        }
    }
    public int[] sort(int[] a,int n){
        int maxBit=0;
        for(int i=0;i<=n;i++){
            int cnt=0,val=a[i];
            while(val>0){
                cnt++;
                val/=10;
            }
            maxBit=Math.max(maxBit,cnt);
        }
        radixSort(a,0,n,maxBit);
        return a;
    }
    public static void main(String args[]){
        Scanner in=new Scanner(System.in);
        int[] a=new int[N];
        int n=in.nextInt();
        for(int i=0;i<n;i++)
            a[i]=in.nextInt();
        radixSort radix =new radixSort();
        radix.sort(a,n-1);
        radix.print(a,n-1);
    }
}

仲間たちが付き合っている間に直してください.

public class Main

さもないとCEが惨めになるT_T
それからこの問題の要求は大きいから小さい行まで出力して、注釈の落ちたコードの段を見てすぐ分かりました
By YOUSIKI