基数排序

基数排序是一种可以按优先级排序的排序方法，例如扑克牌或者麻将的排序，先按照花色排序，再按照点数排序。

描述：

1、取数组最大值的位数；
2、从数据最低位开始排序，这里是从个位开始排，得到新的数组；
3、再按次低位排序，位数不够就按0计算；
4、重复以上过程直到排到最高位。

动画：

基数排序.gif

代码：

    /**
     * @param array   目标数组
     * @param highest 最高位有几位
     */
    private void radixSort(int[] array, int highest) {
        // 排序依据是哪一位
        int high = 1;
        while (high <= highest) {
            LinkedList<Integer>[] bucket = new LinkedList[10];
            for (int data : array) {
                // 排序依据的那一位对应的值 如：123 当前取十位的值为排序依据，十位上的值是2
                int highNum = (data / (int) Math.pow(10, high - 1)) % 10;
                LinkedList<Integer> list = bucket[highNum];
                if (list != null) {
                    list.add(data);
                } else {
                    list = new LinkedList<>();
                    list.add(data);
                    bucket[highNum] = list;
                }
            }
            int arrayIndex = 0;
            for (LinkedList<Integer> list : bucket) {
                while (list != null && list.size() > 0) {
                    array[arrayIndex++] = list.pop();
                }
            }
            high++;
        }

    }

测试代码：

    public void test() {
        int[] array = new int[]{628, 76, 549, 0, 32, 258, 322, 899, 6, 744, 132, 521, 54};
        radixSort(array, 3);
        for (int data : array) {
            System.out.print(data + " ");
        }
    }

运行结果：

0 6 32 54 76 132 258 322 521 549 628 744 899