java基數排序算法

import java.util.Arrays;

public class RadixSort {

/**
 * 取數x上的第d位數字
 *
 * @param x
 *            數
 * @param d
 *            第幾位，從低位到高位
 * @return
 */
public int digit(long x, long d) {

    long pow = 1;
    while (--d > 0) {
        pow *= 10;
    }
    return (int) (x / pow % 10);
}

/**
 * 基數排序實現，以升序排序（下面程序中的位記錄器count中，從第0個元素到第9個元素依次用來
 * 記錄當前比較位是0的有多少個..是9的有多少個數，而降序時則從第0個元素到第9個元素依次用來 記錄當前比較位是9的有多少個..是0的有多少個數）
 *
 * @param arr
 *            待排序數組
 * @param digit
 *            數組中最大數的位數
 * @return
 */
public long[] radixSortAsc(long[] arr) {
    // 從低位往高位循環
    for (int d = 1; d <= getMax(arr); d++) {
        // 臨時數組，用來存放排序過程中的數據
        long[] tmpArray = new long[arr.length];
        // 位記數器，從第0個元素到第9個元素依次用來記錄當前比較位是0的有多少個..是9的有多少個數
        int[] count = new int[10];
        // 開始統計0有多少個，并存儲在第0位，再統計1有多少個，并存儲在第1位..依次統計到9有多少個
        for (int i = 0; i < arr.length; i++) {
            count[digit(arr[i], d)] += 1;
        }
        /*
         * 比如某次經過上面統計后結果為：[0, 2, 3, 3, 0, 0, 0, 0, 0, 0]則經過下面計算后 結果為： [0, 2,
         * 5, 8, 8, 8, 8, 8, 8, 8]但實質上只有如下[0, 2, 5, 8, 0, 0, 0, 0, 0, 0]中
         * 非零數才用到，因為其他位不存在，它們分別表示如下：2表示比較位為1的元素可以存放在索引為1、0的
         * 位置，5表示比較位為2的元素可以存放在4、3、2三個(5-2=3)位置，8表示比較位為3的元素可以存放在
         * 7、6、5三個(8-5=3)位置
         */
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        /*
         * 注，這里只能從數組后往前循環，因為排序時還需保持以前的已排序好的 順序，不應該打
         * 亂原來已排好的序，如果從前往后處理，則會把原來在前面會擺到后面去，因為在處理某個
         * 元素的位置時，位記數器是從大到到小（count[digit(arr[i], d)]--）的方式來處
         * 理的，即先存放索引大的元素，再存放索引小的元素，所以需從最后一個元素開始處理。
         * 如有這樣的一個序列[212,213,312]，如果按照從第一個元素開始循環的話，經過第一輪
         * 后（個位）排序后，得到這樣一個序列[312,212,213]，第一次好像沒什么問題，但問題會
         * 從第二輪開始出現，第二輪排序后，會得到[213,212,312]，這樣個位為3的元素本應該
         * 放在最后，但經過第二輪后卻排在了前面了，所以出現了問題
         */
        for (int i = arr.length - 1; i >= 0; i--) {// 只能從最后一個元素往前處理
            // for (int i = 0; i < arr.length; i++) {//不能從第一個元素開始循環
            tmpArray[count[digit(arr[i], d)] - 1] = arr[i];
            count[digit(arr[i], d)]--;
        }

        System.arraycopy(tmpArray, 0, arr, 0, tmpArray.length);
    }
    return arr;
}

/**
 * 基數排序實現，以降序排序（下面程序中的位記錄器count中，從第0個元素到第9個元素依次用來
 * 記錄當前比較位是0的有多少個..是9的有多少個數，而降序時則從第0個元素到第9個元素依次用來 記錄當前比較位是9的有多少個..是0的有多少個數）
 *
 * @param arr
 *            待排序數組
 * @return
 */
public long[] radixSortDesc(long[] arr) {
    for (int d = 1; d <= getMax(arr); d++) {
        long[] tmpArray = new long[arr.length];
        // 位記數器，從第0個元素到第9個元素依次用來記錄當前比較位是9的有多少個..是0的有多少個數
        int[] count = new int[10];
        // 開始統計0有多少個，并存儲在第9位，再統計1有多少個，并存儲在第8位..依次統計
        // 到9有多少個，并存儲在第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)));
}

}</pre>