栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

基数排序详讲

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

基数排序详讲

基数排序
  • 一、基数排序是什么
  • 二、基数排序步骤
  • 总结

一、基数排序是什么

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

二、基数排序步骤
  • 1:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零.
  • 2:从最低位开始,依次进行一次排序.

代码如下:

import java.util.Arrays;


public final class RadixSort {
    public static int maxBit(int[] arr) { // 求数组的最大位数
        int max = arr[0]; // 数组最大数
        for (int i = 1; i < arr.length; i++) {
            max = max > arr[i] ? max : arr[i];
        }
        int bit = 1;
        while (max >= 10) {
            max /= 10;
            bit++;
        }
        return bit;
    }

    public static void sort(int[] arr) {
        int maxBit = maxBit(arr);
        int mod = 10;
        int dev = 1;
        for (int i = maxBit; i > 0; i--, mod *= 10, dev *= 10) {

            int[][] counts = new int[10][0];

            for (int j = 0; j < arr.length; ++j) {
            	//并不一定要填零,可以使用下行代码获取到0。
                int bucket = ((arr[j] % mod) / dev);
                counts[bucket] = arrayAppend(counts[bucket], arr[j]);
            }

            int post = 0;
            for(int[] bucket : counts){
                for(int value : bucket){
                    arr[post++] = value;
                }
            }
        }
    }
	
	//扩容数组,并保存数据
    private static int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

代码测试结果:

但这样只能排序自然数,不能排序负数,我们可以将sort方法的int[][] counts = new int[10][0]变为int[][] counts = new int[20][0],0—9存储负数,10—19存储自然数.并把获取最大位数的maxBit方法修改一下

如下列代码所示

public static int maxBit(int[] arr) { // 求数组的最大位数
        int max = arr[0]; // 数组最大数
        int min = arr[0]; // 数组最小数
        for (int i = 1; i < arr.length; i++) {
            max = max > arr[i] ? max : arr[i];
            min = min < arr[i] ? min : arr[i];
        }
        int result = (min + max) > 0 ? max : min;
        int bit = 1;
        while (result >= 10 || result <= -10) {
            result /= 10;
            bit++;
        }
        return bit;
    }


public static void sort(int[] arr) {
        int maxBit = maxBit(arr);
        int mod = 10;
        int dev = 1;
        for (int i = maxBit; i > 0; i--, mod *= 10, dev *= 10) {

            int[][] counts = new int[20][0];
            //int[][] counts = new int[10][0];

            for (int j = 0; j < arr.length; ++j) {
                int bucket = ((arr[j] % mod) / dev) + 10;
                //int bucket = ((arr[j] % mod) / dev);
                counts[bucket] = arrayAppend(counts[bucket], arr[j]);
            }

            int post = 0;
            for(int[] bucket : counts){
                for(int value : bucket){
                    arr[post++] = value;
                }
            }
        }
    }

代码测试结果:

总结

基数排序不是直接根据元素整体的大小进行元素比较,而是将原始列表元素分成多个部分,对每一部分按一定的规则进行排序,进而形成最终的有序列表。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/948105.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号