基数排序——简单理解

秒速五厘米 2022-05-10 00:04 123阅读 0赞

## 什么是基数排序 ##

--------------------

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。

--------------------

##  分类 ##

--------------------

![在这里插入图片描述][70]

--------------------

## 举个“栗子” ##

--------------------

![在这里插入图片描述][70 1]

--------------------

##  算法执行步骤： ##

--------------------

(1)遍历序列找出最大的数(为的是确定最大的数是几位数)；

(2)开辟一个与数组大小相同的临时数组tmp；

(3)用一个count数组统计原数组中某一位(从低位向高位统计)相同的数据出现的次数；

(4)用一个start数组计算原数组中某一位(从最低位向最高位计算)相同数据出现的位置；

(5)将桶中数据从小到大用tmp数组收集起来；

(6)重复(3)(4)(5)直到所有位都被统计并计算过，用tmp收集起来；

(7)将tmp数组拷回到原数组中；

--------------------

## 使用场景 ##

--------------------

*  在某个数字可能很大的时候，基数排序没有任何性能上的优势，还会浪费非常多的内存。
 *  所以基数排序大多数情况下面只适用于下面的情景，一组数，这组数的最大值不是很大，更加准确的说，是要排序的对象的数目 和 排序对象的最大值之间相差不多。比如，这组数 1 4 5 2 2，要排序对象的数目是 5 ，排序对象的最大值也是 5. 这样的情况很适合。我们原来的排序的数，默认是以10为基数，现在，这个改进算法是这样的，我以最大的那个数为基数，这样，所有的数都是“个位数”，问题就简单了。

--------------------

## 时间复杂度&空间复杂度&稳定性 ##

--------------------

*  时间复杂度：O(N\*digit)
 *  空间复杂度：O(N)
 *  稳定性：稳定

[70]: /images/20220510/b38ad327bb744581bb5cf4457a8b7ffe.png
[70 1]: /images/20220510/876dd08fbf764c078ee586265391a976.png

发表评论取消回复

表情：

评论列表（有 0 条评论，123人围观）

还没有评论，来说两句吧...

相关阅读

相关基数排序

基数排序与本系列前面讲解的七种排序方法都不同，它不需要比较关键字的大小。它是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。不

以你之姓@/ 2022年08月21日 05:35/ 0 赞/ 198 阅读

相关基数排序

基数排序(Radix sort)是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。比较官方地说，基数排序是一种基于多关键字的排序。基

蔚落/ 2022年06月15日 06:11/ 0 赞/ 221 阅读

相关基数排序

对于一个int数组，请编写一个基数排序算法，对数组元素排序。给定一个int数组A及数组的大小n，请返回排序后的数组。保证元素均小于等于2000。测试样例：

分手后的思念是犯贱/ 2022年06月09日 01:36/ 0 赞/ 215 阅读

相关基数排序

写在前面 > 计数排序，基数排序总结计数排序是非基于比较的排序方式，和一般基于比较的排序不同。基于比较的排序的算法的平均复杂度的下界也是o(nlgn)。

柔情只为你懂/ 2022年05月12日 02:54/ 0 赞/ 273 阅读

相关基数排序——简单理解

什么是基数排序 -------------------- 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bu

秒速五厘米/ 2022年05月10日 00:04/ 0 赞/ 124 阅读

相关基数排序

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

客官°小女子只卖身不卖艺/ 2022年01月29日 02:01/ 0 赞/ 286 阅读

相关基数排序

package com.sort; / @Auther: 大哥的叔 @Date: 2019/8/8 13:06 @

àì夳堔傛蜴生んèń/ 2021年11月05日 18:12/ 0 赞/ 312 阅读

相关基数排序

在箱子排序中，尽管时间复制度仅仅有(n),但假设其箱子序列较大的话将会导致程序的空间复杂度较大，所以对于对于属性值跨度比較大的序列能够採用基数排序法。概述：详细的做法

痛定思痛。/ 2021年09月19日 10:12/ 0 赞/ 388 阅读

相关基数排序

在介绍基数排序前，我们先简单介绍下桶排序：例如有10个桶，我们给分边编号1——10，然后寻找其中装有水的桶。 ![70][] 我们可以显而易见，其中装有水的桶编号是

清疚/ 2021年09月15日 20:52/ 0 赞/ 397 阅读

相关基数排序就这么简单

一、基数排序(桶排序)介绍来源360百科： > 基数排序(radix sort)属于”分配式排序”(distribution sort)，又称”桶子法”(bucket

以你之姓@/ 2021年09月15日 02:26/ 0 赞/ 366 阅读