基数排序简介及Java语言实现

基本思想

基数排序(RadixSort)是在桶排序的基础上发展而来的,两种排序都是分配排序的高级实现。分配排序(DistributiveSort)的基本思想:排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶:O(n)。

基数排序是一种稳定的排序算法,但有一定的局限性:

  1、关键字可分解。
  2、记录的关键字位数较少,如果密集更好
  3、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。

先来看一下桶排序(RadixSort)。

桶排序也称为箱排序(BinSort),其基本思想是:设置若干个桶,依次扫描待排序的记录R[0],R[1],…,R[n-1],把关键字在某个范围内的记录全都装入到第k个桶里(分配),然后按序号依次将各非空的桶首尾连接起来(收集)。

例如,要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序,需设置13个“桶”,排序时依次将每张牌按点数放入相应的桶里,然后依次将这些桶首尾相接,就得到了按点数递增序排列的一副牌。

桶排序中,桶的个数取决于关键字的取值范围。因此桶排序要求关键字的类型是有限类型,否则可能要无限个桶。

一般情况下每个桶中存放多少个关键字相同的记录是无法预料的,故桶的类型应设计成链表为宜。

为保证排序是稳定的,分配过程中装箱及收集过程中的连接必须按先进先出原则进行。

对于桶排序来说,分配过程的时间是O(n);收集过程的时间为O(m)(采用链表来存储输入的待排序记录)或O(m+n)。因此,桶排序的时间为O(m+n)。若桶个数m的数量级为O(n),则桶排序的时间是线性的,即O(n)。

前面说的几大排序算法,大部分时间复杂度都是O(n2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是:首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。其次待排序的元素都要在一定的范围内等等。

基数排序是对桶排序的一种改进,这种改进是让“桶排序”适合于更大的元素值集合的情况,而不是提高性能。

我们还是用扑克牌的例子来说明。一张牌有两个关键字组成:花色(桃<心<梅<方)+面值(A<2<3<4<...<K)。假如一张牌的大小首先被花色决定,同花色的牌有数字决定的话。我们就有两种算法来解决这个问题。

即两张牌,若花色不同,不论面值怎样,花色低的那张牌小于花色高的,只有在同花色情况下,大小关系才由面值的大小确定。这就是多关键码排序。

为得到排序结果,我们讨论两种排序方法。

方法1:先对花色排序,将其分为4个组,即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序,最后,将4个组连接起来即可。

方法2:先按13个面值给出13个编号组(2号,3号,...,A号),将牌按面值依次放入对应的编号组,分成13堆。再按花色给出4个编号组(梅花、方块、红心、黑心),将2号组中牌取出分别放入对应花色组,再将3号组中牌取出分别放入对应花色组,……,这样,4个花色组中均按面值有序,然后,将4个花色组依次连接起来即可。

多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序,分两种方法:

最高位优先(MostSignificantDigitfirst)法,简称MSD法:

1)先按k1排序分组,将序列分成若干子序列,同一组序列的记录中,关键码k1相等。

2)再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后。

3)再将各组连接起来,便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD法。

最低位优先(LeastSignificantDigitfirst)法,简称LSD法:

1)先从kd开始排序,再对kd-1进行排序,依次重复,直到按k1排序分组分成最小的子序列后。

2)最后将各个子序列连接起来,便可得到一个有序的序列,扑克牌按花色、面值排序中介绍的方法二即是LSD法。

对数字型或字符型的单关键字,可以看作由多个数位或多个字符构成的多关键字,此时可以采"分配-收集”的方法进行排序,这一过程称作基数排序法,其中每个数字或字符可能的取值个数称为基数。比如,扑克牌的花色基数为4,面值基数为13。在整理扑克牌时,既可以先按花色整理,也可以先按面值整理。按花色整理时,先按红、黑、方、花的顺序分成4摞(分配),再按此顺序再叠放在一起(收集),然后按面值的顺序分成13摞(分配),再按此顺序叠放在一起(收集),如此进行二次分配和收集即可将扑克牌排列有序。

在“分配-收集”的过程中,需要保证排序的稳定性。

基数排序的思想就是将待排数据中的每组关键字依次进行桶分配。比如下面的待排序列:

135、242、192、93、345、11、24、19

我们将每个数值的个位,十位,百位分成三个关键字,例如:

135->k1(个位)=5,k2(十位)=3,k3(百位)=1。

然后从最低位个位开始(从最次关键字开始),对所有数据的k1关键字进行桶分配(因为,每个数字都是0-9的,因此桶大小为10),再依次输出桶中的数据得到下面的序列。

(11)、(242、192)、(93)、(24)、(135、345)、(19)(从最次关键字开始排序,忽略百位与十位,按照个位上的数字分配)

再对上面的序列接着进行针对k2的桶分配,输出序列为:

