LeetCode 基数排序题解

LeetCode 基数排序题解

题目描述

实现基数排序算法，对一个整数数组进行排序。

示例：

输入：[64, 34, 25, 12, 22, 11, 90]
输出：[11, 12, 22, 25, 34, 64, 90]

解题思路

方法：基数排序

思路：

• 基数排序的核心思想是按照从低位到高位的顺序，对数组中的元素进行排序。
• 具体步骤：
  1. 找出数组中的最大值，确定最大位数。
  2. 从最低位开始，对数组中的元素进行计数排序。
  3. 对每一位进行计数排序，直到最高位。
  4. 最终得到排序后的数组。

复杂度分析：

• 时间复杂度：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 是最大位数。

基数排序的核心思想是：按照从低位到高位的顺序，对数组中的元素进行计数排序。

基数排序适用于元素范围较大但位数有限的数组，当元素的位数较多时，基数排序的时间复杂度会增加。

掌握基数排序的原理和实现，对于理解非比较排序算法非常重要。