算法分析与设计第5版第3章算法分析题3-3
时间: 2024-05-02 19:21:38 浏览: 26
题目描述:
假设有一个长度为n的数字序列,每个数字的范围是1到k,设计一个时间复杂度为O(n+k)的算法对它进行排序。
算法分析:
本题要求时间复杂度为O(n+k),可以想到计数排序算法。计数排序算法的核心思想是将每个数字在序列中出现的次数统计出来,然后根据每个数字出现的次数,将它们依次放回到原序列中,从而实现排序。
具体实现过程如下:
1. 统计每个数字在序列中出现的次数,用一个数组count来记录。
2. 将count数组中的数字累加,得到count数组中每个数字在排序后序列中的最后一个位置。
3. 将原序列中的每个数字依次插入到排序后序列中对应的位置上。插入过程中需要更新count数组中记录的位置。
4. 将排序后序列返回。
时间复杂度分析:
由于需要遍历原序列一次,统计数字出现次数,时间复杂度为O(n)。
由于数字的范围是1到k,因此count数组的长度为k,遍历count数组一次,时间复杂度为O(k)。
由于需要遍历原序列一次,将每个数字插入到排序后序列中,时间复杂度为O(n)。
因此,总时间复杂度为O(n+k)。
代码实现:
```
def counting_sort(nums, k):
# 统计每个数字在序列中出现的次数
count = [0] * (k + 1)
for num in nums:
count[num] += 1
# 累加count数组中的数字,得到每个数字在排序后序列中的最后一个位置
for i in range(1, k + 1):
count[i] += count[i - 1]
# 将原序列中的每个数字插入到排序后序列中对应的位置上
sorted_nums = [0] * len(nums)
for num in nums:
sorted_nums[count[num] - 1] = num
count[num] -= 1
return sorted_nums
```