LeetCode 基数排序题解

LeetCode 基数排序题解题目描述实现基数排序算法对一个整数数组进行排序。示例输入[64, 34, 25, 12, 22, 11, 90]输出[11, 12, 22, 25, 34, 64, 90]解题思路方法基数排序思路基数排序的核心思想是按照从低位到高位的顺序对数组中的元素进行排序。具体步骤找出数组中的最大值确定最大位数。从最低位开始对数组中的元素进行计数排序。对每一位进行计数排序直到最高位。最终得到排序后的数组。复杂度分析时间复杂度O(n * k)其中 n 是数组的长度k 是最大位数。空间复杂度O(n k)需要额外的空间来存储计数数组和临时数组。代码实现方法基数排序# 基数排序 def radix_sort(arr): if not arr: return arr # 找出数组中的最大值 max_val max(arr) # 计算最大值的位数 max_digit len(str(max_val)) # 从最低位开始对每一位进行计数排序 for i in range(max_digit): # 计算当前位的除数 divisor 10 ** i # 创建计数数组 count [0] * 10 # 统计每个数字出现的次数 for num in arr: # 提取当前位的数字 digit (num // divisor) % 10 count[digit] 1 # 计算累积计数 for j in range(1, 10): count[j] count[j - 1] # 创建临时数组 temp [0] * len(arr) # 从后向前遍历原数组按照当前位的数字将元素放入临时数组 for j in range(len(arr) - 1, -1, -1): digit (arr[j] // divisor) % 10 temp[count[digit] - 1] arr[j] count[digit] - 1 # 将临时数组复制回原数组 arr temp return arr # 测试 def test_radix_sort(): arr [64, 34, 25, 12, 22, 11, 90] print(radix_sort(arr)) # 输出[11, 12, 22, 25, 34, 64, 90] arr [5, 4, 3, 2, 1] print(radix_sort(arr)) # 输出[1, 2, 3, 4, 5] arr [1, 2, 3, 4, 5] print(radix_sort(arr)) # 输出[1, 2, 3, 4, 5] if __name__ __main__: test_radix_sort()测试用例测试用例 1基本情况输入[64, 34, 25, 12, 22, 11, 90]输出[11, 12, 22, 25, 34, 64, 90]测试用例 2逆序数组输入[5, 4, 3, 2, 1]输出[1, 2, 3, 4, 5]测试用例 3已排序数组输入[1, 2, 3, 4, 5]输出[1, 2, 3, 4, 5]总结基数排序是一种非比较排序算法它按照从低位到高位的顺序对数组中的元素进行排序。基数排序的时间复杂度为 O(n * k)其中 k 是最大位数。基数排序的核心思想是按照从低位到高位的顺序对数组中的元素进行计数排序。基数排序适用于元素范围较大但位数有限的数组当元素的位数较多时基数排序的时间复杂度会增加。掌握基数排序的原理和实现对于理解非比较排序算法非常重要。