算法导论笔记(五)—— Chap 8 线性排序

线性时间排序

计数排序

  • 计数排序假设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
# tmp array now contains the number of elements equal to i
for i in range(1, k+1):
tmp[i] = tmp[i] + tmp[i-1]
# tmp array now contains the number of element less than or equal to i
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])
# print "---", res
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