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

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

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

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

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

首先看看只有三個(gè)元素時(shí)，決策樹(shù)的圖：

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

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

因?yàn)橛衝個(gè)結(jié)點(diǎn)，根據(jù)高中學(xué)的組合排列知識(shí)，知道有n!個(gè)情況，也就是n!個(gè)葉子結(jié)點(diǎn)。

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

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

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