1 package sorts; 2  3 import java.util.ArrayList; 4 import java.util.HashMap; 5 import java.util.LinkedList; 6 import java.util.List; 7 import java.util.Map; 8 import java.util.Queue; 9 import java.util.Set;10 11 import test.RSHelper;12 13 public class RadixSort {14     15     private RadixSort() {16         17     }18     19     public static <K extends Comparable<K>, T> void sort(RSHelper<K, T> helper) {20         // initialize21         Set<K> keys = helper.keys();22         Map<K, Queue<T>> map = new HashMap<K, Queue<T>>();23         List<Queue<T>> queues = new ArrayList<Queue<T>>();24         for (int i = 0; i < keys.size(); i++) {25             queues.add(new LinkedList<T>());26         }27         int i = 0;28         for (K k : keys) {29             map.put(k, queues.get(i++));30         }31         int dataLength = helper.dataLength();32         // sort33         T data = http://www.mamicode.com/null;34         K key = null;35         for (i = 0; i < dataLength; i++) {36             while (helper.hasNext()) {37                 data =http://www.mamicode.com/ helper.next();38                 key = helper.key(data, i);39                 map.get(key).offer(data);40             }41             for (Queue<T> queue : queues) {42                 while (!queue.isEmpty()) {43                     data =http://www.mamicode.com/ queue.poll();44                     helper.put(data);45                 }46             }47         }48     }49     50 }

 1 package test; 2  3 import java.util.Set; 4  5 public interface RSHelper<K extends Comparable<K>, T> { 6     /** 7      * @return true if there‘s still data available, false otherwise. 8      * */ 9     boolean hasNext();10     /**11      * @return the next data. 12      * */13     T next(); 14     /**15      * @param index starts from 0 (the lowest index)16      * @param data the data where the key is from.17      * @return the key at the specified index in the data.18      * */19     K key(T data, int index);20     /**21      * @return the keys that will be involved while sorting. The set must be sorted according22      * to the natural order of the keys.23      * */24     Set<K> keys();25     26     /**27      * @return the number of keys in one data object.28      * */29     int dataLength();30     /**31      * Put the data back to the client, in a sequential manner32      * that the client can receive the result of one round of sorting.33      * */34     void put(T data);35 }

  1 package test;  2   3 import java.util.Arrays;  4 import java.util.Random;  5 import java.util.Set;  6 import java.util.TreeSet;  7   8 import sorts.RadixSort;  9  10 class DataType { 11      12     Integer[] arr = new Integer[3]; 13     public DataType(int a, int b, int c) { 14         if (a > 9 || b > 9 || c > 9) { 15             throw new IllegalArgumentException("Argument should be no more than 9."); 16         } 17         arr[0] = a; 18         arr[1] = b; 19         arr[2] = c; 20     } 21     int get(int index) { 22         return arr[3-index-1]; 23     } 24     void set(int index, int value) { 25         arr[3-index-1] = value; 26     } 27     static int dataLength() { 28         return 3; 29     } 30     @Override 31     public String toString() { 32         return arr[0] + "" + arr[1] + "" + arr[2]; 33     } 34 } 35  36 class MyRSHelper implements RSHelper<Integer, DataType> { 37      38     static Set<Integer> keySet = new TreeSet<>(); 39     static { 40         for (int i = 0; i < 10; i++) { 41             keySet.add(i); 42         } 43     } 44      45     int index = 0; 46     DataType[] arr = new DataType[10]; 47      48     public MyRSHelper() { 49         int bound = 10; 50         Random random = new Random(); 51         for (int i = 0; i < arr.length; i++) { 52             arr[i] = new DataType(random.nextInt(bound),  53                     random.nextInt(bound), random.nextInt(bound)); 54         } 55     } 56  57     @Override 58     public boolean hasNext() { 59         return (index < arr.length); 60     } 61  62     @Override 63     public DataType next() { 64         DataType result = arr[index]; 65         arr[index] = null; 66         index++; 67         return result; 68     } 69  70     @Override 71     public Integer key(DataType data, int index) { 72         return data.get(index); 73     } 74  75     @Override 76     public Set<Integer> keys() { 77         return keySet; 78     } 79  80     @Override 81     public int dataLength() { 82         return DataType.dataLength(); 83     } 84  85     @Override 86     public void put(DataType data) { 87         if (index == arr.length) { 88             index = 0; 89         } 90         arr[index++] = data; 91         if (index == arr.length) { 92             index = 0; 93         } 94     } 95      96     @Override 97     public String toString() { 98         return Arrays.toString(arr); 99     }100 101 }102 103 public class TestRadixSort {104     // test105     public static void main(String[] args) {106         MyRSHelper helper = new MyRSHelper();107         RadixSort.sort(helper);108         System.out.println(helper);109     }110 }