基数排序

基本概念

基数排序（Radix Sort）基本思想：
按照数字的每一位进行排序，从最低位到最高位，逐位比较。

算法步骤

  1. 确定最大位数：遍历数组，找出最大值的位数
  2. 从最低位开始，到最高位为止，逐位对每一位排序：
    1. 创建10个桶（0-9）
    2. 按照每个元素当前位上的数字，将元素放入对应桶中
    3. 清空原始数组，然后按照桶的顺序依次取出对应元素，重新加入到数组中

内部实现：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
	def radixSort(self,nums:[int])->[int]:
		# 步骤1找出最大位数
		size=len(str(max(nums)))
		# 步骤2 从最低位开始逐位排序
		for i in range(size):
		# 步骤2.1 创建10个桶
			buckets=[[]for _ in range(10)]
		# 步骤2.2 按照每个元素当前位数字，将元素放入对应桶中
			for num in nums:
				buckets[num//(10**i)%10].append(num)
			nums.clear()
			for bucket in buckets:
				for num in bucket:
					nums.append(num)
		return nums
	def sortArray(self,nums:[int])->[int]:
		return self.radixSort(nums)

复杂度分析：

指标 复杂度 说明
最佳时间复杂度 O(n×k) 所有数字位数相同，k 为最大位数
最坏时间复杂度 O(n×k) 所有数字位数相同，k 为最大位数
平均时间复杂度 O(n×k) 基数排序的时间复杂度与数据状态无关
空间复杂度 O(n+k) 需要 n 个元素的存储空间和 k 个桶
稳定性 稳定 桶排序保证相等元素的相对位置不变

适用场景：

  • 整数排序，位数不多（k 较小）
  • 数据范围大但位数固定
  • 电话号码、身份证号等固定位数数据
    基数排序是一种非比较排序算法，通过按位分配和收集实现排序。
  • 优点：时间复杂度与数据范围无关，稳定排序，适合固定位数数据
  • 缺点：空间复杂度较高，只适用于整数排序

应用场景：

  1. 561数组拆分