基数排序

基数排序（radix sort）属于“分配式排序”，又称“桶子法”或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

实现起来是将数组中的数进行位比较，放入相应的桶中，之后再取出的方法

代码如下

package com.company.Radix;

import java.util.Arrays;

/**
 * @author : CLEAR Li
 * @version : V1.0
 * @className : RadixSort
 * @packageName : com.company.Radix
 * @description : 一般类
 * @date : 2020-05-06 10:23
 **/
public class RadixSort {
    public static void main(String[] args) {
      int[] arr = new  int[]{23,6,164,84,96,1,34,777};
      radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void radixSort(int[] arr){
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]>max){
                max=arr[i];
            }
        }
        System.out.println(max);
        //求最大数字是几位数
        int maxLength = (max + "").length();
       //用于存储临时存储数据的数组
        int [][]temp = new int[10][arr.length];
        //用于记录在相应的数组中妨的数字的数量
        int[] counts = new int[10];
        for (int i = 0, n = 1; i < maxLength; i++,n*=10) {
            for (int j=0;j<arr.length;j++){
               //计算余数
                int ys= arr[j]/n%10;
                temp[ys][counts[ys]]=arr[j];
                counts[ys]++;
            }
            //记录取的元素药房的位置
            int index = 0;
            //把数字取出来
            for (int j = 0; j < counts.length; j++) {
                //记录数量的数组中当前余数记录的数量不为零
                if (counts[j]!=0){
                   //循环取出元素
                    for (int k = 0; k < counts[j]; k++) {
                        //取出元素
                        arr[index]=temp[j][k];
                        index++;
                    }
                    //把数量值为0
                    counts[j]=0;
                }
            }

        }

    }
}

测试结果