import java.util.Arrays;
 
public class RadixSort {
 
    /**
     * 取數(shù)x上的第d位數(shù)字
     *
     * @param x
     *            數(shù)
     * @param d
     *            第幾位，從低位到高位
     * @return
     */
    public int digit(long x, long d) {
 
        long pow = 1;
        while (--d > 0) {
            pow *= 10;
        }
        return (int) (x / pow % 10);
    }
 
    /**
     * 基數(shù)排序?qū)崿F(xiàn)，以升序排序（下面程序中的位記錄器count中，從第0個(gè)元素到第9個(gè)元素依次用來(lái)
     * 記錄當(dāng)前比較位是0的有多少個(gè)..是9的有多少個(gè)數(shù)，而降序時(shí)則從第0個(gè)元素到第9個(gè)元素依次用來(lái) 記錄當(dāng)前比較位是9的有多少個(gè)..是0的有多少個(gè)數(shù)）
     *
     * @param arr
     *            待排序數(shù)組
     * @param digit
     *            數(shù)組中最大數(shù)的位數(shù)
     * @return
     */
    public long[] radixSortAsc(long[] arr) {
        // 從低位往高位循環(huán)
        for (int d = 1; d <= getMax(arr); d++) {
            // 臨時(shí)數(shù)組，用來(lái)存放排序過(guò)程中的數(shù)據(jù)
            long[] tmpArray = new long[arr.length];
            // 位記數(shù)器，從第0個(gè)元素到第9個(gè)元素依次用來(lái)記錄當(dāng)前比較位是0的有多少個(gè)..是9的有多少個(gè)數(shù)
            int[] count = new int[10];
            // 開(kāi)始統(tǒng)計(jì)0有多少個(gè)，并存儲(chǔ)在第0位，再統(tǒng)計(jì)1有多少個(gè)，并存儲(chǔ)在第1位..依次統(tǒng)計(jì)到9有多少個(gè)
            for (int i = 0; i < arr.length; i++) {
                count[digit(arr[i], d)] += 1;
            }
            /*
             * 比如某次經(jīng)過(guò)上面統(tǒng)計(jì)后結(jié)果為：[0, 2, 3, 3, 0, 0, 0, 0, 0, 0]則經(jīng)過(guò)下面計(jì)算后 結(jié)果為： [0, 2,
             * 5, 8, 8, 8, 8, 8, 8, 8]但實(shí)質(zhì)上只有如下[0, 2, 5, 8, 0, 0, 0, 0, 0, 0]中
             * 非零數(shù)才用到，因?yàn)槠渌�位不存在，它們分別表示如下：2表示比較位為1的元素可以存放在索引為1、0的
             * 位置，5表示比較位為2的元素可以存放在4、3、2三個(gè)(5-2=3)位置，8表示比較位為3的元素可以存放在
             * 7、6、5三個(gè)(8-5=3)位置
             */
            for (int i = 1; i < 10; i++) {
                count[i] += count[i - 1];
            }
 
            /*
             * 注，這里只能從數(shù)組后往前循環(huán)，因?yàn)榕判驎r(shí)還需保持以前的已排序好的 順序，不應(yīng)該打
             * 亂原來(lái)已排好的序，如果從前往后處理，則會(huì)把原來(lái)在前面會(huì)擺到后面去，因?yàn)樵谔幚砟硞�(gè)
             * 元素的位置時(shí)，位記數(shù)器是從大到到小（count[digit(arr[i], d)]--）的方式來(lái)處
             * 理的，即先存放索引大的元素，再存放索引小的元素，所以需從最后一個(gè)元素開(kāi)始處理。
             * 如有這樣的一個(gè)序列[212,213,312]，如果按照從第一個(gè)元素開(kāi)始循環(huán)的話，經(jīng)過(guò)第一輪
             * 后（個(gè)位）排序后，得到這樣一個(gè)序列[312,212,213]，第一次好像沒(méi)什么問(wèn)題，但問(wèn)題會(huì)
             * 從第二輪開(kāi)始出現(xiàn)，第二輪排序后，會(huì)得到[213,212,312]，這樣個(gè)位為3的元素本應(yīng)該
             * 放在最后，但經(jīng)過(guò)第二輪后卻排在了前面了，所以出現(xiàn)了問(wèn)題
             */
            for (int i = arr.length - 1; i >= 0; i--) {// 只能從最后一個(gè)元素往前處理
                // for (int i = 0; i < arr.length; i++) {//不能從第一個(gè)元素開(kāi)始循環(huán)
                tmpArray[count[digit(arr[i], d)] - 1] = arr[i];
                count[digit(arr[i], d)]--;
            }
 
            System.arraycopy(tmpArray, 0, arr, 0, tmpArray.length);
        }
        return arr;
    }
 
    /**
     * 基數(shù)排序?qū)崿F(xiàn)，以降序排序（下面程序中的位記錄器count中，從第0個(gè)元素到第9個(gè)元素依次用來(lái)
     * 記錄當(dāng)前比較位是0的有多少個(gè)..是9的有多少個(gè)數(shù)，而降序時(shí)則從第0個(gè)元素到第9個(gè)元素依次用來(lái) 記錄當(dāng)前比較位是9的有多少個(gè)..是0的有多少個(gè)數(shù)）
     *
     * @param arr
     *            待排序數(shù)組
     * @return
     */
    public long[] radixSortDesc(long[] arr) {
        for (int d = 1; d <= getMax(arr); d++) {
            long[] tmpArray = new long[arr.length];
            // 位記數(shù)器，從第0個(gè)元素到第9個(gè)元素依次用來(lái)記錄當(dāng)前比較位是9的有多少個(gè)..是0的有多少個(gè)數(shù)
            int[] count = new int[10];
            // 開(kāi)始統(tǒng)計(jì)0有多少個(gè)，并存儲(chǔ)在第9位，再統(tǒng)計(jì)1有多少個(gè)，并存儲(chǔ)在第8位..依次統(tǒng)計(jì)
            // 到9有多少個(gè)，并存儲(chǔ)在第0位
            for (int i = 0; i < arr.length; i++) {
                count[9 - digit(arr[i], d)] += 1;
            }
 
            for (int i = 1; i < 10; i++) {
                count[i] += count[i - 1];
            }
 
            for (int i = arr.length - 1; i >= 0; i--) {
                tmpArray[count[9 - digit(arr[i], d)] - 1] = arr[i];
                count[9 - digit(arr[i], d)]--;
            }
 
            System.arraycopy(tmpArray, 0, arr, 0, tmpArray.length);
        }
        return arr;
    }
 
    private int getMax(long[] array) {
        int maxlIndex = 0;
        for (int j = 1; j < array.length; j++) {
            if (array[j] > array[maxlIndex]) {
                maxlIndex = j;
            }
        }
        return String.valueOf(array[maxlIndex]).length();
    }
 
    public static void main(String[] args) {
        long[] ary = new long[] { 123, 321, 132, 212, 213, 312, 21, 223 };
        RadixSort rs = new RadixSort();
        System.out.println("升 - " + Arrays.toString(rs.radixSortAsc(ary)));
 
        ary = new long[] { 123, 321, 132, 212, 213, 312, 21, 223 };
        System.out.println("降 - " + Arrays.toString(rs.radixSortDesc(ary)));
    }
}

標(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)系。