精华内容
下载资源
问答
  • 基数排序 java实现

    2018-04-12 11:05:25
    自己写的插入排序,随机产生1000次,每次产生0-1000个数,验证算法正确性。java实现。
  • 基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...
  • 基数排序Java实现

    2021-08-27 13:04:24
    //基数排序 public class RadisSort { public static void main(String[] args) { int[]arr = new int[]{12,5,187,965,23,45,45,88,46,999}; radisSort(arr); System.out.println(Arrays.toString(arr)); } ...

    动图演示
    在这里插入图片描述

    import java.util.Arrays;
    //基数排序
    public class RadisSort {
        public static void main(String[] args) {
            int[]arr = new int[]{12,5,187,965,23,45,45,88,46,999};
            radisSort(arr);
            System.out.println(Arrays.toString(arr));
        }
        public static void radisSort(int[] arr){
            int max=arr[0];
            for(int i=0;i<arr.length;i++){
                if(arr[i]>max){
                    max=arr[i];
                }
            }
            int maxLength=(max+"").length();
            int[][] bucket=new int[10][arr.length];
            int[] tempCount=new int[10];
            int n=1;
            for(int x=0;x<maxLength;x++){
                for (int i=0;i<arr.length;i++){
                    int element=arr[i]/n%10;
                    bucket[element][tempCount[element]]=arr[i];
                    tempCount[element]++;
                }
                int index=0;
                for (int j=0;j< tempCount.length;j++){
                    if(tempCount[j]!=0){
                        for(int k=0;k<tempCount[j];k++){
                            arr[index++]=bucket[j][k];
                        }
                    }
                    tempCount[j]=0;
                }
                n=n*10;
            }
        }
    }
    
    [5, 12, 23, 45, 45, 46, 88, 187, 965, 999]
    
    展开全文
  • (七) 基数排序Java实现

    2020-06-24 14:51:03
    基数排序 核心:从元素的个位开始,按照数字放入0-19(不包含负数0-9)号桶,顺序取出,再按照倒数第二位排序 动图(不考虑负数) 代码(不考虑负数) public static void radixSort(int[] arr) { // 二维数组模拟桶...

    基数排序


    核心:从元素的个位开始,按照数字放入0-19(不包含负数0-9)号桶,顺序取出,再按照倒数第二位排序


    动图(不考虑负数)
    在这里插入图片描述
    代码(不考虑负数)

    public static void radixSort(int[] arr) {
        // 二维数组模拟桶
        int[][] bucket = new int[10][arr.length];
        // 一维数组模拟索引
        int[] bucketCounts = new int[10];
        // 确定数组最大数的位数
        int max = arr[0];
        for (int n = 0; n < arr.length; n++) {
            if (arr[n] > arr[0]) {
                max = arr[n];
            }
        }
        int num = (max + "").length();
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < arr.length; j++) {
                int digit = (int) ((arr[j] / Math.pow(10, i)) % 10);
                bucket[digit][bucketCounts[digit]] = arr[j];
                bucketCounts[digit]++;
            }
            int index = 0;
            for (int k = 0; k < bucketCounts.length; k++) {
                if (bucketCounts[k] != 0) {
                    for (int l = 0; l < bucketCounts[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                bucketCounts[k] = 0;
            }
        }
    }
    

    代码(考虑负数)

    public static void radixSort(int[] arr) {
        int[][] bucket = new int[20][arr.length];
        int[] bucketCounts = new int[20];
        int max = arr[0];
        for (int n = 0; n < arr.length; n++) {
            if (arr[n] > arr[0]) {
                max = arr[n];
            }
        }
        int num = (max + "").length();
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < arr.length; j++) {
                int digit = (int) ((arr[j] / Math.pow(10, i)) % 10)+10;
                bucket[digit][bucketCounts[digit]] = arr[j];
                bucketCounts[digit]++;
            }
            int index = 0;
            for (int k = 0; k < bucketCounts.length; k++) {
                if (bucketCounts[k] != 0) {
                    for (int l = 0; l < bucketCounts[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                bucketCounts[k] = 0;
            }
        }
    }
    
    

    本文动图来源:https://www.cnblogs.com/onepixel/p/7674659.html

    展开全文
  • 基数排序JAVA实现)

    2020-05-14 20:37:36
    (2)基数排序法是属于稳定性的排序,基数排序法是效率高的稳定排序法 (3)基数排序是桶排序的扩展 稳定性: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变...

    基本介绍:
    (1)通过键值得各个位的值,将要排序的元素分配至一些桶中,达到排序的作用
    (2)基数排序法是属于稳定性的排序,基数排序法是效率高的稳定排序法
    (3)基数排序是桶排序的扩展

    稳定性:
    假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]前面,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的,否则称为不稳定的。

    图解:
    在这里插入图片描述
    代码实现:

    public class RadixSort {
    
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		//定义测试数组
    		int[] arr= {53,3,542,748,14,214};
    		radixSort(arr);
    	}
    	
    	public static void radixSort(int[] arr) {
    		//得到数组中的最大数的小标,这样才能知道要循环多少轮
    		int max=0;
    		for(int maxindex=1;maxindex<arr.length;maxindex++) {
    			if(arr[max]<arr[maxindex]) {
    				max=maxindex;
    			}
    		}
    		//得到数字共有几位数
    		int times=(arr[max]+"").length();
    		for(int time=0,n=1;time<times;time++,n*=10) {
    			//创建桶,共有10个桶,每个桶最多有arr.length个数据
    			int[][] bucket=new int[10][arr.length];
    			//用于记录每个桶中有多少数据,用于遍历桶中的数据
    			int[] bucketElementsCount=new int[10];
    			//开始遍历数组
    			for(int i=0;i<arr.length;i++) {
    				int digitOfElement=(int) ((arr[i]/n)%10); //取出对应的位数
    				//将其存入bucket中
    				bucket[digitOfElement][bucketElementsCount[digitOfElement]]=arr[i];
    				bucketElementsCount[digitOfElement]++;
    			}
    			
    			//将bucket中的数据输出到arr中
    			int index=0;
    			for(int i=0;i<bucketElementsCount.length;i++) {
    				if(bucketElementsCount[i]!=0) {
    					for(int j=0;j<bucketElementsCount[i];j++) {
    						arr[index]=bucket[i][j];
    						index++;
    					}
    				}
    			}
    			System.out.println("第"+(time+1)+"轮过后的数组为:"+Arrays.toString(arr));
    		}
    	}
    
    }
    
    

    测试结果:
    第1轮过后的数组为:[542, 53, 3, 14, 214, 748]
    第2轮过后的数组为:[3, 14, 214, 542, 748, 53]
    第3轮过后的数组为:[3, 14, 53, 214, 542, 748]

    展开全文
  • Java 基数排序

    千次阅读 2018-10-08 17:46:45
    基数排序是这样一种排序算法,我们可以从低位(个位)开始,根据个位数排序一次,然后根据十位数排序,再根据百位数进行排序……最终完成整个数组的排序。 对于十进制数字而言,每一位只会是 0~9 这十个数字,我们...

    一、简介

    基数排序是这样一种排序算法,我们可以从低位(个位)开始,根据个位数排序一次,然后根据十位数排序,再根据百位数进行排序……最终完成整个数组的排序。

    对于十进制数字而言,每一位只会是 0~9 这十个数字,我们通常使用桶排序(计数排序)来完成每一位数的排序。桶排序是一种稳定的排序算法,基数排序的正确性依赖一种稳定的排序算法。

    基数排序其实是分 LSD(从低位向高位排序) 和 MSD(从高位向低位排序) 两种。

     

    二、示意图

     

    三、时间复杂度

    基数排序的时间复杂度为 O(n)。

    基数排序使用桶排序对其每一位进行排序,即每一位的排序时间复杂度为 O(n),假设最大的数有 digit 位,则共需要进行 digit * O(n) 次排序。时间复杂度依旧为 O(n)。

     

    四、代码示例

    import java.util.ArrayList;
     
    public class Main {
     
        public static void main(String[] args) {
            int[] arr = new int[] { 321, 1234, 543, 324, 24, 960, 540, 672, 783, 1000 };
            radixSort(arr);
            printArray(arr);
        }
     
        public static void radixSort(int[] arr) {
            int digit = getMaxDigit(arr); // 获取最大的数是多少位
            for (int i = 0; i < digit; i++) {
                bucketSort(arr, i); // 执行 digit 次 bucketSort 排序即可
            }
        }
     
        public static int getMaxDigit(int[] arr) {
            int digit = 1; // 默认只有一位
            int base = 10; // 十进制每多一位,代表其值大了10倍
            for (int i : arr) {
                while (i > base) {
                    digit++;
                    base *= 10;
                }
            }
            return digit;
        }
     
        public static void bucketSort(int[] arr, int digit) {
            int base = (int) Math.pow(10, digit);
            // init buckets
            ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
            for (int i = 0; i < 10; i++) { // 只有0~9这十个数,所以准备十个桶
                buckets.add(new ArrayList<Integer>());
            }
            // sort
            for (int i : arr) {
                int index = i / base % 10;
                buckets.get(index).add(i);
            }
            // output: copy back to arr
            int index = 0;
            for (ArrayList<Integer> bucket : buckets) {
                for (int i : bucket) {
                    arr[index++] = i;
                }
            }
        }
     
        public static void printArray(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
        }
     
    }
    

    执行结果:

    24 321 324 540 543 672 783 960 1000 1234 

     

    五、使用基数排序实现英文单词字母表顺序排序

    基数排序也不局限于对自然数进行排序,它也是一种适合对英文单词排序的一种线性时间(时间复杂度 O(n))的排序算法。

    具体实现跳转至:https://blog.csdn.net/afei__/article/details/82971490

    展开全文
  • Java实现基数排序

    2019-05-01 22:50:40
    基数排序算法原理及实现和优化 基数排序不同于之前所介绍的各类排序,前边介绍到的排序方法或多或少的是通过使用比较和移动记录(元素)来实现排序,而基数排序的实现不需要进行对关键字的比较,只需要对关键字进行...
  • java实现基数排序

    2020-11-04 16:39:21
    基数排序,又称为桶排序的拓展 1,接下来看图理解实现的过程 定义10个桶,相当于定义了一个二维数组,每个桶相当于一个以为数组 以数组中的每个数据的各个位数上的值进行比较,即先各位,再1十位,再百位…一直下去...
  • Java排序算法:插入,冒泡,选择,Shell,快速排序,归并排序,堆排序,桶式排序,基数排序
  • 基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法 基数排序(Radix Sort)是桶排序的扩展 基数排序是1887年赫尔曼何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别...
  • 基数排序 java代码实现

    千次阅读 2016-06-12 21:36:52
    基数排序的基本思想:  设置r个队列(r为进制数,例如十进制r=10),队列编号分别为0,1,2,… ,r-1;首先按数据元素关键字最低位上的数字值依次把n个数据元素分配到r个队列中(入队);  然后按照队列编号...
  • 基数排序Java实现)

    2019-10-22 10:40:28
    import java.lang.reflect.Array;... * 基数排序 * 实现原理:首先定义10个桶,并给桶编号0-9,用于存放数组中待排序的数据。 * 1,第一轮的时候将分别计算出的数组中的各个数据的个位数,将个位数 * 对应的...
  • 基数排序java代码

    2012-08-11 23:31:10
    基数排序java代码,望对大家有帮助,谢谢!
  • 基数排序定义对于数字型或字符型的单关键字,可以看成是由多个数位或多个字符构成的多关键字,可以采用“分配-收集”的办法进行排序,称为基数排序法。实现原理将待排序列(正整数)统一为同样的数位长度,数位较短...
  • import java.util.Arrays; public class RadixSort { public static void main(String[] args) { int[] arr = new int[]{0,879,78,56,4,15,23,11,47,22,100}; System.out.println("排序之前:"); ...
  • Java实现基数排序算法

    2021-02-25 07:31:11
    基数排序”利用以下思想: 整数中的位数取决于: 它的基础 与数据相比要少得多 数字线性增加,但数字对数增加。 开发基数排序可以对大整数排序。它会将整数视为一串数字,因此我们也可以使用“基数排序”对...
  • 基数排序Java

    2019-06-28 15:23:00
    基数排序Java版 题目和我的前几个排序一样 这次是Java版的 代码 + 注释 package com.vdian.qatest.supertagbiz.test.niu; /** * Created by fengyanhua on 2019/6/28. */ public class sortJiSu { public ...
  • 基数排序法(Java实现)

    千次阅读 2018-09-03 17:26:45
    基数排序也是排序算法的一种,老规矩,先来看看百度百科的定义:基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,...
  • 归并排序,快速排序,基数排序(MSD) Java实现以及时间对比 归并排序,快速排序,基数排序(MSD) Java实现以及时间对比 基数排序 基数排序的MSD 在网上找了好多都没有找到有关的代码 从最高位开始放入桶中。number...
  • 基数排序:将字符串按位分割,从低到高逐位比较字符串的每一位,如果个元素的字符串长度不一样,在不足的字符串的低位补0,是基于稳定版的计数排序实现的。 如果要进行位数较多的数字的比较,即要从高位到低位开始...
  • 主要介绍了Java基数排序radix sort原理及用法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • 基数排序java实现

    2016-11-24 10:22:44
    /** * 基数排序 * * @author timmy1 * */public class RadixSort { /** * 实现思路:根据传入的位数进行循环: 第一遍:先循环数组中元素个位数上的数字,先根据个位数进行排序,使用二维数组进行数据存放 * 第二...
  • 基数排序 Java

    2014-11-10 19:24:31
    1、基数排序用于解决待排序记录数目较大,但记录关键字维数较小(如关键字是整数,则维数为10;若关键是字符串,则维数为26); 2、基数排序由分配和收集两部分组成; 3、基数排序实现的关键是下一趟的分配...
  • 该死的基数排序!(java代码实现)

    千次阅读 2019-02-22 21:28:49
    基数排序基本思想 先按数组每个数的个位数进行排序 再将十位数排序 再将百位数排序 以此类推 没有十位数百位数…的补0。当所有位上的数排完序后 整个数组就是有序的。底下有java代码实现。 -----以下是具体实现步骤 ...
  • 基数排序算法 java实现 还有基数排序的原理文档
  • 前面的计数排序是基数排序的基础,思想是按照多个关键字(桶)对元素进行多轮的计数排序 例如对三位数排序时,首先根据个位数进行计数排序,然后十位数,最后根据百分数,最后得到有序的序列 import java.util....
  • 基数排序-java

    2020-04-12 17:02:23
    1. 基数排序 1.1 基数排序的基本介绍 1.2 基数排序思想 1.3 基数排序的时间复杂度和空间复杂度等 2. 代码演示 3. 图片引用 1. 基数排序 1.1 基数排序的基本介绍 桶排序的一种,是通过数据的各个位的值,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,640
精华内容 9,856
关键字:

基数排序java

java 订阅