資源描述：
《3.2比較分類堆分類》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、1§2.Sorting by Comparisons（基于“比較”的分類算法）元素的結(jié)構(gòu)未知2基于“比較‘的分類算法：----是最常用也是最簡(jiǎn)單的分類方法。上面介紹的基數(shù)分類需要知道變程，而基于“比較”的分類方法是：只要是線序集均可進(jìn)行分類。3問題:已知n個(gè)元素的數(shù)組A[1:n]，將A中元素按非降順序排列。4例1:程序3-2-１向有序數(shù)組插入元素TemplateVoidInsert(Ta[],int&n,constT&x){//向數(shù)組a[0:n-1]中插入元素x//假定a的存儲(chǔ)空間大小超過ninti;for(i=n-1;i>=0&&x2、a[i+1]=x;//添加了一個(gè)元素}在程序3-2-１中假定：a中元素在x被插入前后都是按遞增的順序排列的。插入分類算法5我們?nèi)〕跏紨?shù)組a的大小n作為實(shí)例特征，則程序3-2-１的關(guān)鍵操作是x與a中元素的比較。顯然，最少的比較次數(shù)為1，這種情況發(fā)生在x被插在數(shù)組尾部的時(shí)候；最多的比較次數(shù)是n，發(fā)生在x被插在數(shù)組的首部的時(shí)候。6程序3-2-２插入分類templatevoidInsertionSort(Ta[],intn){//對(duì)a[0:n-1]進(jìn)行分類for(inti=1;i3、evoidInsertionSort(Ta[],intn){for(inti=1;i=0&&t4、分成兩部分，先對(duì)每部分進(jìn)行分類，然后再將兩部分已經(jīng)排好序的子數(shù)組的元素按照從小到大的順序交替地?cái)[放在一個(gè)新的數(shù)組中。以下介紹的歸并分類程序，從某種程度上減少了這種浪費(fèi)。這一過程也許需要多次分解和組合，因而是一個(gè)遞歸過程。10例２:程序3-2-４：歸并分類主程序MergeSort(low,high)//A[low:high]是一個(gè)全程數(shù)組，含有//high-low+1個(gè)待分類的元素。integerlow,high;iflow5、//將第二子數(shù)組分類Merge(low,mid,high)//歸并兩個(gè)已經(jīng)分類的子數(shù)組endifendMergeSort歸并分類算法11歸并分類由分解與合并兩部分組成，以含有10個(gè)元素?cái)?shù)組的整個(gè)過程為例，可用兩棵樹表示出來。MergeSort(low,high)調(diào)用（分拆）過程:12Merge(low,mid,high)調(diào)用（合并）過程:Merge(1,1,2)Merge(6,6,7)Merge(4,4,5)Merge(6,7,8)Merge(9,9,10)Merge(1,2,3)Merge(1,3,5)Merge(6,8,10)Merge(1,5,10)13如果用T(n)表示歸并分類所用的時(shí)
6、間，并假定合并過程所用時(shí)間與n成正比：cn，其中c是一個(gè)正數(shù)，則有:其中，a是一個(gè)常數(shù)。若n是2的方冪：n=2k，直接推導(dǎo)可得:14對(duì)于一般的整數(shù)n，我們可以假定，于是，得,15基于“比較”分類算法的時(shí)間下界：我們可以用決策樹(判定樹)來模擬分類算法，在此我們考慮最壞情況下的時(shí)間下限。在樹的內(nèi)部頂點(diǎn)上，算法執(zhí)行一次比較，并根據(jù)比較的結(jié)果移向它的某一個(gè)孩子。由于每?jī)蓚€(gè)元素A[i]和A[j]的比較只有兩種可能：A[i]7、到外頂點(diǎn)路徑即描述了該外頂點(diǎn)所代表的排列生成過程，路徑的長(zhǎng)度即是經(jīng)歷的比較次數(shù)。因此，比較樹中最長(zhǎng)路徑的長(zhǎng)度（其實(shí)就是比較樹的高）就是算法在最壞情況下所做的比較次數(shù)。要求出所有以比較為基礎(chǔ)的分類算法在最壞情況的時(shí)間下界，只需求出這些算法所對(duì)應(yīng)的比較樹的最小高度。如果比較樹的高是k，則該二叉樹的外頂點(diǎn)至多是2k個(gè)。于是，最壞情況下的最少比較次數(shù)T(n)滿足。[seePage15Fig.1.18]3!