(11、19)、(24)、(135)、(242、345)、(192、93)(参考最次关键字来排序第二次关键字,忽略百位与个位,按照十位上的数字分配)

最后针对k3的桶分配,输出序列为:

(011、019、024、093)、(135、192)、(242)、(345)(参考第二次关键字来排序最高关键字,忽略十位与个位,按照百位上的数字分配)

排序完毕。

java实现

public void radixSort(){ 

       int max = array[0];
       for(int i=0;i<array.length;i++){ //找到数组中的最大值
          if(array[i]>max){
              max = array[i];
          }
       } 

       int keysNum = 0; //关键字的个数,我们使用个位、十位、百位...当做关键字,所以关键字的个数就是最大值的位数
       while(max>0){
          max /= 10;
          keysNum++;
       } 

       List<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
       for(int i=0;i<10;i++){ //每位可能的数字为0~9,所以设置10个桶
          buckets.add(new ArrayList<Integer>()); //桶由ArrayList<Integer>构成
       } 

       for(int i=0;i<keysNum;i++){ //由最次关键字开始,依次按照关键字进行分配 

          for(int j=0;j<array.length;j++){ //扫描所有数组元素,将元素分配到对应的桶中
              //取出该元素对应第i+1位上的数字,比如258,现在要取出十位上的数字,258%100=58,58/10=5
              int key =array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
              buckets.get(key).add(array[j]); //将该元素放入关键字为key的桶中
          } 

          //分配完之后,将桶中的元素依次复制回数组
          int counter = 0; //元素计数器
          for(int j=0;j<10;j++){
              ArrayList<Integer> bucket =buckets.get(j); //关键字为j的桶
              while(bucket.size()>0){
                  array[counter++] = bucket.remove(0); //将桶中的第一个元素复制到数组,并移除
              }
          }
          System.out.print("第"+(i+1)+"轮排序:");
          display();
       } 

   } 

打印结果如下:

算法分析

初看起来,基数排序的执行效率似乎好的让人无法相信,所有要做的只是把原始数据项从数组复制到链表,然后再复制回去。如果有10个数据项,则有20次复制,对每一位重复一次这个过程。假设对5位的数字排序,就需要20*5=100次复制。如果有100个数据项,那么就有200*5=1000次复制。复制的次数与数据项的个数成正比,即O(n)。这是我们看到的效率最高的排序算法。

不幸的是,数据项越多,就需要更长的关键字,如果数据项增加10倍,那么关键字必须增加一位(多一轮排序)。复制的次数和数据项的个数与关键字长度成正比,可以认为关键字长度是N的对数。因此在大多数情况下,基数排序的执行效率倒退为O(N*logN),和快速排序差不多。

总结

以上就是本文关于基数排序简介及Java语言实现的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。

(0)

