基数排序与另外七种排序不一样,它是基于分配模式的排序,它有两种模式,第一种MSD最高位优先,LSD最低位优先,这里以最低位优先举例:

  • 第一步,取待排序的序列中的数的个位数,将它们一次放在一个二维数组中,第一维是0-910个数字,第二维是个位数为第一维数的值
  • 第二步,取百位数字,然后在放到二位数组中,依次这样执行

具体代码:

package com.xiaoteng;

import java.util.Arrays;

public class LsdSort {

    // 基数排序
    // 基数排序是基于分配模式的排序方
    // 主要思想(LSD):
    // 第一步,取待排序序列的第一位数字,

    public int[] sort(int[] a) {
        int n = 1;
        int[] c = new int[a.length];
        for (; n <= 100; n *= 10) {
            int[][] b = new int[10][a.length];
            int[] l = new int[10];
            for (int i = 0; i < a.length; i++) {
                // 取位数,n=1就是取个位数,n=10就是取10位数,n=100就是取百位数,以此类推
                int m = (a[i] / n) % 10;
                b[m][l[m]] = a[i];
                l[m]++;
            }

            int k = 0;
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < a.length; j++) {
                    if (b[i][j] != 0) {
                        c[k++] = b[i][j];
                    }
                }
            }

            // 一轮排序结束
            System.out.println("本轮排序结束后:" + Arrays.toString(c));

            a = c;
        }

        return c;
    }


    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 3, 18, 1, 999, 3, 19, 99, 29, 190, 120, 12};
        LsdSort lsdSort = new LsdSort();
        System.out.println("排序结果:" + Arrays.toString(lsdSort.sort(arr)));
    }

}

输出结果:

本轮排序结束后:[190, 120, 1, 1, 1, 2, 12, 3, 3, 18, 999, 19, 99, 29]
本轮排序结束后:[1, 1, 1, 2, 3, 3, 12, 18, 19, 120, 29, 190, 999, 99]
本轮排序结束后:[1, 1, 1, 2, 3, 3, 12, 18, 19, 29, 99, 120, 190, 999]
排序结果:[1, 1, 1, 2, 3, 3, 12, 18, 19, 29, 99, 120, 190, 999]

基数排序非常消耗空间,另外需要知道待排序中的最大位数。