7.5.2 基数排序

基数排序是一种很特别的排序方法,它不是基于比较进行排序的,而是采用多关键字排序思想,借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先(MSD)排序和最低位优先(LSD)排序。

以r为基数的最低位优先基数排序的过程:

假设线性表由结点序列a0,a1,……an-1构成,每个结点aj的关键字由d元组[{ k((d-1j),k(d-2,j),……,k(1,j),k(0,j) }组成,

其中0<=k(i,j)<=r-1   (0<=j<n,0<=i<=d-1).

在排序过程中,使用r个队列Q0,Q1,……Qr-1。排序过程如下:

对i=0,1,……,d-1,依次做一次“分配”和“收集”(其实就是一次稳定的排序过程)。

分配:开始时,把Q0,Q1,……,Qr-1各个队列置成空队列,然后依次考察线性表中的每一个结点aj(j=0,1,……,n-1),如果aj的关键字k(i,j)=k,就把aj放进Qk队列中。

收集:把Q0,Q1,……Qr-1各个队列中的结点依次首尾相连,得到新的结点序列,从而组成新的线性表

原始序列:329—>457—>657—>839—>436—>720—>355

1、按个位分配

Q0

Q1

Q2

Q3

Q4

Q5

Q6

Q7

Q8

Q9

720

355

436

457

329

657

839

收集:720—>355—>436—>457—>657—>329—>839

2、按十位分配

Q0

Q1

Q2

Q3

Q4

Q5

Q6

Q7

Q8

Q9

720

436

355

329

839

457

657

收集:720—>329—>436—>839—>355—>457—>657

3、按百位分配

Q0

Q1

Q2

Q3

Q4

Q5

Q6

Q7

Q8

Q9

329

436

657

720

839

355

457

收集:329—>355—>436—>457—>657—>720—>839

空间效率:一趟排序需要的辅助空间为r(r个队列),但以后的排序中重复使用这些队列,所以基数排序的空间复杂度为O(r).

时间效率:基数排序需要进行d趟分配和收集,一趟分配需要O(n),一趟收集需要O(r),所以基数排序的时间复杂度为O(d(n+r)),它与序列的初始状态无关。

稳定性:对于基数排序算法而言,很重要一定是按位排序时必须是稳定的,因此,这也保证了基数排序保持稳定性。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

Java中有关Null的9件事

对于Java程序员来说,null是令人头痛的东西。时常会受到空指针异常(NPE)的骚扰。连Java的发明者都承认这是他的一项巨大失误。Java为 什么要保留nu...

892
来自专栏java一日一条

Java中有关Null的9件事

对于Java程序员来说,null是令人头痛的东西。时常会受到空指针异常(NPE)的骚扰。连Java的发明者都承认这是他的一项巨大失误。Java为什么要保留nul...

622
来自专栏java一日一条

Java有值类型吗?

有人看了我之前的文章『Swift 语言的设计错误』,问我:“你说 Java 只有引用类型(reference type),但是根据 Java 的官方文档,Jav...

1182
来自专栏noteless

[五]java函数式编程归约reduce概念原理 stream reduce方法详解 reduce三个参数的reduce方法如何使用

java8 流相关的操作中,我们把它理解 "累加器",之所以加引号是因为他并不仅仅是加法

2653
来自专栏技术小站

深入理解Java的接口和抽象类(转)

  对于面向对象编程来说,抽象是它的一大特征之一。在Java中,可以通过两种形式来体现OOP的抽象:接口和抽象类。这两者有太多相似的地方,又有太多不同的地方。很...

752
来自专栏醒者呆

融会贯通——深入了解面向对象设计原则“依赖倒转原则”

一千个人眼里有一千个哈姆雷特,下面我尝试用深入浅出的语言贯穿到“控制反转”,“依赖注入”,“面向抽象编程”,以及“面向接口编程”这几个概念。 传递参数,关联(组...

3427
来自专栏C语言及其他语言

C语言的数据类型

变量与常量数据 在程序的世界中,可以让计算机按照指令做很多事情,如进行数值计算、图像显示、语音对话、视频播放、天文计算、发送邮件、游戏绘图以及任何我们可以想...

4745
来自专栏架构师小秘圈

深入理解Java的接口和抽象类

架构技术干货第一时间送达! 对于面向对象编程来说,抽象是它的一大特征之一。在Java中,可以通过两种形式来体现OOP的抽象:接口和抽象类。这两者有太多相似的地方...

3365
来自专栏Java学习网

Java中有关Null的9问题

Java中有关Null的9问题 对于Java程序员来说,null是令人头痛的东西。时常会受到空指针异常(NPE)的骚扰。连Java的发明者都承认...

2215
来自专栏GIS讲堂

面向对象思想

类:描述了具有相同特性(属性)和相同行为(操作方法)的对象。在程序中,类就是数据类型。

1244

扫码关注云+社区

领取腾讯云代金券