基数排序

**基数排序**

基数排序是一种非比较型整数排序算法，主要用于对整数进行排序。它的基本思想是将每个数字按照其各位数字（从最低位开始）进行分组，然后依次对这些分组中的元素进行排序。

### 基数排序流程1. **确定基数**:首先，我们需要确定基数，即我们要根据哪一位数字来进行排序。通常，基数是10，因为我们使用的数字系统是十进制。
2. **计算每个数字的各位值**:接下来，我们需要计算每个数字的各位值（从最低位开始）。例如，对于一个三位数来说，我们需要计算其百位、十位和个位的值。
3. **根据各位值进行分组**:然后，我们根据每个数字的各位值来进行分组。对于基数为10的系统，通常会将数字按照其个位、十位和百位分别进行分组。
4. **对每个分组中的元素进行排序**:最后，我们需要对每个分组中的元素进行排序。由于我们已经根据各位值进行了分组，因此可以使用简单的比较算法来完成这个步骤。

### 基数排序示例假设我们有一个长度为5的整数数组：`[3,6,1,8,2]`

**第一轮（个位）**

| 数字 | 个位 |
| --- | --- |
|3 |3 |
|6 |6 |
|1 |1 |
|8 |8 |
|2 |2 |

**第二轮（十位)**| 数字 | 个位 | 十位 |
| --- | --- | --- |
|3 |3 |0 |
|6 |6 |1 |
|1 |1 |0 |
|8 |8 |2 |
|2 |2 |0 |

**第三轮（百位)**| 数字 | 个位 | 十位 | 百位 |
| --- | --- | --- | --- |
|3 |3 |0 |0 |
|6 |6 |1 |0 |
|1 |1 |0 |0 |
|8 |8 |2 |1 |
|2 |2 |0 |0 |

### 基数排序代码示例

def radix_sort(nums):
 # 确定基数 RADIX =10 # 计算每个数字的各位值 max_length = False tmp , cnt = -1, [0] * RADIX while len(nums) >0:
 tmp +=1 buckets = [ [] for _ in range(RADIX) ]
 # 分配输入中的元素到每个桶中 for i in nums:
 digit = (i // (10 ** cnt)) %10 buckets[digit].append(i)
 # 将数字从小到大排列在输出列表中 nums = []
 for b in buckets: nums += b # 如果最长数字的位数就是当前处理的位数,则跳出 if max_length and tmp == max_length: break cnt[tmp] = len(nums) -1 return nums# 测试基数排序函数nums = [3,6,1,8,2]
print(radix_sort(nums)) # 输出:[1,2,3,6,8]