type
status
date
slug
summary
tags
category
icon
password
整理定义
中文名称:基数排序
英文名称: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则相反,由键值的最左边开始。 |
百度百科 |
复述展开
基数排序的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。
LSD法(least significant digit first)最低位优先:先从低位开始排序,在每个关键字上,可采用桶排序
MSD法(most significant digit first)最高位优先:先从高位开始进行排序,在每个关键字上,可采用计数排序
动态图:
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2Fdea38628-64dc-40fd-8d17-2efa87e3d554%2Feec10404-19e6-44c7-a340-4ba7c48c50b7%2F330px-%25E5%259F%25BA%25E6%2595%25B0%25E6%258E%2592%25E5%25BA%258F.gif?table=block&id=c26fd7ed-316f-4506-b1f3-103fe19cca20&t=c26fd7ed-316f-4506-b1f3-103fe19cca20&width=330&cache=v2)
代码演示:
理解体会
基数排序与计数排序、桶排序这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:
- 基数排序:根据键值的每位数字来分配桶;
- 计数排序:每个桶只存储单一键值;
- 桶排序:每个桶存储一定范围的数值;
基数排序不是直接根据元素整体的大小进行元素比较,而是将原始列表元素分成多个部分,对每一部分按一定的规则进行排序,进而形成最终的有序列表。
快速跳转链接
【概念解析】启动
【概念解析】Day 1 - 10
【概念解析】Day 11 - 20
【概念解析】Day 21 - 30
【概念解析】Day 31 - 40
【概念解析】Day 41 - 50
【概念解析】Day 51 - 60
【概念解析】Day 61 - 70
【概念解析】Day 71 - 80
【概念解析】Day 81 - 90
- 作者:eachenkuang
- 链接:https://kuangyichen.com/article/industry-day23
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。