线性时间排序
计数排序
- 计数排序假设n个输入元素中的每一个都是在0到k内的一个整数,其中k为某个整数。当k=O(n)时,排序的运行时间为O(n)。
- 计数排序的基本思想是:对每一个输入元素x,确定小于x的元素个数。(如果有17个元素小于x,则把x放在第18个输出位置上)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| def counting_sort(nums, k): ''' sort nums and the output is res the samples of the nums are between 0 to k :type nums: list :type k: int :rtype: list ''' res = [0]*len(nums) tmp = [0]*(k+1) for i in range(0, len(nums)): tmp[nums[i]] = tmp[nums[i]] + 1 for i in range(1, k+1): tmp[i] = tmp[i] + tmp[i-1] for i in range(len(nums)-1, -1, -1): res[tmp[nums[i]]-1] = nums[i] tmp[nums[i]] = tmp[nums[i]] - 1 return res
|
基数排序
基数排序对于n个d位的元素,先按照最低有效位进行排序。
1 2 3 4 5 6 7 8 9
| def radix_sort(nums, d): ''' use a stable sort to sort array nums on digit i ''' res = nums for i in range(d-1, -1, -1): res = sorted(res, key=lambda num: str(num)[i]) return res
|
桶排序
桶排序假设输入数据服从均匀分布,平均情况下时间代价为O(n)。例如输入均匀独立地分布在[0,1)区间上,桶排序将[0,1)区间分成n个相同大小的子区间,将n个输入数分别放在各个桶中。先对每个桶中的数进行排序,然后遍历每个桶,按照次序把各个桶中的元素列出来即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| def bucket_sort(nums): ''' the samples of the nums are belong [0,1) ''' n = len(nums) res = [[] for _ in range(n)] ans = [] for i in range(0, n): res[int(nums[i]*10)].append(nums[i]) for i in range(0, n): res[i].sort() ans.extend(res[i]) return ans
|