建議先看看前言 ： http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

第八章將介紹幾種非比較排序—計數排序，基數排序，桶排序，這三種排序都在線性時間下運行的。

這一節決策樹其實是對前面的堆排序，快排等是最優的比較算法的證明，

首先說下《算法導論》上對決策樹的定義：一棵決策樹是一棵滿二叉樹(注意看下面解釋)，表示某排序算法作用于給定輸入所做的所有比較，而控制結構，移動等都被忽略了。

注意：這里個人認為定義是錯誤的，決策樹不是一棵滿二叉樹，連完全二叉樹都不是。(不知道有沒有朋友看到這里和我想法一樣？)

首先看看只有三個元素時，決策樹的圖：

在決策樹中，每個內結點都用i:j表示比較下標為i數組元素與下標為j的數組元素的大小。每一個葉結點是一個n個元素的全排列。

所以排序算法的執行對應于遍歷一條從樹的根到葉結點的路徑！

因為有n個結點，根據高中學的組合排列知識，知道有n!個情況，也就是n!個葉子結點。

在決策樹中，從根到任意一個可達葉結點之間的最長路徑的長度，表示對應的排序算法中最壞情況下的比較次數。這樣，一個比較算法的最壞情況的比較次數就是其決策樹的高度。

定理8.1證明了任意一個比較算法在最壞情況下都需要做?(n lg n)次的比較。這個證明比較簡單，可以看看書上的證明過程。

這一節其實沒什么內容，就是一點基本的概念，以及了解比較算法可以通過轉換為決策樹這個模型去理解。