JAVA十大排序算法之基数排序详解

2024-09-30 20:29:52

基数排序

常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位0~9数字组成。

基数排序按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，同时每一轮排序都基于上轮排序后的结果；当我们将所有的位排序后，整个数组就达到有序状态。基数排序不是基于比较的算法。

基数是什么意思？对于十进制整数，每一位都只可能是0~9中的某一个，总共10种可能。那10就是它的基，同理二进制数字的基为2；对于字符串，如果它使用的是8位的扩展ASCII字符集，那么它的基就是256。

基数排序有两种方法：

MSD 从高位开始进行排序
LSD 从低位开始进行排序

对于大小范围为0~9的数的组合（若是两位数，就是个位数和十位数的组合），于是可以准备十个桶，然后放到对应的桶里，然后再把桶里的数按照0号桶到9号桶的顺序取出来即可。

代码实现

public class RadixSort {
    public static final int[] ARRAY = {82, 50, 21, 5, 66, 48, 43, 79, 14, 37, 25};
    public static int[] sort(int[] array) {
        if (array.length < 2) return array;
        //根据最大值算出位数
        int max = array[0];
        for (int temp : array) {
            if (temp > max) {
                max = temp;
            }
        }
        //算出位数digit
        int maxDigit = 0;
        while (max != 0) {
            max /= 10;
            maxDigit++;
        }
        //创建桶并初始化
        ArrayList<ArrayList<Integer>> bucket = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            bucket.add(new ArrayList<>());
        }
        //按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，每一轮排序都基于上轮排序后的结果
        int mold = 10;//取模运算
        int div = 1;//获取对应位数的值
        for (int i = 0; i < maxDigit; i++, mold *= 10, div *= 10) {
            for (int j = 0; j < array.length; j++) {
                //获取个位/十位/百位......
                int num = (array[j] % mold) / div;
                //把数据放入到对应的桶里
                bucket.get(num).add(array[j]);
            }
            //把桶中的数据重新写回去，并把桶的元素清空，开始第二轮排序
            int index = 0;
            for (int k = 0; k < bucket.size(); k++) {
                //桶中对应的数据
                ArrayList<Integer> list = bucket.get(k);
                for (int m = 0; m < list.size(); m++) {
                    array[index++] = list.get(m);
                }
                //清除桶
                bucket.get(k).clear();
            }
        }
        return array;
    }
    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

时间复杂度

计数排序算法的时间复杂度是O(N+M)，基数排序算法执行了k次计数排序，所以基数排序算法的时间复杂度为O(K(N+M))。

算法稳定性

从上面的分析可以看出，相同元素会按照顺序放进固定的桶内，取出的时候也是按照顺序取出来的，所以基数排序算法是一种稳定的排序算法。

基数排序 vs 桶排序 vs 计数排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异

基数排序：根据每一位的关键字来分配桶
桶排序：存储一定范围的值
计数排序：每个桶只存储一个类型值，但是数量不限

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容!

Java基数排序radix sort原理及用法解析

基数排序(桶排序)介绍基数排序(radix sort)属于"分配式排序"(distribution sort),又称"桶子法"(bucket sort)或bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些"桶"中,达到排序的作用基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法基数排序(Radix Sort)是桶排序的扩展基数排序是1887年赫尔曼·何乐礼发明的.它是这样实现的:将整数按位数切割成
Python数据结构与算法之常见的分配排序法示例【桶排序与基数排序】

本文实例讲述了Python数据结构与算法之常见的分配排序法.分享给大家供大家参考,具体如下: 箱排序(桶排序) 箱排序是根据关键字的取值范围1~m,预先建立m个箱子,箱排序要求关键字类型为有限类型,可能会有无限个箱子,实用价值不大,一般用于基数排序的中间过程. 桶排序是箱排序的实用化变种,其对数据集的范围,如[0,1) 进行划分为n个大小相同的子区间,每一个子区间为一个桶,然后将n非记录分配到各桶中.因为关键字序列是均匀分布在[0,1)上的,所以一般不会有很多记录落入同一个桶中. 以下的桶排序方
基数排序简介及Java语言实现

基本思想基数排序(RadixSort)是在桶排序的基础上发展而来的,两种排序都是分配排序的高级实现.分配排序(DistributiveSort)的基本思想:排序过程无须比较关键字,而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶:O(n). 基数排序是一种稳定的排序算法,但有一定的局限性: 1.关键字可分解. 2.记录的关键字位数较少,如果密集更好 3.如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序. 先来看一
Java语言实现基数排序代码分享

