算法导论笔记（六）—— Chap 9 顺序统计量

顺序统计量

期望为线性时间的选择算法

找出数组nums[p…r]中第i小的元素。最坏运行时间为O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def partition(nums, p, r):
	x = nums[r]
	i = p-1
	for j in range(p, r):
		if nums[j] <= x:
			i += 1
			nums[i], nums[j] = nums[j], nums[i]
	nums[i+1], nums[r] = nums[r], nums[i+1]
	return i+1
def randomoized_partition(nums, p, r):
	i = random.randint(p,r)
	nums[i], nums[r] = nums[r], nums[i]
	return partition(nums, p, r)
def randomized_select(nums, p, r, i):
	if p==r:
		return nums[p]
	q = randomoized_partition(nums, p, r)
	k = q - p + 1
	if i==k:
		return nums[q]
	elif i<k:
		return randomized_select(nums, p, q-1, i)
	else:
		return randomized_select(nums, q+1, r, i-k)
vv