首页 / 软件开发 / 数据结构与算法 / 【算法导论】排序 （四）：决策树、线性时间排序（计数、基数、桶排序）

【算法导论】排序 （四）：决策树、线性时间排序（计数、基数、桶排序）2014-01-01 csdn shuangde800到目前为止，一共整理总结了五大排序算法：

1、插入排序

2、冒泡排序、选择排序、交换排序 （把这三种方法归为一种，因为他们的思想本质上都是一样的）

3、归并排序

4、堆排序

5、快速排序

以上五种排序都可以称为“比较排序”，顾名思义，因为他们都是基于比较元素 来决定其相对位置的。

其中前两种的时间为O（n^2），归并排序和堆排序最坏O（ n lg n ），快排平 均O（ n lg n ）

定理：任意一种比较排序算法最坏情况下，都需要做 Ω（ n lg n ）次的比较。

我们通过决策树来证明：

●决策树（decision tree）

比较排序可以被抽象的视为决 策树。撒一颗决策树是一颗满二叉树，表示某排序算法作用于给定输入元素所作的所有比较，而其它因素忽 略。

假设有一组三个元素的序列,我们用1，2，3来分别表示这三个元素，我们基于比较来对它排序， 可以有下列决策树：

不难发现，判定树的叶子表示了三个元素的所有可能排列。

另外，用比较排序对这三个元素进行排序 的话，你总可以找到一条路径来表示它的整个比较过程。（需要注意的是，1并不表示它代表第一个元素，它 可以代表三个元素中任意一个。2，3也相同。但是1，2，3不指向相同元素）。显然最坏情况下的复杂度即是 判定树的高。

对于一颗高度为H的、具有L个可达叶节点的决策树，它对应于对N个元素所作的比较排 序。因为N个元素有N！种排列（排列组合知识）， 每一种都作为一个叶子出现在书中，故有N！<=L（重要, 注：）有又由于在一颗高为H的二叉树中，叶子的数目不多于2^H,则有 N！ <= L <= 2^H

对该式 子取对数,得到：

        H>=lg（N！）      （因为lg函 数时单调递增的）

            =Ω（N lg N）

注： 一开始我以 为应该是等于的关系，后来百度了一下，原文有这一句：Because each of the N！ permutation appears as areachable leaf. 作者的意思着重于用N！来表示N个元素的所有可能排列，但是N个元素的所有可能排列实 际上是小于等于N！的，因为在N个元素中有可能有相等的元素。