基数排序

开发者 · 2024-9-4 08:31:49

基数排序（英语：Radix sort）是一种非比力型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比力。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在列表机（Tabulation Machine）上的贡献。
它是如许实现的：将全部待比力数值（正整数）同一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次举行一次排序。如许从最低位排序不绝到最高位排序完成以后，数列就酿成一个有序序列。
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
基数排序与计数排序的区别是：计数排序每个桶只存储单一键值，而基数排序会根据键值的每位数字来分配桶；

基数排序

所属分类: 问答交流

新帖推荐: 30日

推荐作品