算法思想:依次按个位.十位...来排序,每一个pos都有分配过程和收集过程,array[i][0]记录第i行数据的个数. package sorting; /** * 基数排序 * 平均O(d(n+r)),最好O(d(n+r)),最坏O(d(n+r));空间复杂度O(n+r);稳定;较复杂 * d为位数,r为分配后链表的个数 * @author zeng * */ public class RadixSort { //pos=1表示个位,pos=2表示十位 public static int g
JS实现的计数排序与基数排序算法示例

本文实例讲述了JS实现的计数排序与基数排序算法.分享给大家供大家参考,具体如下: 计数排序计数排序就是简单的桶排序,一个桶代表数组中一个数出现的个数,所以需要一个和数组数字范围一样大的辅助数组,一般用在范围小于100的排序,时间复杂度为O(n),空间复杂度为数组的数字范围. /** * 范围在 start - end 之间的排序 * 计数排序需要辅助数组,该辅助数组的长度是待排序数组的范围,所以一般用作范围小于100的排序 */ function countSort(arr, start, e
JAVA十大排序算法之基数排序详解

目录基数排序代码实现时间复杂度算法稳定性基数排序 vs 桶排序 vs 计数排序总结基数排序常见的数据元素一般是由若干位组成的,比如字符串由若干字符组成,整数由若干位0~9数字组成. 基数排序按照从右往左的顺序,依次将每一位都当做一次关键字,然后按照该关键字对数组排序,同时每一轮排序都基于上轮排序后的结果:当我们将所有的位排序后,整个数组就达到有序状态.基数排序不是基于比较的算法. 基数是什么意思?对于十进制整数,每一位都只可能是0~9中的某一个,总共10种可能.那10就是它的基,
JAVA十大排序算法之归并排序详解

目录归并排序怎么分怎么治代码实现时间复杂度算法稳定性总结归并排序归并,指合并,合在一起.归并排序(Merge Sort)是建立在归并操作上的一种排序算法.其主要思想是分而治之.什么是分而治之?分而治之就是将一个复杂的计算,按照设定的阈值进行分解成多个计算,然后将各个计算结果进行汇总.即"分"就是把一个大的通过递归拆成若干个小的,"治"就是将分后的结果在合在一起. 若将两个有序集合并成一个有序表,称为2-路归并,与之对应的还有多路归并. 怎么分对于
JAVA十大排序算法之冒泡排序详解

目录冒泡排序代码实现代码实现时间复杂度算法稳定性总结冒泡排序 1.从数组头开始,比较相邻的元素.如果第一个比第二个大(小),就交换它们两个 2.对每一对相邻元素作同样的工作,从开始第一对到尾部的最后一对,这样在最后的元素应该会是最大(小)的数 3.重复步骤1~2,重复次数等于数组的长度,直到排序完成代码实现对下面数组实现排序:{24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9} 代码实现 public class BubbleSort {
JAVA十大排序算法之堆排序详解

目录堆排序知识补充二叉树满二叉树完全二叉树二叉堆代码实现时间复杂度算法稳定性思考总结堆排序这里的堆并不是JVM中堆栈的堆,而是一种特殊的二叉树,通常也叫作二叉堆.它具有以下特点: 它是完全二叉树堆中某个结点的值总是不大于或不小于其父结点的值知识补充二叉树树中节点的子节点不超过2的有序树满二叉树二叉树中除了叶子节点,每个节点的子节点都为2,则此二叉树为满二叉树. 完全二叉树如果对满二叉树的结点进行编号,约定编号从根结点起,自上而下,自左而右.则深度为k的,有
JAVA十大排序算法之快速排序详解

目录快速排序问题思路荷兰国旗问题代码实现时间复杂度算法稳定性总结快速排序快速排序是对冒泡排序的一种改进,也是采用分治法的一个典型的应用.JDK中Arrays的sort()方法,具体的排序细节就是使用快速排序实现的. 从数组中任意选取一个数据(比如数组的第一个数或最后一个数)作为关键数据,我们称为基准数(pivot,或中轴数),然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序,也称为分区(partition)操作. 问题若给定一个无序数组
JAVA十大排序算法之插入排序详解

目录插入排序代码实现动图演示代码实现时间复杂度算法稳定性总结插入排序当我们在玩扑克牌的时候,总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列. 插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的. 1.对于未排序数据(一般取数组的二个元素,把第一个元素当做有序数组),在已排序序列中从左往右扫描,找到相应位置并插入. 2.为了给要插入的元素腾出空
Java 十大排序算法之冒泡排序刨析

目录冒泡排序原理冒泡排序API设计冒泡排序的代码实现冒泡排序的时间复杂度分析冒泡排序原理 ①比较相邻的元素,如果前一个元素比后一个元素大,则交换这两个元素的位置 ②对每一对相邻的元素循环上面的步骤,最终最后面的元素就是最大值冒泡排序API设计类名 Bubble 构造方法 Bubble:创建Bubble对象成员方法 1.public static void sort(Comparable[] a):对数组内元素进行排序 2.private static void greater(C
Java 十大排序算法之选择排序刨析

目录选择排序原理选择排序API设计选择排序代码实现选择排序的时间复杂度选择排序原理 ①假设第一个索引处的元素为最小值,和其他值进行比较,如果当前的索引处的元素大于其他某个索引处的值,则假定其他某个索引处的值为最小值,最后找到最小值所在的索引 ②交换第一个索引处和最小值所在的索引处的值选择排序API设计类名 Selection 构造方法 Selection():创建Selection对象成员方法 1.public static void sort(Comparable[] a):对
Java 十大排序算法之插入排序刨析

目录插入排序原理插入排序API设计插入排序代码实现插入排序的时间复杂度分析插入排序原理 ①把所有元素分成已排序和未排序两组 ②找到未排序组的第一个元素,向已经排序的组中进行插入 ③倒序遍历已经排好的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他元素向后移动一位插入排序API设计类名 Insertion 构造方法 Insertion():创建Insertion对象成员方法 1.public static void sort
Java 十大排序算法之归并排序刨析

目录归并排序原理归并排序API设计归并排序代码实现归并排序的时间复杂度分析归并排序原理 1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止. ⒉将相邻的两个子组进行合并成一个有序的大组. 3.不断的重复步骤2,直到最终只有一个组为止. 归并排序API设计类名 Merge 构造方法 Merge():创建Merge对象成员方法 1.public static void sort(Comparable[] a):对数组内的元素进行