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

基数排序(桶排序)介绍

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用

基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法

基数排序(Radix Sort)是桶排序的扩展

基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较。

基数排序基本思想

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

特点

空间换时间,稳定

代码

package cn.guizimo.sort;

import java.util.Arrays;

public class RadixSort {
  public static void main(String[] args) {
    int arr[] = {53,45,6,378,15,234,78};
    System.out.println("排序前");
    System.out.println(Arrays.toString(arr));
    radixSort(arr);
    System.out.println("排序后");
    System.out.println(Arrays.toString(arr));
  }

  public static void radixSort(int arr[]) {
    //获取最大位数
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
      if (arr[i] > max) {
        max = arr[i];
      }
    }
    //计算位数
    int maxLength = (max + "").length();

    int[][] bucket = new int[10][arr.length];
    int[] bucketElemtCounts = new int[10];

    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
      for (int j = 0; j < arr.length; j++) {
        int digitOfElemt = arr[j] / n % 10;
        bucket[digitOfElemt][bucketElemtCounts[digitOfElemt]] = arr[j];
        bucketElemtCounts[digitOfElemt]++;
      }
      int index = 0;
      for (int k = 0; k < bucketElemtCounts.length; k++) {
        if (bucketElemtCounts[k] != 0) {
          for (int l = 0; l < bucketElemtCounts[k]; l++) {
            arr[index++] = bucket[k][l];
          }
        }
        bucketElemtCounts[k] = 0;
      }
      System.out.println("第"+(i+1)+"轮排序");
      System.out.println(Arrays.toString(arr));
    }

  }
}

测试

测试速度

package cn.guizimo.sort;

import java.util.Arrays;

public class RadixSort {
  public static void main(String[] args) {
    int max = 80000;
    int[] arr = new int[max];
    for (int i = 0; i < max; i++) {
      arr[i] = (int)(Math.random() * 80000);
    }
    long date1 = System.currentTimeMillis();
    radixSort(arr);
    long date2 = System.currentTimeMillis();
    System.out.println("位移式希尔排序"+max+"数组的时间为:"+(date2-date1));
  }

  public static void radixSort(int arr[]) {
    //获取最大位数
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
      if (arr[i] > max) {
        max = arr[i];
      }
    }
    //计算位数
    int maxLength = (max + "").length();

    int[][] bucket = new int[10][arr.length];
    int[] bucketElemtCounts = new int[10];

    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
      for (int j = 0; j < arr.length; j++) {
        int digitOfElemt = arr[j] / n % 10;
        bucket[digitOfElemt][bucketElemtCounts[digitOfElemt]] = arr[j];
        bucketElemtCounts[digitOfElemt]++;
      }
      int index = 0;
      for (int k = 0; k < bucketElemtCounts.length; k++) {
        if (bucketElemtCounts[k] != 0) {
          for (int l = 0; l < bucketElemtCounts[k]; l++) {
            arr[index++] = bucket[k][l];
          }
        }
        bucketElemtCounts[k] = 0;
      }
    }
  }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

时间: 2020-06-26

c#基数排序Radix sort的实现方法

经典排序算法 - 基数排序Radix sort 原理类似桶排序,这里总是需要10个桶,多次使用 首先以个位数的值进行装桶,即个位数为1则放入1号桶,为9则放入9号桶,暂时忽视十位数 例如 待排序数组[62,14,59,88,16]简单点五个数字 分配10个桶,桶编号为0-9,以个位数数字为桶编号依次入桶,变成下边这样 |  0  |  0  | 62 |  0  | 14 |  0  | 16 |  0  |  88 | 59 | |  0  |  1  |  2  |  3  |  4 | 

Java实体类中Set按照对象的某个字段对set排序

背景: User实体类 有个属性是 Set<PositionChange> 职位变更字段 如下: PositionChange实体类 有个属性是positionStartDate 什么时候开始任职此职务的字段 现在有一个需求,想在查询出 User这个对象的时候 ,可以获取到 Set<PositionChange>中 用户最新任职的一条岗位记录,也就是展示当前用户所处的岗位信息. 但是,Set始终的无序的,想要取出Set中PositionChange的positionStartDat

