算法逻辑

基数排序（Radix Sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的 无素分配至某些“桶”中，藉以达到排序的作用

以整型数组排序为例，

首先需要声明一个桶数组，一个装载数据的临时数组，然后会按个位进行计数，再之后对计数进行累加，这么做的目的是得到符合当前桶特征的数据最后一个的所在位置。然后，对原数组从后往前遍历，结合桶数组中计算的好位置信息，得到一个新的数组存在临时数组中，之后将临时数组复制到原数组。 做完个位的排序后，还要做十位、百位，这个得看数组中最大值有多少位，它有多位就得轮循几次。

示例代码

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.stream.Collectors;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class RadixSortTest {

    @Test
    void testSort(){
        int[] datas = {101,80,56,61,4536,578,102,975,38,679};
        sort(datas);
        assertEquals("38,56,61,80,101,102,578,679,975,4536", Arrays.stream(datas).mapToObj(item->item+"").collect(Collectors.joining(",")));
    }

    public void sort(int[] datas){
        int length = datas.length;
        int[] tempArr = new int[length];
        int[] radixBucket = new int[10];

        int cycleCount = Integer.toString(getMaxValue(datas)).length();
        int base;
        for(int i=0;i<cycleCount;i++){
            base = (int)Math.pow(10,i);
            for(int j=0;j<length;j++){
                // 相应桶进行计数
                radixBucket[datas[j]/base%10]++;
            }
            // 累加计数
            for(int j=1;j<10;j++){
                radixBucket[j]+=radixBucket[j-1];
            }
            //　为什么要从后往前遍历，因为上面累加的那个值是实际上最后出现那个数所在的位置，这个很关键，如果改成从前往后遍历，就有问题
            for(int j=length-1;j>=0;j--){
                tempArr[--radixBucket[datas[j]/base%10]] = datas[j];
            }
            System.arraycopy(tempArr,0,datas,0,datas.length);
            Arrays.fill(radixBucket,0);
        }
    }

    protected int getMaxValue(int[] datas){
        int maxValue = 0;
        for(int temp:datas){
            if(temp>maxValue){
                maxValue = temp;
            }
        }
        return maxValue;
    }

}

算法总结

平均/最坏/最好时间复杂度： O(k*n)

空间复杂度：O(n) 

稳定性：稳定