1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.*;

class Program {

    public ArrayList<Integer> radixSort(ArrayList<Integer> array) {
        if (array.size() < 2)
            return array;
        int digit = 0;
        int max = Collections.max(array);
        while ((max / Math.pow(10, digit)) > 0) {
            countSort(array, digit);
            digit += 1;
        }
        return array;
    }

    public void countSort(List<Integer> array, int digit) {
        int digitColumn = (int) Math.pow(10, digit);
        int[] countArray = new int[10];
        int[] sortedArray = new int[array.size()];

        for (int i = 0; i < array.size(); i++) {
            int countIdx = (array.get(i) / digitColumn) % 10;
            countArray[countIdx] += 1;
        }

        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }

        for (int i = array.size() - 1; i >= 0; i--) {
            int countIdx = (array.get(i) / digitColumn) % 10;
            countArray[countIdx] -= 1;
            int sortIdx = countArray[countIdx];
            sortedArray[sortIdx] = array.get(i);
        }

        for (int i = 0; i < array.size(); i++) {
            array.set(i, sortedArray[i]);
        }
    }
}

Radix Sort, 也就是每一个digit从小到大去sort.