基数排序

/**
    * @param number 给定一个数字
    * @param order 指定要获取的位数，取值应该大于0（个位用1表示，十位用2表示，以此类推）
    * @return 返回指定位置上的数字，合理的返回结果是0~9共十种可能的结果
    */
public static int digit(int number, int order) {
    int digit = number;
    while (--order > 0) digit /= 10;
    return digit % 10;
}

/**
    * 返回给定数字的位数
    */
public static int maxOrder(int number) {
    int order = 1;
    while ((number /= 10) != 0) order++;
    return order;
}

public static void radixSort(int[] numbers) {
    int radix = 10;
    int size = numbers.length;
    int[][] bucket = new int[radix][size];  // 桶数组，radix为桶的个数，size为桶的大小
    int[] counter = new int[radix];  // 记录每个桶中保存的数据个数

    int maxNum = numbers[0];
    for (int num: numbers)
        if (num > maxNum) maxNum = num;
    int maxOrder = maxOrder(maxNum);  // 比较序列中最大数的位数

    // 基数排序分为分配过程和收集过程两大步
    for (int i = 1; i <= maxOrder; i++) {
        // 分配过程（数据序列装入桶中）
        for (int j = 0; j < size; j++) {
            int row = digit(numbers[j], i);
            int col = counter[row]++;
            bucket[row][col] = numbers[j];
        }
        // 收集过程（从桶中取出数据）
        int j = 0;
        for (int r = 0; r < radix; r++) {
            for (int c = 0; c < counter[r]; c++)
                numbers[j++] = bucket[r][c];
            counter[r] = 0;
        }
    }
}

public static void main(String[] args) {
    int[] numbers = {73, 22, 93, 43, 55, 14, 28, 9};
    radixSort(numbers);
    System.out.println(Arrays.toString(numbers));
}