기수 정렬

주어진 수들에서 마지막 자리로 정렬하고 맨 앞자리까지 반복하여 정렬
시간 복잡도는 O(k * n) 이다.

예를들어
1 22 33 14 25 42 가 있으면
1 22 42 33 14 25로 정렬 (1의 자리)
그 뒤에 10의 자리로 정렬
1 14 22 25 33 42가 된다.

1의 자리로 정렬한 상태로 저장되기 때문에
그 다음 자리수를 기준으로 정렬될때
이미 한번 정렬된 상태(완전하지 않더라도)에서 정렬하게 된다.

구현

public static int[] radix(int[] lst, int k) {
        int n = lst.length;

        for (int i = 0; i < k; i++) {
            Queue<Integer>[] num = new LinkedList[10];
            for (int d = 0; d < 10; d++) {
                num[d] = new LinkedList<>();
            }

            // 자릿수별로 분배
            for (int j = 0; j < n; j++) {
                int digit = (lst[j] / (int) Math.pow(10, i)) % 10;
                num[digit].offer(lst[j]);
            }

            // 새로운 배열로 재구성
            int cnt = 0;
            for (int d = 0; d < 10; d++) {
                while (!num[d].isEmpty()) {
                    lst[cnt++] = num[d].poll();
                }
            }
        }

        return lst;
    }

Queue를 활용하여 구현하였다.