决策树和桶排序

决策树

决策树（decision tree）是用于证明下界的抽象概念。每个节点表示在元素之间一组可能的排序，它与已经进行的比较一致。比较的结果是树的边。

只是用比较进行排序的每一种算法都可以用决策树表示。当然，只有输入数据非常少的情况下画决策树才是可行的。排序算法所使用的比较次数等于最深的树叶的深度。所使用的比较的平均次数等于树叶的平均深度。由于决策树很大，因此必然存在一些长的路径。

引理 1：令 T 是深度为 d 的二叉树，则 T 最多有 片树叶。

引理 2：具有 L 片树叶的二叉树的深度至少是 。

引理 3：只使用元素间比较的任何排序算法在最坏情形下至少需要 次比较。

引理 4：只使用元素间比较的任何排序算法需要进行 次比较。

桶排序

为使桶排序能够正常工作，必须要有一些额外的信息。输入数据 必须只由小于 M 的正整数组成。（显然还可以对其进行扩充。）如果是这种情况，那么算法很简单：使用一个大小为 M 称为 Count 的数组，它被初始化为全 0。于是，Count 有 M 个单元（或称桶），这些桶初始化为空。当读 时， 增 1。在所有的输入数据读入后，扫描数组 Count，打印除排序后的表。该算法用时 。

尽管桶排序看似太平凡，用处不大，但是实际上却存在许多其输入只是一些小的整数的情况，使用像快速排序这样的排序方法真的是小题大做了。