Java 기수정렬 구현

1 개요[ | ]

Java 기수정렬 구현
자바 기수정렬 구현

import java.util.Collections;
import java.util.Arrays;
public class MyClass {
    static void radix_sort(Integer a[]) {
        radix_sort(a, 10);
    }
    static void radix_sort(Integer a[], int base) {
        int max = Collections.max(Arrays.asList(a));
        int exp, i, j, size = a.length;
        for(exp=1; exp<=max; exp*=base) {
            int count[] = new int[base];
            int output[] = new int[size];
            for(i=0; i<size; i++) count[(a[i]/exp)%base]++;
            for(i=1; i<base; i++) count[i]+=count[i-1];
            for(i=size-1; i>-1; i--) {
                j = (a[i]/exp)%base;
                output[count[j]-1] = a[i];
                count[j]--;
            }
            for(i=0; i<size; i++) a[i]=output[i];
        }
    }
    public static void main(String args[]) {
		Integer arr[] = {9,1,22,4,0,1,22,100,10};
		radix_sort(arr);
		for(int x: arr) System.out.format("%d ",x);
		// 0 1 1 4 9 10 22 22 100 
    }
}

public class MyClass {
	static void radix_counting_sort(int a[], int exp, int base) {
		int i, j, size = a.length;
		int output[] = new int[size];
		int count[] = new int[base];
		for(i=0; i<size; i++) count[(a[i]/exp)%base]++;
		for(i=1; i<base; i++) count[i] += count[i-1];
		for(i=size-1; i>-1; i--) {
			j = (a[i]/exp)%base;
			output[count[j]-1] = a[i];
			count[j]--;
		}
		for(i=0; i<size; i++) a[i] = output[i];
	}
	static void radix_sort(int a[], int base) {
		int max = a[0];
		for(int x: a) if(max<x) max=x;
		for(int exp=1; max/exp>0; exp*=base) radix_counting_sort(a, exp, base);
	}
	static void radix_sort(int a[]) {
	    radix_sort(a, 10);
	}
	public static void main(String[] args) {
		int arr[] = {9,1,22,4,0,1,22,100,10};
		radix_sort(arr);
		for(int x: arr) System.out.format("%d ",x);
		// 0 1 1 4 9 10 22 22 100 
	}
}

2 같이 보기[ | ]