《桶排序
》中我们能够看到,数据值的范围越大,可能需要桶的个数也就越多,空间代价也就越高。对于上亿单位的关键字,桶排序是很不实用的。基数排序是对桶排序的一种改进,这种改进是让“桶排序”适合于更大的元素值集合的情况,而不是提高性能。
多关键字排序问题(类似于字典序):
我们先看看扑克牌的例子。一张牌有两个关键字组成:花色(桃<心<梅<方)+面值(2<3<4<...<A)。假如一张牌的大小首先被花色决定,同花色的牌有数字决定的话。我们就有两种算法来解决这个问题。
(1) 首先按照花色对所有牌进行稳定排序,这样就可以将所有牌分成4组。然后同组的牌(同花色)再按照面值进行排序。
(2) 首先按照面值对所有牌进行稳定排序,然后按照花色再次对所有牌进行稳定排序。
显然,第一种方法需要将序列分割成几个子序列。而第二种方法则完全不需要。因此我们采用从次关键字排序开始的方法。
基数排序
上面的问题是多关键字的排序,但单关键字也仍然可以使用这种方式。
比如字符串“abcd” “aesc” "dwsc" "rews"就可以把每个字符看成一个关键字。另外还有整数 425、321、235、432也可以每个位上的数字为一个关键字。
基数排序的思想就是将待排数据中的每组关键字依次进行桶分配。比如下面的待排序列:
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、589、269
再对上面的序列接着进行针对k2的桶分配,输出序列为:
505、008、109、930、063、269、278、083、184、589
最后针对k3的桶分配,输出序列为:
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个左右。
但是,对比桶排序,基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作,而桶排序在桶相对较少的情况下,桶内多个数据必须进行基于比较操作的排序。因此,在实际应用中,基数排序的应用范围更加广泛。
分享到:
相关推荐
数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数...
数据结构中的基数排序是一种非比较型整数排序算法,它基于数字的位宽进行排序,尤其适用于处理大量相同数字的情况。基数排序的核心思想是将数字按照位数从低位到高位分别进行桶排序,最终得到完全有序的序列。下面将...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种排序方法适用于处理大量数据,且数据的范围不超过10的某个幂次方的情况。基数排序是基于多关键字排序的一...
数据结构学习笔记基数排序 详细讲解数据结构学习笔记基数排序 详细讲解数据结构学习笔记基数排序 详细讲解数据结构学习笔记基数排序 详细讲解数据结构学习笔记基数排序 详细讲解数据结构学习笔记基数排序 详细讲解...
例如,插入排序和选择排序适合小规模数据,冒泡排序虽然效率较低但实现简单,堆排序和快速排序在处理大规模数据时有较好性能,而基数排序则能处理非负整数排序。在实际开发中,根据具体需求选择合适的排序算法是非常...
数据结构排序选择排序归并排序基数排序PPT学习教案.pptx
本文主要介绍了五种内部排序算法:插入排序、交换排序、选择排序、归并排序和基数排序。 1. **插入排序**: 插入排序的基本思想是从未排序的序列中取出一个元素,然后将其插入到已排序序列的正确位置,以保持序列...
这里我们将深入探讨四种常见的排序算法:基数排序、堆排序、希尔排序和直接插入排序。 首先,基数排序是一种非比较型整数排序算法,它的基本思想是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序...
链式基数排序是基数排序的一种变体,它利用了链表的数据结构来优化基数排序的过程。这种排序方法特别适用于大数据量的排序场景,因为它能够有效地减少内存访问次数,提高排序效率。 #### 基本思想 链式基数排序的...
基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。在这个程序中,基数排序被实现为一个名为`RadixSort`的函数,用于对`SLList`类型的链表进行排序。`SLList`...
"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式基数排序。 基本要求: 待排序表的表长不...
接下来,我们将深入探讨基数排序、C语言实现、数据结构的相关知识点。 1. **基数排序原理**: - 基数排序的基本思想是按照每位数字进行排序,从最低位开始,逐步到最高位。通常采用“桶”或“袋”来收集每个位上的...
### 数据结构 - 基数排序详解与代码分析 #### 一、基数排序简介 基数排序(Radix Sort)是一种非比较整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数进行比较。由于整数也可以表达字符串(如...
7. **基数排序**(Radix Sort): - 基数排序不是比较型排序,而是利用数字的位数进行排序。从低位到高位,对每个位数进行一次分配排序,如桶排序。 - C# 实现基数排序时,需要创建多个桶,按位进行分配和收集,...
本文将详细解析几种常见的排序算法:冒泡排序、快速排序、选择排序以及基数排序,并探讨它们的工作原理、效率和适用场景。 **冒泡排序**: 冒泡排序是一种简单直观的排序算法,通过比较相邻元素并交换位置来实现...
【数据结构】基数排序的哈希表 一个专为巨量数据的快速存储和检索而设计的哈希表类, 可提供基于不同哈希键值对的近似常数时间的寻位存储和定位检索。 寻位和定位算法基于键对象之哈希值的每一个二进制位的状态所...
链式基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。在描述中提到的实验报告中,主要目标是实现一个链式基数排序算法,用于对一组数据进行最低位优先的排序...
3.基数排序。 北工大电控学院《数据结构与算法》课程的其它章节实验及作业程序代码亦已在本站上传,需要的同学可进入作者的空间或通过搜索获取。本代码为上传者原创,仅供个人学习参考使用,请勿自行在其他网站及...
本篇内容主要涉及数据结构中的内部排序方法,包括选择排序、堆排序以及归并排序和基数排序。这些排序算法是计算机科学中数据处理和算法设计的基础部分,对于理解和优化程序性能至关重要。 **选择排序**是一种简单...