import java.util.LinkedList;  
import java.util.Objects;  
  
/** 
 * 基數(shù)排序的思想是多關(guān)鍵字排序 
 * @author yuncong 
 * 
 */  
public class RadixSort {  
    /** 
     * 基于最低位優(yōu)先方式對(duì)一個(gè)整型數(shù)組排序，數(shù)組中整數(shù)是d位數(shù)； 
     * 以3位整數(shù)排序?yàn)槔�，基于最低位�?yōu)先方式排序的步驟是：創(chuàng)建十個(gè)隊(duì)列，用于臨時(shí)存儲(chǔ)整數(shù)； 
     * 首先按個(gè)位排序，按照每個(gè)整數(shù)的個(gè)位數(shù)字把整數(shù)放進(jìn)相應(yīng)隊(duì)列，比如120放進(jìn)第0個(gè)隊(duì)列， 
     * 124放進(jìn)第4個(gè)隊(duì)列，當(dāng)把所有整數(shù)都放進(jìn)相應(yīng)隊(duì)列后，依次從第零個(gè)隊(duì)列到第9個(gè)隊(duì)列收集整數(shù)， 
     * 收集得到的所有整數(shù)按照個(gè)位數(shù)大小從小到大排序了； 
     * 然后按十位數(shù)排序，以同樣的方式把每個(gè)整數(shù)按十位數(shù)放進(jìn)相應(yīng)隊(duì)列，對(duì)于十位數(shù)相同的整數(shù)， 
     * 個(gè)位數(shù)小的整數(shù)先放進(jìn)隊(duì)列，因?yàn)樯弦徊桨磦�(gè)位數(shù)的排序?qū)е聜�(gè)位數(shù)小的數(shù)在前面，接下來， 
     * 依次從第零個(gè)隊(duì)列到第9個(gè)隊(duì)列收集整數(shù)，整體上先收集十位數(shù)小的數(shù)，局部到具體隊(duì)列中， 
     * 也就是十位數(shù)相同的那些數(shù)，按照隊(duì)列先進(jìn)先出的特性，個(gè)位數(shù)小的數(shù)先被收集，于是，收集 
     * 得到的所有整數(shù)是按照十位和個(gè)位組合后的大小從小到大排列的； 
     * 最后按百位數(shù)排序，以同樣的方式把每個(gè)整數(shù)按百位數(shù)放進(jìn)相應(yīng)隊(duì)列，對(duì)于百位數(shù)相同的整數(shù)， 
     * 十位數(shù)和個(gè)位數(shù)組合后小的整數(shù)先被放進(jìn)隊(duì)列，因?yàn)樯弦徊降呐判驅(qū)е率�位�?shù)和個(gè)位數(shù)組合后小 
     * 的整數(shù)在前面，接下來，依次從第零個(gè)隊(duì)列到第9個(gè)隊(duì)列收集整數(shù)，整體上，先收集百位數(shù)小 
     * 的數(shù)，局部到具體隊(duì)列中，也就是百位數(shù)相同的那些數(shù)，按照隊(duì)列的先進(jìn)先出特性，十位數(shù)和 
     * 個(gè)位數(shù)組合后小的整數(shù)先被收集，于是，收集得到的所有整數(shù)按從小到大排列。 
     * 一句話總結(jié)排序過程，整體上從小到大，局部上也是從小到大。 
     * @param integers 待排序整數(shù)數(shù)組 
     * @param d 待排序數(shù)組中整數(shù)的位數(shù) 
     */  
    public void sort(Integer[] integers, int d) {  
        /** 
         * 創(chuàng)建隊(duì)列集合并初始化，集合中的隊(duì)列用于存放相應(yīng)的元素，比如按最低為排序，234應(yīng)該 
         * 放在queues.get(4)這個(gè)隊(duì)列中 
         */  
        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--) {  
            // 根據(jù)排序key，把元素放進(jìn)相應(yīng)的隊(duì)列里  
            for (int j = 0; j < integers.length; j++) {  
                Integer key = getValueByIndex(integers[j], i);  
                queues.get(key).add(integers[j]);  
            }  
            /** 
             * 把元素收回來； 
             * for循環(huán)從頭到尾便利集合 
             */  
            int index = 0;  
            for (LinkedList<Integer> linkedList : queues) {  
                for (Integer integer : linkedList) {  
                    integers[index] = integer;  
                    index++;  
                }  
                // 清空queues里的所有隊(duì)列，為二次利用做準(zhǔn)備  
                linkedList.clear();  
            }  
        }  
    }  
    /** 
     * 獲得integer中第index + 1個(gè)數(shù)字 
     * @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]);  
        }  
    }  
  
}  

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。