java实现6种字符串数组的排序(String array sort)

注意,本文不是字符串排序,是字符串数组的排序. 方法分别是: 1.低位优先键索引排序 2.高位优先建索引排序 3.Java自带排序(经过调优的归并排序) 4.冒泡排序 5.快速排序 6.三向快速排序 时间复杂度: 最慢的肯定是冒泡,O(n的平方) 最快的是快速排序,平均 O(nlogn) 低位优先,O(nW),W是字符串长度,在字符串长度较短情况下和快速排序时间应该很接近 高位优先,O(n) - O(nW) 三向快速排序,O(n) - O(nW) 本文中使用的例子是一个5757行的随机字符串数组

Java实现储存对象并按对象某属性排序的几种方法示例

本文实例讲述了Java实现储存对象并按对象某属性排序的几种方法.分享给大家供大家参考,具体如下: 在编程的时候,经常会出现对某一种类的对象们按照某属性进行自定义的排序,比如:学生对象按照age大小排序. 有一种方法就是把age单独提出来排好序,然后按照ages数组的顺序把students重存一次.但是这样太繁琐了,有没有更好的方法呢? 有滴~ 第一种,可以实现边添加边排序,需要用到TreeSet. 第二种,用数组存放对象们,但是不需单独取出某属性排列好再重存,而是在原数组上用比较器重新排一次序.

java8 stream自定义分组求和并排序的实现

