算法导论第八章

发表于 2017-04-27 | 分类于算法导论 | 阅读次数 | 318 words

比较排序

比较排序算法下界
比较排序与决策树（完全二叉树）的关系
决策树高度与比较排序复杂度的关系

运算排序

记数排序

$n$ 个在 $[0, k]$ 的整数，运行时间为 $O(k+n)$
基本思想：对每个输入元素 $x$, 确定不超过 $x$ 的元素的个数
稳定排序：具有相同值的元素在输入和输出数组上顺序一致

非原址排序

def CountingSort(lis, k):
    
    B = []
    for i in range(len(lis)):
        B.append(0)
        
    C = []
    for i in range(k+1):
        C.append(0)
        
    for i in lis:
        C[i] += 1
    for i in range(1,k+1):
        C[i] = C[i]+C[i-1]
        
    for i in range(len(lis)-1,-1,-1):
        B[C[lis[i]]-1] = lis[i]
        C[lis[i]] -= 1
    
    return B

基数排序

$n$ 个在 $d$ 位数，每位有 $k$ 个可能取值，运行时间为 $O(d(k+n))$
基于稳定排序
先按最高有效位 v.s. 先按最低有效位
对位数的灵活分解

桶排序

输入数据服从均匀分布
$n$ 个数据设计 $n$ 个桶
期望运行时间 $\Theta(n)$
$$ T(n) = \Theta(n) + \sum_{i=1}^{n}O(n_i^2) $$

习题

8.1-2, 8.1-3, 8.2-3, 8.2-4, 8.3-2, 8.3-4, 8.3-5, 8.4-4, 8.4-5

# 排序算法