Day23【概念解析】基数排序

type

status

date

slug

summary

整理定义

中文名称：基数排序

英文名称：radix sort

出处	定义
中国大百科全书	一般情况下，假设某个序列含有d个元素（K1，K2，.. Kd）且记录的元素为整型（实际上元素并不限于整型），其中K1为最主位关键字，Kd为最次位关键字。为实现多关键字排序，有以下两种方法：1、最高位优先法，简称MSD法：先按K1排序分组，同一组中记录，关键码K1相等，再对各组按K2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码Kd对各子组排序后。再将各组连接起来，便得到一个有序序列。2、最低位优先法，简称LSD法：先从Kd开始排序，再对Kd-1进行排序，一次重复，直到对K1排序后便得到一个有序数列。
维基百科	基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
百度百科	基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

复述展开

基数排序的原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

LSD法（least significant digit first）最低位优先：先从低位开始排序，在每个关键字上，可采用桶排序

MSD法（most significant digit first）最高位优先：先从高位开始进行排序，在每个关键字上，可采用计数排序

动态图：

代码演示：

理解体会

基数排序与计数排序、桶排序这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶；

计数排序：每个桶只存储单一键值；

桶排序：每个桶存储一定范围的数值；

基数排序不是直接根据元素整体的大小进行元素比较，而是将原始列表元素分成多个部分，对每一部分按一定的规则进行排序，进而形成最终的有序列表。

📌

快速跳转链接

【概念解析】启动

【活动打卡】写100个行业概念 | 易浅小站

为什么要参加这个活动呢？起源于S老师的”写100个行业概念“活动。之前一直有关注Scalers老师的公众号，也阅读完了《学习的学问》这本书，感叹于S老师学习成长会的魅力，决定先让自己跟着这个活动坚持个一百天先。

整理定义

复述展开

理解体会

eachenkuang