- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章基数排序简介及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实现 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
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语言实现的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出.
原文链接:http://blog.csdn.net/u012152619/article/details/47702673 。
最后此篇关于基数排序简介及Java语言实现的文章就讲到这里了,如果你想了解更多关于基数排序简介及Java语言实现的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我正在尝试对每个条目有多个值的关联数组进行排序。 例如 [0] => stdClass Object ( [type] => node [sid] => 158 [score] => 0.059600
我在 mysql 中有“日期”列以这种格式保存日期 2014 年 9 月 17 日(日-月-年) 我需要对它们进行升序排序,所以我使用了这个命令: SELECT * FROM table ORDER
我目前正在将 MySQL 存储过程重写为 MS SQL 存储过程,但遇到了问题。 在 MySQL 存储过程中,有一个游标,它根据最近的日期 (effdate) 选择一个值并将其放入变量 (thestt
我想要 gwt r.QuestionId- 排序。但是我得到未排序的 QuestionId 尽管我提到了 QuestionId ASC 的顺序。 SELECT r.QuestionId,
我有一个关于在 scandir 函数中排序的基本问题。到目前为止,我阅读了 POSIX readdir 的手册页,但没有找到有关订购保证的具体信息。 但是当我遍历大目录(无法更改,只读)时,我在多个系
基本上我必须从 SQL 数据库中构建项目列表,但是用户可以选择对 7 个过滤器的任意组合进行过滤,也可以选择要排序的列以及按方向排序。 正如您可以想象的那样,这会以大量不同的组合进行编码,并且数据集非
我有两张 table 。想象第一个是一个目录,包含很多文件(第二个表)。 第二个表(文件)包含修改日期。 现在,我想选择所有目录并按修改日期 ASC 对它们进行排序(因此,最新的修改最上面)。我不想显
我想先根据用户的状态然后根据用户名来排序我的 sql 请求。该状态由 user_type 列设置: 1=活跃,2=不活跃,3=创始人。 我会使用此请求来执行此操作,但它不起作用,因为我想在“活跃”成员
在 C++ 中,我必须实现一个“类似 Excel/Access”(引用)的查询生成器,以允许对数据集进行自定义排序。如果您在 Excel 中使用查询构建器或 SQL 中的“ORDER BY a, b,
我面临这样的挑战: 检索按字段 A 排序的文档 如果字段 B 存在/不为空 . 否则 按字段排序 C. 在 SQL 世界中,我会做两个查询并创建一个 UNION SELECT,但我不知道如何从 Mon
我想对源列表执行以下操作: map 列表 排序 折叠 排序 展开 列表 其中一些方法(例如map和toList)是可链接的,因为它们返回非空对象。但是,sort 方法返回 void,因为它对 List
我制作了一个用于分析 Windows 日志消息编号的脚本。 uniq -c 数字的输出很难预测,因为根据数字的大小会有不同的空白。此时,我手动删除了空白。 这是对消息进行排序和计数的命令: cat n
我有以下词典: mydict1 = {1: 11, 2: 4, 5: 1, 6: 1} mydict2 = {1: 1, 5: 1} 对于它们中的每一个,我想首先按值(降序)排序,然后按键(升序)排序
我刚刚开始使用泛型,目前在对多个字段进行排序时遇到问题。 案例: 我有一个 PeopleList 作为 TObjectList我希望能够通过一次选择一个排序字段,但尽可能保留以前的排序来制作类似 Ex
有没有办法在 sql 中组合 ORDER BY 和 IS NULL 以便我可以在列不为空时按列排序,但如果它为null,按另一列排序? 最佳答案 类似于: ORDER BY CASE WHEN
我有一个包含 2 列“id”和“name”的表。 id 是常规的自动增量索引,name 只是 varchar。 id name 1 john 2 mary 3 pop 4 mary 5 j
场景 网站页面有一个带有分页、过滤、排序功能的表格 View 。 表中的数据是从REST API服务器获取的,数据包含数百万条记录。 数据库 REST API 服务器 Web 服务器 浏览器 问
假设我有一本字典,其中的键(单词)和值(分数)如下: GOD 8 DONG 16 DOG 8 XI 21 我想创建一个字典键(单词)的 NSArray,首先按分数排序,然后按字
如何在 sphinx 上通过 sql 命令选择前 20 行按标题 WEIGHT 排序,接下来 20 行按标题 ASC 排序(总共 40 个结果),但不要给出重复的标题输出。 我尝试了这个 sql 命令
我有一个奇怪的问题,当从 SQLite 数据库中选择信息并根据日期排序时,返回的结果无效。 我的SQL语句是这样的: Select pk from usersDates order by dateti
我是一名优秀的程序员,十分优秀!