本文主要介绍了java8 stream自定义分组求和并排序的实现,分享给大家,具体如下: public static void main(String[] args) { List<GroupDetailDTO> list = new ArrayList<>(); GroupDetailDTO dto1 = new GroupDetailDTO(); dto1.setHeadsetId(1); dto1.setTime("2020-01-03"); dto1.s

Java8 Comparator排序方法实例详解

这篇文章主要介绍了Java8 Comparator排序方法实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Java8 中 Comparator 接口提供了一些静态方法,可以方便于我们进行排序操作,下面通过例子讲解下如何使用 对整数列表排序(升序) List<Integer> list = Arrays.asList(1, 4, 2, 6, 2, 8); list.sort(Comparator.naturalOrder()); Sys

PHP排序算法之基数排序(Radix Sort)实例详解

本文实例讲述了PHP排序算法之基数排序(Radix Sort).分享给大家供大家参考,具体如下: 基数排序在<大话数据结构>中并未讲到,但是为了凑齐八大排序算法,我自己通过网络学习了这个排序算法,并给大家分享出来. 基本思想: 基数排序(radix sort)属于"分配式排序"(distribution sort),又称"桶子法"(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶&quo

Java sort集合排序的两种方式解析

这篇文章主要介绍了Java sort集合排序的两种方式解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Comparable和Comparator public static <T> void sort(List<T> list); 将集合中的数据按照默认规则进行排序 (我们在自己的类里面实现Comparabl接口方法compareTo) public static <T> void sort(List<T&g

深入解析Radix Sort基数排序算法思想及C语言实现示例

基本思想: 将待排数据中的每组关键字依次进行桶分配. 具体示例: 278.109.063.930.589.184.505.269.008.083 我们将每个数值的个位,十位,百位分成三个关键字: 278 -> k1(个位)=8,k2(十位)=7,k3=(百位)=2. 然后从最低位个位开始(从最次关键字开始),对所有数据的k1关键字进行桶分配(因为,每个数字都是 0-9的,因此桶大小为10),再依次输出桶中的数据得到下面的序列. 930.063.083.184.505.278.008.109.58

Java8 Comparator: 列表排序的深入讲解

在本文中,我们将看到几个关于如何在Java 8中对List进行排序的示例. 1.按字母顺序排序字符串列表 List<String> cities = Arrays.asList( "Milan", "london", "San Francisco", "Tokyo", "New Delhi" ); System.out.println(cities); //[Milan, london, San

Python 列表排序方法reverse、sort、sorted详解

python语言中的列表排序方法有三个:reverse反转/倒序排序.sort正序排序.sorted可以获取排序后的列表.在更高级列表排序中,后两中方法还可以加入条件参数进行排序. reverse()方法 将列表中元素反转排序,比如下面这样 >>> x = [1,5,2,3,4] >>> x.reverse() >>> x [4, 3, 2, 5, 1] reverse列表反转排序:是把原列表中的元素顺序从左至右的重新存放,而不会对列表中的参数进行排序

Python对列表排序的方法实例分析

本文实例讲述了Python对列表排序的方法.分享给大家供大家参考.具体分析如下: 1.sort()函数 sort()函数使用固定的排序算法对列表排序.sort()函数对列表排序时改变了原来的列表,从而让其中的元素能按一定的顺序排列,而不是简单的返回一个已排序的列表副本. 注意sort()函数改变原来的列表,函数返回值是空值即None.因此,如果需要一个已排好序的列表副本,同时又要保留原有列表不变的时候,就不能直接简单的使用sort()函数.为了实现上述功能使用sort()的方法是:先获取列表X的

python实现忽略大小写对字符串列表排序的方法

本文实例讲述了python实现忽略大小写对字符串列表排序的方法,是非常实用的技巧.分享给大家供大家参考.具体分析如下: 先来看看如下代码: string = ''' the stirng Has many line In THE fIle jb51 net ''' list_of_string = string.split() print list_of_string #将字符串分离开,放入列表中 print '*'*50 def case_insensitive_sort(liststring

利用jQuery对无序列表排序的简单方法

利用jQuery对无序列表排序的原理是:获取到无序列表中的所有列表项,并转成数组形式,使用JavaScript函数对其进行排序后再次输出.其中使用到的jQuery函数有ready().get().text().each().append()和JavaScript函数sort(). 1.jQuery函数介绍 (1)jQuery函数get()--获取匹配元素集合 该函数取得所有匹配元素的一种向后兼容的方式(不同于jQuery对象,实际上是元素数组).其语法形式如下: object.get() 注:如

MySQL 按指定字段自定义列表排序的实现

问题描述 大家都知道, MySQL 中按某字段升序排列的 SQL 为 (以 id 为例,下同): SELECT * FROM `MyTable` WHERE `id` IN (1, 7, 3, 5) ORDER BY `id` ASC 降序排列的 SQL 为: SELECT * FROM `MyTable` WHERE `id` IN (1, 7, 3, 5) ORDER BY `id` DESC 有时以上排序并不能满足我们的需求. 例如, 我们想要按 id 以 5, 3, 7, 1 的顺序排列

Python cookbook(数据结构与算法)通过公共键对字典列表排序算法示例

本文实例讲述了Python通过公共键对字典列表排序算法.分享给大家供大家参考,具体如下: 问题:想根据一个或多个字典中的值来对列表排序 解决方案:利用operator模块中的itemgetter()函数对这类结构进行排序是非常简单的. # Sort a list of a dicts on a common key rows = [ {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}, {'fname': 'David', 'lname': 'Be

对int array进行排序的实例讲解

今天再学习一些C#的基础知识,如对 Int Array进行排序: 你可以在控制台应用程序中,创建一个类别,它属性和2个构造函数: Source Code class Af { private int[] myVar; public int[] MyIntArray { get { return myVar; } set { myVar = value; } } public Af() { } public Af(int[] arr) { this.myVar = arr; } } 接下来,我在这

Python实现的列表排序、反转操作示例

本文实例讲述了Python实现的列表排序.反转操作.分享给大家供大家参考,具体如下: 排序: 使用sorted方法和列表的sort方法: sorted方法适用范围更广,sort方法只有列表有. li = [{'a':'23'}, {'a':'12'}] def sort_fun(mp): s = mp['a'] return int(s) print(sorted(li, key = sort_fun, reverse = True)) #这会返回一个排好序的列表,原列表不变. print(li