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

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

這一節(jié)決策樹其實是對前面的堆排序，快排等是最優(yōu)的比較算法的證明，

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

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

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

在決策樹中，每個內(nèi)結(jié)點都用i:j表示比較下標(biāo)為i數(shù)組元素與下標(biāo)為j的數(shù)組元素的大小。每一個葉結(jié)點是一個n個元素的全排列。

所以排序算法的執(zhí)行對應(yīng)于遍歷一條從樹的根到葉結(jié)點的路徑！

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

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

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

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