相关推荐

  • Java 选择排序、插入排序、希尔算法实例详解

    1.基本思想: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换:然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止. 2.实例 3.算法实现 /** * 选择排序算法 * 在未排序序列中找到最小元素,存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾. * 以此类推,直到所有元素均排序完毕. * @param numbers */ public static void selectSort(int[] nu

  • java 算法之冒泡排序实例详解

    java 算法之冒泡排序实例详解 无人不知无人不晓的冒泡排序,据说是模仿泡泡从水中浮起跑到水面的过程. 在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒.即: 每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换. 来看一下代码: package cn.songxinqiang.study.algorithm.sort; import java.util.Arrays; /** * 冒泡排序 * * <p>

  • java实现的各种排序算法代码示例

    折半插入排序 折半插入排序是对直接插入排序的简单改进.此处介绍的折半插入,其实就是通过不断地折半来快速确定第i个元素的 插入位置,这实际上是一种查找算法:折半查找.Java的Arrays类里的binarySearch()方法,就是折半查找的实现,用 于从指定数组中查找指定元素,前提是该数组已经处于有序状态.与直接插入排序的效果相同,只是更快了一些,因 为折半插入排序可以更快地确定第i个元素的插入位置 代码: package interview; /** * @author Administrat

  • Java使用分治算法实现排序数索引功能示例【二分搜索】

    本文实例讲述了Java使用分治算法实现排序数索引功能.分享给大家供大家参考,具体如下: /** * Find the first q and return the index * First method is brutal force * Second may * be Divid and Conquer * * @author open201 * */ public class Ono { /** * f(n) = s.length = n; * * @param s * @param q

  • Java TreeMap排序算法实例

    本文实例讲述了Java TreeMap排序算法.分享给大家供大家参考,具体如下: TreeMap 和 HashMap 用法大致相同,但实际需求中,我们需要把一些数据进行排序: 以前在项目中,从数据库查询出来的数据放在List中,顺序都还是对的,但放在HashMap中,顺序就完全乱了. 为了处理排序的问题: 1. 对于一些简单的排序,如:数字,英文字母等 TreeMap hm = new TreeMap<String, String>(new Comparator() { public int

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

  • 基数排序简介及Java语言实现

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

  • Java语言简介(动力节点Java学院整理)

    Java 简介 Java是由Sun Microsystems公司(现已被oracle公司收购)于1995年5月推出的Java面向对象程序设计语言和Java平台的总称.由James Gosling和同事们共同研发,并在1995年正式推出,据oracle官方数据指数,目前全球已有上亿的系统是使用Java开发的. Java是一门面向对象编程语言,不仅吸收了C++语言的各种优点,还摒弃了C++里难以理解的多继承.指针等概念,因此Java语言具有功能强大和简单易用两个特征.Java语言作为静态面向对象编程

  • 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

  • Java语言Consistent Hash算法学习笔记(代码示例)

    本文研究的主要是ConsistentHashing算法代码. 一致性哈希(Consistent Hash) 协议简介 一致性哈希算法在1997年由麻省理工学院提出(参见0),设计目标是为了解决因特网中的热点(Hot pot)问题,初衷和CARP十分类似.一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用. 哈希算法 一致性哈希提出了在动态变化的Cache环境中,哈希算法应该满足的4个适应条件: 平衡性(Balance) 平衡性是指哈希的结果能够尽可能分

  • Java语言的11大特点(Java初学者必知)

    Java简介 Java是一门面向对象编程语言,不仅吸收了C++语言的各种优点,还摒弃了C++里难以理解的多继承.指针等概念,因此Java语言具有功能强大和简单易用两个特征. Java语言作为静态面向对象编程语言的代表,极好地实现了面向对象理论,允许程序员以优雅的思维方式进行复杂的编程  . Java具有简单性.面向对象.分布式.健壮性.安全性.平台独立与可移植性.多线程.动态性等特点 Java可以编写桌面应用程序.Web应用程序.分布式系统和嵌入式系统应用程序等 . Java是一种简单的,面向对

  • Java语言实现反转链表代码示例

    问题描述 定义一个函数,输入一个链表的头结点,反转该链表并输出反转后的链表的头结点.链表结点如下: public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } 思路1: 要想反转链表,对于结点i,我们要把它的next指向它的前趋,因此我们需要保存前趋结点,同时,如果我们已经把i的next重新赋值,会无法找到i的后继,因此,在重新赋值之前,我们要保存i的后继. 代码:

  • Java语言实现简单FTP软件 FTP软件主界面(4)

    首先看一下FTP软件的整体代码框架,具体内容如下 1.首先介绍程序的主入口FTPMain.java,采用了一个漂亮的外观风格 package com.oyp.ftp; import java.util.logging.Level; import java.util.logging.Logger; import javax.swing.UIManager; import com.sun.java.swing.plaf.nimbus.NimbusLookAndFeel; public class F

  • JAVA语言编程格式高级规范

    作为一位开发人员,都要有严格的代码规范.为此我总结了一些代码规范案例. 目 录 1. 前言 2. 试用范围 3. JAVA命名规范-- 3.1 公共约定 3.2 Java文件.包 3.3 类.接口命名规范 3.4 方法命名规范 3.5 常量 3.6 变量和参数 3.7 组件/部件 3.8 集合 3.9 神秘的数 3.10 其他 3.11 Java异常 3.12 数组命名 3.13 数据库表命名规则 3.14 数据库字段命名规则 3.15 JSP文件命名 3.16 Servlet类命名 4. 书写

  • Java语言十大基础特性分析

    Java语言的作者们编写了具有广泛影响的Java白皮书,里面详细地介绍了他们的设计目标以及实现成果,还用简短的篇幅介绍了Java语言的特性.下面将对这些特性进行介绍. 1. 简单 Java语言的语法简单明了,容易掌握,而且是纯面向对象的语言.Java语言的简单性主要体现在以下几个方面: 语法规则和C++类似.从某种意义上讲,Java语言是由C和C++语言转变而来的,所以C程序设计人员可以很容易地掌握Java语言的语法. Java语言对C++进行了简化和提高.例如,Java使用接口取代了多重继承,

  • Javascript和Java语言有什么关系?两种语言间的异同比较

    虽然Javascript与Java有紧密的联系,但却是两个公司开发的不同的两个产品.Java是Sun公司推出的新一代面向对象的程序设计语言.特别适合于Internet应用程序开发:而Javascript是Sun与Netscape公司联合推出的产品,是为了扩展Netscape Navigator功能而开发的一种可以嵌入Web页面中的基于对象和事件驱动的解释性语言.且它的前身是Live Script,而Java的前身是Oak语言.下面就对两种语言间的异同作如下比较: (1)基于对象和面向对象 Jav

随机推荐