用python实现线性排序
时间: 2023-09-23 10:04:55 浏览: 47
线性排序是一种基于计数的排序算法,时间复杂度为O(n+k),其中n是待排序元素的数量,k是元素的取值范围。
以下是Python实现线性排序的示例代码:
```python
def counting_sort(arr):
# 获取数组的长度和最大值
n, k = len(arr), max(arr)
# 创建计数数组,初始化为0
count = [0] * (k+1)
# 统计每个元素出现的个数
for i in arr:
count[i] += 1
# 对计数数组进行前缀和操作,得到每个元素的排名
for i in range(1, k+1):
count[i] += count[i-1]
# 创建临时数组存放排序结果
res = [0] * n
# 从后往前遍历原数组,根据计数数组得到元素的排名
# 将元素放置到临时数组中的对应位置
for i in range(n-1, -1, -1):
res[count[arr[i]]-1] = arr[i]
count[arr[i]] -= 1
return res
```
在上述代码中,我们首先获取待排序数组的长度和最大值,然后创建计数数组并对其进行初始化。接下来,统计每个元素出现的个数,并对计数数组进行前缀和操作,得到每个元素的排名。然后,创建临时数组存放排序结果,从后往前遍历原数组,根据计数数组得到元素的排名,将元素放置到临时数组中的对应位置。最后,返回排序结果。