简介:基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog®m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。通常有两种方法:LSD(Least Significant Digit,最小有效位排序)和MSD(Most Significant Digit,最大有效位排序)。基数排序的效率依赖于内部操作的速度。
历史攻略:
Python基础入门 1 - 230题
Golang基础练习 1 - 40题
实现原理:基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。它是这样实现的:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。
Python语言描述:
import math
def bucket_sort(a, radix=10):
"""a为整数列表, radix为基数"""
if not a: # 检查列表是否为空
return a
max_val = max(a)
if max_val <= 0: # 检查最大值是否大于0
return a
K = int(math.ceil(math.log(max_val, radix))) # 用K位数可表示任意整数
bucket = [[] for _ in range(radix)] # 不能用 [[]]*radix
for i in range(1, K + 1): # K次循环
for val in a:
# 使用整数除法
bucket_index = (val // (radix ** (i - 1))) % radix
bucket[bucket_index].append(val) # 析取整数第K位数字 (从低到高)
del a[:]
for each in bucket:
a.extend(each) # 桶合并
bucket = [[] for _ in range(radix)]
return a
案例源码:3题文章来源:https://www.toymoban.com/news/detail-820559.html
# -*- coding: utf-8 -*-
# time: 2023/12/17 17:18
# file: bucket_sort_demo.py
# 公众号: 玩转测试开发
from typing import List
# 164. 最大间距
# 给定一个无序的数组 nums,返回 数组在排序之后,相邻元素之间最大的差值 。如果数组元素个数小于 2,则返回 0 。
# 您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。
# 示例 1:
# 输入: nums = [3,6,9,1]
# 输出: 3
# 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
# 示例 2:
# 输入: nums = [10]
# 输出: 0
# 解释: 数组元素个数小于 2,因此返回 0。
class Solution164:
def maximumGap(self, nums: List[int]) -> int:
# 思路
# 1、排序
# 2、设置无限小。
# 3、如果数组长度小于2.返回0
# 4、如果长度大于2. 从第二个开始遍历。每次如果间距大于前一个结果,则替换结果。不大于则继续。
# 5、结束返回
if len(nums) < 2:
return 0
else:
nums.sort()
res = float("-inf")
for index, value in enumerate(nums[1:]):
tmp = value - nums[index]
if tmp > res:
res = tmp
else:
continue
return res
s164 = Solution164()
r164 = s164.maximumGap([3, 6, 9, 1, 22])
print(f"r164:{r164}") # r164:13
# 912. 排序数组
# 给你一个整数数组 nums,请你将该数组升序排列。
# 示例 1:
# 输入:nums = [5,2,3,1]
# 输出:[1,2,3,5]
# 示例 2:
# 输入:nums = [5,1,1,2,0,0]
# 输出:[0,0,1,1,2,5]
import math
class Solution912:
def sortArray(self, nums: List[int]) -> List[int]:
# return sorted(nums)
def bucket_sort(a, radix=10):
"""a为整数列表, radix为基数"""
if not a: # 检查列表是否为空
return a
max_val = max(a)
if max_val <= 0: # 检查最大值是否大于0
return a
K = int(math.ceil(math.log(max_val, radix))) # 用K位数可表示任意整数
bucket = [[] for _ in range(radix)] # 不能用 [[]]*radix
for i in range(1, K + 1): # K次循环
for val in a:
# 使用整数除法
bucket_index = (val // (radix ** (i - 1))) % radix
bucket[bucket_index].append(val) # 析取整数第K位数字 (从低到高)
del a[:]
for each in bucket:
a.extend(each) # 桶合并
bucket = [[] for _ in range(radix)]
return a
bucket_sort(nums)
return nums
s912 = Solution912()
input_912 = [50, 21, 32, 11]
r912 = s912.sortArray(input_912)
print(f"r912:{r912}") # r912:[11, 21, 32, 50]
# 2343. 裁剪数字后查询第 K 小的数字
# 给你一个下标从 0 开始的字符串数组 nums ,其中每个字符串 长度相等 且只包含数字。
# 再给你一个下标从 0 开始的二维整数数组 queries ,其中 queries[i] = [ki, trimi] 。对于每个 queries[i] ,你需要:
# 将 nums 中每个数字 裁剪 到剩下 最右边 trimi 个数位。在裁剪过后的数字中,找到 nums 中第 ki 小数字对应的 下标 。
# 如果两个裁剪后数字一样大,那么下标 更小 的数字视为更小的数字。
# 将 nums 中每个数字恢复到原本字符串。请你返回一个长度与 queries 相等的数组 answer,其中 answer[i]是第 i 次查询的结果。
# 提示:
# 裁剪到剩下最右边 x 个数位的意思是不断删除最左边的数位,直到剩下 x 个数位。
# nums 中的字符串可能会有前导 0 。
# 示例 1:
# 输入:nums = ["102","473","251","814"], queries = [[1,1],[2,3],[4,2],[1,2]]
# 输出:[2,2,1,0]
# 解释:
# 1. 裁剪到只剩 1 个数位后,nums = ["2","3","1","4"] 。最小的数字是 1 ,下标为 2 。
# 2. 裁剪到剩 3 个数位后,nums 没有变化。第 2 小的数字是 251 ,下标为 2 。
# 3. 裁剪到剩 2 个数位后,nums = ["02","73","51","14"] 。第 4 小的数字是 73 ,下标为 1 。
# 4. 裁剪到剩 2 个数位后,最小数字是 2 ,下标为 0 。
# 注意,裁剪后数字 "02" 值为 2 。
#
# 示例 2:
# 输入:nums = ["24","37","96","04"], queries = [[2,1],[2,2]]
# 输出:[3,0]
# 解释:
# 1. 裁剪到剩 1 个数位,nums = ["4","7","6","4"] 。第 2 小的数字是 4 ,下标为 3 。
# 有两个 4 ,下标为 0 的 4 视为小于下标为 3 的 4 。
# 2. 裁剪到剩 2 个数位,nums 不变。第二小的数字是 24 ,下标为 0 。
class Solution2343:
def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
result = []
for i in queries:
tmp = []
for j in nums:
tmp.append(j[-i[-1]:])
tmp = [(int(i), index) for index, i in enumerate(tmp)]
tmp.sort()
result.append(tmp[i[0] - 1][-1])
return result
s2343 = Solution2343()
r2343 = s2343.smallestTrimmedNumbers(nums=["24", "37", "96", "04"], queries=[[2, 1], [2, 2]])
print(f"r2343:{r2343}") # r2343:[3, 0]
运行结果:文章来源地址https://www.toymoban.com/news/detail-820559.html
r164:13
r912:[11, 21, 32, 50]
r2343:[3, 0]
到了这里,关于数据结构与算法Python版:基数排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!