基数排序 | FloatingDream🌞

Radix Sort 排序算法——基数排序

基本概念

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
基数排序(Radix Sort)是桶排序的扩展

基本思想

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

思路图解

代码

ps:不支持负数

算法代码

基数排序是根据元素的某位数的值进行划分，将对应元素划分到桶里，然后在存入原数组，不断循环以上做法，循环次数是最大元素的位数，当循环完后，顺序也就出来了。从代码上看，也会发现该算法是明显的空间换时间，但明显会感觉到它的循环次数少比较也只在判断时比较，因此达到时间很短。

//基数排序方法
public static void radixSort(int[] arr) {

    //首先找最大值
	int max = Arrays.stream ( arr ).max ( ).getAsInt ( );
    //得到最大数是几位数
    int maxLength = ( max + "" ).length ( );

    //定义一个二维数据，表示10个桶，每个桶就是一维数组
    int[][] bucket = new int[ 10 ][ arr.length ];
    //为了记录每个桶中实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
    //比如bucketindex[0],就记录的是bucket[0]桶的放入数据个数
    int[] bucketIndex = new int[ 10 ];

    //这里使用循环来控制每一轮
    for ( int i = 0,n=1; i < maxLength; i++ ,n*=10){

        for ( int j = 0 ; j < arr.length ; j++ ) {
            //取出每个元素对应位的值
            int digitOfElement = arr[ j ] /n % 10;  //
            //放入对应的桶
            bucket[ digitOfElement ][ bucketIndex[ digitOfElement ] ] = arr[ j ];  //根据元素的个位数，放到对应的桶中，用bucketIndex[ digitOfElement ]的方式记录在桶中存放的位置
            bucketIndex[ digitOfElement ]++; //自加加使指针下标往后移动，来等待下一个存储
        }

        //按照加入元素的先后顺序取出
        int index = 0;
        //遍历每一个桶，并把桶中数据，放入原数组
        for ( int x = 0 ; x < bucket.length ; x++ ) {
            //如果桶里有数据我们才放入

            for ( int y = 0 ; y < bucketIndex[ x ] ; y++ ) {
                arr[ index ] = bucket[ x ][ y ];
                index++;
            }
            //非常重要，会影响后面后面轮数的指针下标
            bucketIndex[ x ] = 0;
        }
        System.out.println ( "第" + ( i + 1 ) + "轮结果" + Arrays.toString ( arr ) );
    }
}

性能测试

public class RadixSorting {
    public static void main ( String[] args ) {
//        int[] arr = {53, 3, 542, 748, 14, 214};
//        radixSort ( arr );
        int [] arr = new int[ 80000000 ];
        randomArr ( arr );
        System.out.println ( "基数排序8000万数据所用时间" );
        String date1String = Date ( );
        System.out.println ( "排序前时间是：" + date1String );
        radixSort ( arr );
        String date2String = Date ( );
        System.out.println ( "排序后时间是：" + date2String );
    }

