《算法导论》笔记2-8

线性时间排序

计数排序

计数排序假设 n 个输入元素中的每一个都是在 0 到 max 区间内的一个整数。（max 是数组里最大的数字）

基本思想：对每个输入元素 x，确定小于 x 的元素个数。利用这一信息，就可以直接把 x 放到它的输出数组中的位置了。例如如果有 17 个元素小于 x，则 x 就应该在第 18 个输出位置上。当有几个元素相同时，这一方案就要稍作修改，因为不能把它们放在同一输出位置。

假设输入数组是 A[0 … n]，那么我们还需要两个数组：B[0 … n] 输出数组，C[0 … max] 临时数组。

伪代码：

counting_sort(A, B, max)
	C = [max]
	# 初始化
	for i in range(0, max)
		C[i] = 0
	# 计数
	for i in range(0, A.length)
		C[A[i]]++
	# 统计有多少元素 <= i
	for i in range(0, max)
		C[i] += C[i - 1]
	for i in range(0, A.length, -1)
		B[C[A[i]]] = A[i]
		C[A[i]]-- 

基数排序

这里通过实例说： 设有一个初始序列为 A = {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。
为方便说明将这些数字补齐成这样：{050, 123, 543, 187, 049, 030, 000, 002, 011, 100}。

1. 按个位排序：{050, 030, 000, 100, 011, 002, 123, 543, 187, 049}。（50、30、0、100 的个位都是 0）
2. 按十位排序：{000, 100, 002, 011, 123, 030, 543, 049, 050, 187}。（个位排序后顺序判断）
3. 按百位排序：{000, 002, 011, 030, 049, 050, 100, 123, 187, 543}。（十位排序后顺序判断）

最后得到由小到大的序列：{0, 2, 11, 30, 49, 50, 100, 123, 187, 543}。

例如，对 {2010-3-4, 2001-4-30, 2008-8-1, 2001-2-28, 1998-3-8} 按日期从小到大排序。

1. 对日按照上面的个十位排序：{2008-8-1, 2010-3-4, 1998-3-8, 2001-2-28, 2001-4-30}。
2. 对月按照个十位排序：{2001-2-28, 2010-3-4, 1998-3-8, 2001-4-30, 2008-8-1}。
3. 对年按照个十百千位排序：{1998-3-8, 2001-2-28, 2001-4-30, 2008-8-1, 2010-3-4}。

伪代码：

radix_sort(A, highestBit)
	# 从最低位到最高位
	for i in range(1, highestBit)
		# 使用稳定的排序算法对数组 A 排序，比如计数排序
		counting_sort(A, B, max)

桶排序

桶排序假设输入的数据服从均匀分布，平均情况下它的时间代价为 O(n)。

伪代码：

bucket_sort(A)
	n = A.length
	# B 是存放链表（桶）的数组
	B = new [n - 1]
	for i in range(1, n)
		# 把 A[i] 插到 B 对应的桶中
	for i in range(0, n - 1)
		# 对 B 中的每一个桶（即B[i]）都进行排序，比如插入排序
		# 桶里存了若干元素，也就相当于数组
		insert_sort(B[i])
	# 最后把第一个桶到最后一个桶中的所有元素合并起来