Java實現基數排序

import java.util.LinkedList;

import java.util.Objects;

/**

基數排序的思想是多關鍵字排序 
@author yuncong 
*/

public class RadixSort {

 /**

基于最低位優先方式對一個整型數組排序，數組中整數是d位數； 
以3位整數排序為例，基于最低位優先方式排序的步驟是：創建十個隊列，用于臨時存儲整數； 
首先按個位排序，按照每個整數的個位數字把整數放進相應隊列，比如120放進第0個隊列， 
124放進第4個隊列，當把所有整數都放進相應隊列后，依次從第零個隊列到第9個隊列收集整數， 
收集得到的所有整數按照個位數大小從小到大排序了； 
然后按十位數排序，以同樣的方式把每個整數按十位數放進相應隊列，對于十位數相同的整數， 
個位數小的整數先放進隊列，因為上一步按個位數的排序導致個位數小的數在前面，接下來， 
依次從第零個隊列到第9個隊列收集整數，整體上先收集十位數小的數，局部到具體隊列中， 
也就是十位數相同的那些數，按照隊列先進先出的特性，個位數小的數先被收集，于是，收集 
得到的所有整數是按照十位和個位組合后的大小從小到大排列的； 
最后按百位數排序，以同樣的方式把每個整數按百位數放進相應隊列，對于百位數相同的整數， 
十位數和個位數組合后小的整數先被放進隊列，因為上一步的排序導致十位數和個位數組合后小 
的整數在前面，接下來，依次從第零個隊列到第9個隊列收集整數，整體上，先收集百位數小 
的數，局部到具體隊列中，也就是百位數相同的那些數，按照隊列的先進先出特性，十位數和 
個位數組合后小的整數先被收集，于是，收集得到的所有整數按從小到大排列。 
一句話總結排序過程，整體上從小到大，局部上也是從小到大。 
@param integers 待排序整數數組 
@param d 待排序數組中整數的位數 
*/

public void sort(Integer[] integers, int d) {

 /** 

創建隊列集合并初始化，集合中的隊列用于存放相應的元素，比如按最低為排序，234應該 
放在queues.get(4)這個隊列中 
*/

LinkedList<LinkedList<Integer>> queues = new LinkedList<>();

for(int i = 0; i < 10; i++){

 LinkedList<Integer> queue = new LinkedList<>();

 queues.add(queue);

}

for(int i = d - 1; i >= 0; i--) {

 // 根據排序key，把元素放進相應的隊列里

 for (int j = 0; j < integers.length; j++) {  
 Integer key = getValueByIndex(integers[j], i);  
 queues.get(key).add(integers[j]);  

 }

 /** 

把元素收回來； 
for循環從頭到尾便利集合 
*/

int index = 0;

for (LinkedList<Integer> linkedList : queues) {

 for (Integer integer : linkedList) {  
 integers[index] = integer;  
 index++;  

 }

 // 清空queues里的所有隊列，為二次利用做準備

 linkedList.clear();

}

}

}

/** 




獲得integer中第index + 1個數字 
@param integer 
@param index 
@return 
*/

public Integer getValueByIndex(Integer integer, int index) {

 Objects.requireNonNull(integer);

 String iString = integer.toString();

 if (index < 0 || index >= iString.length()) {

 throw new IndexOutOfBoundsException();  

}

 String value = iString.substring(index, index + 1);

 return Integer.valueOf(value);

}
public static void main(String[] args) {

 Integer[] integers = new Integer[]{654, 122, 987, 123, 345, 234};

 new RadixSort().sort(integers, 3);

 for (int i = 0; i < integers.length; i++) {

 System.out.println(integers[i]);  

}

}




}  </pre>