    //基数排序方法
    public static void radixSort(int[] arr) {

        //首先找最大值
        int max = Arrays.stream ( arr ).max ( ).getAsInt ( );
//        int max = arr[ 0 ];
//        for ( int i=0;i<arr.length;i++ ) {
//            if ( arr[ i ] > max ) {
//                max = arr[ i ];
//            }
//        }
        //得到最大数是几位数
        int maxLength = ( max + "" ).length ( );

        //定义一个二维数据，表示10个桶，每个桶就是一维数组
        int[][] bucket = new int[ 10 ][ arr.length ];
        //为了记录每个桶中实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //比如bucketindex[0],就记录的是bucket[0]桶的放入数据个数
        int[] bucketIndex = new int[ 10 ];

        //这里使用循环来控制每一轮
        for ( int i = 0,n=1; i < maxLength; i++ ,n*=10){

            for ( int j = 0 ; j < arr.length ; j++ ) {
                //取出每个元素对应位的值
                int digitOfElement = arr[ j ] /n % 10;  //
                //放入对应的桶
                bucket[ digitOfElement ][ bucketIndex[ digitOfElement ] ] = arr[ j ];  //根据元素的个位数，放到对应的桶中，用bucketIndex[ digitOfElement ]的方式记录在桶中存放的位置
                bucketIndex[ digitOfElement ]++; //自加加使指针下标往后移动，来等待下一个存储
            }

            //按照加入元素的先后顺序取出
            int index = 0;
            //遍历每一个桶，并把桶中数据，放入原数组
            for ( int x = 0 ; x < bucket.length ; x++ ) {
                //如果桶里有数据我们才放入

                for ( int y = 0 ; y < bucketIndex[ x ] ; y++ ) {
                    arr[ index ] = bucket[ x ][ y ];
                    index++;
                }
                //非常重要，会影响后面后面轮数的指针下标
                bucketIndex[ x ] = 0;
            }
//            System.out.println ( "第" + ( i + 1 ) + "轮结果" + Arrays.toString ( arr ) );
        }

        /*//第一轮排序（针对元素个数进行排序）
        for ( int j = 0 ; j < arr.length ; j++ ) {
            int digitOfElement = arr[ j ] % 10;  //元素的个位数
            //放入对应的桶
            bucket[ digitOfElement ][ bucketIndex[ digitOfElement ] ] = arr[ j ];  //根据元素的个位数，放到对应的桶中，用bucketIndex[ digitOfElement ]的方式记录在桶中存放的位置
            bucketIndex[ digitOfElement ]++; //自加加使指针下标往后移动，来等待下一个存储
        }

        //按照加入元素的先后顺序取出
        int index = 0;
        //遍历每一个桶，并把桶中数据，放入原数组
        for ( int x = 0 ; x < bucket.length ; x++ ) {
            //如果桶里有数据我们才放入

            for ( int y = 0 ; y < bucketIndex[ x ] ; y++ ) {
                arr[ index ] = bucket[ x ][ y ];
                index++;
            }
            //非常重要，会影响后面后面轮数的指针下标
            bucketIndex[ x ] = 0;
        }
        System.out.println ( Arrays.toString( arr));

        //第二轮排序（针对元素百位数进行排序）
        for ( int j = 0 ; j < arr.length ; j++ ) {
            int digitOfElement = arr[ j ] /10 % 10;  //元素的百位数
            //放入对应的桶
            bucket[ digitOfElement ][ bucketIndex[ digitOfElement ] ] = arr[ j ];  //根据元素的个位数，放到对应的桶中，用bucketIndex[ digitOfElement ]的方式记录在桶中存放的位置
            bucketIndex[ digitOfElement ]++; //自加加使指针下标往后移动，来等待下一个存储
        }

        //按照加入元素的先后顺序取出
        index = 0;
        //遍历每一个桶，并把桶中数据，放入原数组
        for ( int x = 0 ; x < bucket.length ; x++ ) {
            //如果桶里有数据我们才放入

            for ( int y = 0 ; y < bucketIndex[ x ] ; y++ ) {
                arr[ index ] = bucket[ x ][ y ];
                index++;
            }
            //非常重要，会影响后面后面轮数的指针下标
            bucketIndex[ x ] = 0;
        }
        System.out.println ( Arrays.toString( arr));*/


    }

    private static void randomArr ( int[] arr ) {
        for ( int i = 0 ; i < arr.length ; i++ ) {
            arr[ i ] = (int) ( Math.random ( ) * 8000000 );  //会生成【0，8000000）直接的数
        }
    }

    /**
     * 将此时调用函数的时间格式化打出来
     *
     * @return 年-月-日 时-分秒
     */
    private static String Date ( ) {
        Date date1 = new Date ( );  //调函数的当前时间
        SimpleDateFormat simpleFormatter = new SimpleDateFormat ( "HH:mm:ss" );//格式化
        return simpleFormatter.format ( date1 );
    }
}