- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章深入解析Radix Sort基数排序算法思想及C语言实现示例由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
基本思想:
将待排数据中的每组关键字依次进行桶分配。 具体示例:
1
|
278、109、063、930、589、184、505、269、008、083
|
我们将每个数值的个位,十位,百位分成三个关键字: 278 -> k1(个位)=8,k2(十位)=7,k3=(百位)=2.
然后从最低位个位开始(从最次关键字开始),对所有数据的k1关键字进行桶分配(因为,每个数字都是 0-9的,因此桶大小为10),再依次输出桶中的数据得到下面的序列.
1
|
930、063、083、184、505、278、008、109、589、269
|
再对上面的序列接着进行针对k2的桶分配,输出序列为:
1
|
505、008、109、930、063、269、278、083、184、589
|
最后针对k3的桶分配,输出序列为:
1
|
008、063、083、109、184、269、278、505、589、930
|
效率分析:
基数排序的性能比桶排序要略差。每一次关键字的桶分配都需要O(N)的时间复杂度,而且分配之后得到新的关键字序列又需要O(N)的时间复杂度。假如待排数据可以分为d个关键字,则基数排序的时间复杂度将是O(d*2N) ,当然d要远远小于N,因此基本上还是线性级别的。基数排序的空间复杂度为O(N+M),其中M为桶的数量。一般来说N>>M,因此额外空间需要大概N个左右.
但是,对比桶排序,基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作,而桶排序在桶相对较少的情况下,桶内多个数据必须进行基于比较操作的排序。因此,在实际应用中,基数排序的应用范围更加广泛.
举例: 假设我们有一些二元组(a,b),要对它们进行以a为首要关键字,b的次要关键字的排序。我们可以先把它们先按照首要关键字排序,分成首要关键字相同的若干堆。然后,在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起,使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序.
第二种方式是从最低有效关键字开始排序,称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序,然后对所有的数据按照首要关键字排序。要注意的是,使用的排序算法必须是稳定的,否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序,LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的.
通常,基数排序要用到计数排序或者桶排序。使用计数排序时,需要的是Order数组。使用桶排序时,可以用链表的方法直接求出排序后的顺序。下面是一段用桶排序对二元组基数排序的程序:
。
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using
namespace
std;
struct
data
{
int
key[2];
};
struct
linklist
{
linklist *next;
data value;
linklist(data v,linklist *n):value(v),next(n){}
~linklist() {
if
(next)
delete
next;}
};
void
BucketSort(data *A,
int
N,
int
K,
int
y)
{
linklist *Bucket[101],*p;
//建立桶
int
i,j,k,M;
M=K/100+1;
memset
(Bucket,0,
sizeof
(Bucket));
for
(i=1;i<=N;i++)
{
k=A[i].key[y]/M;
//把A中的每个元素按照的范围值放入对应桶中
Bucket[k]=
new
linklist(A[i],Bucket[k]);
}
for
(k=j=0;k<=100;k++)
{
for
(p=Bucket[k];p;p=p->next) j++;
for
(p=Bucket[k],i=1;p;p=p->next,i++)
A[j-i+1]=p->value;
//把桶中每个元素取出
delete
Bucket[k];
}
}
void
RadixSort(data *A,
int
N,
int
K)
{
for
(
int
j=1;j>=0;j--)
//从低优先到高优先 LSD
BucketSort(A,N,K,j);
}
int
main()
{
int
N=100,K=1000,i;
data *A=
new
data[N+1];
for
(i=1;i<=N;i++)
{
A[i].key[0]=
rand
()%K+1;
A[i].key[1]=
rand
()%K+1;
}
RadixSort(A,N,K);
for
(i=1;i<=N;i++)
printf
(
"(%d,%d) "
,A[i].key[0],A[i].key[1]);
printf
(
"\n"
);
return
0;
}
|
基数排序是一种用在老式穿卡机上的算法。一张卡片有80列,每列可在12个位置中的任一处穿孔。排序器可被机械地"程序化"以检查每一迭卡片中的某一列,再根据穿孔的位置将它们分放12个盒子里。这样,操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面,第二个位置穿孔的其次,等等.
对于一个位数有限的十进制数,我们可以把它看作一个多元组,从高位到低位关键字重要程度依次递减。可以使用基数排序对一些位数有限的十进制数排序.
最后此篇关于深入解析Radix Sort基数排序算法思想及C语言实现示例的文章就讲到这里了,如果你想了解更多关于深入解析Radix Sort基数排序算法思想及C语言实现示例的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我想编写一种方法,从单向链表中删除具有重复数据值的连续项。该方法应返回移除的项目数。该方法应根据需要清理内存,并应假定内存是使用 new 分配的。 比如传入列表 ->a->b->c->c->a->b-
大家好! 属性未在 C++ 中实现。我估计我们不能写 myObject.property = value; // try to set field f_ to value 是 property 是
我正在尝试学习 java 中的设计原理...他们说,编程一个接口(interface)并实现一个接口(interface)而不是类.. 记住这一点,这是我的用例.. 从文件中读取两种格式的数据(csv
事件、工作、 self 和联系人只不过是 DTO 对象,每个对象都可以从数据库中添加、编辑和删除。我对用例图不太熟悉,所以我想知道这是否正确或可以改进。 这里有什么可以概括的吗?实现中的添加编辑和删除
我是一名优秀的程序员,十分优秀!