7计数排序和基数排序.pdf

How fast can we sort? 排序可以多快？ • 插入排序、归并排序、快速排序，它们都 是基于比较的排序：即仅通过元素间比较 确定元素间的顺序。 • 这些基于比较的排序算法，其最坏情形下 的时间开销最小也是O(n lg n) 能否做到比O(n lg n)更好？ • 通过决策树可帮助我们回答这个问题 决策树的例子 对a , a , …, a 排序 1 2 n 每个中间节点标记为i :j ，i, j ∈{1,2,…,n} • 左子树表示当a ≤ a 时接下去比较的情况； i j • 右子树表示当a ≥ a 时接下去比较的情况。 i j 决策树的例子 对a , a , …, a 排序 1 2 n 9, 4, 6 每个中间节点标记为i :j ，i, j ∈{1,2,…,n} • 左子树表示当a ≤ a 时接下去比较的情况； i j • 右子树表示当a ≥ a 时接下去比较的情况。 i j 决策树的例子 对a , a , …, a 排序 1 2 n 9, 4, 6 每个中间节点标记为i :j ，i, j ∈{1,2,…,n} • 左子树表示当a ≤ a 时接下去比较的情况； i j • 右子树表示当a ≥ a 时接下去比较的情况。 i j 决策树的例子 对a , a , …, a 排序 1 2 n 9, 4, 6 每个中间节点标记为i :j ，i, j ∈{1,2,…,n} • 左子树表示当a ≤ a 时接下去比较的情况； i j • 右子树表示当a ≥ a 时接下去比较的情况。 i j 决策树的例子 对a , a , …, a 排序 1 2 n 9, 4, 6 每个叶节点为一个排列π(1), π(2), …,π(n) 它表示序列aπ(1) ≤ aπ(2) ≤ … ≤ aπ(n) 已经建立。 决策树模型 决策树模型可以描述对任何基于比较的排序 算法： • 对于每个输入长度n有一颗决策树 • 算法中任何做比较时，都分为两种情况 • 决策树中包含了算法指令执行过程中的比较序列 • 算法执行时间恰好为到达叶节点的路径长度 • 最坏情形下的执行时间为决策树的高度 决策树排序算法的下限 定理：任何可对n个元素排序的决策树，其高 度一定为Ω(nlgn) 。 证明：树中一定包含有≥n !个叶节点，因为n 个元素具有n !个排列；高度为h的二叉树的 h h 叶节点数