數(shù)據(jù)結(jié)構(gòu)與算法第一二部分

數(shù)據(jù)結(jié)構(gòu)與算法第一二部分1第1頁(yè)，共68頁(yè)，2023年，2月20日，星期六課程內(nèi)容及教學(xué)概述第一部分基礎(chǔ)知識(shí)第一章算法在計(jì)算中的作用第二章算法入門第三章函數(shù)的增長(zhǎng)第四章遞歸式第五章概率分析和隨機(jī)算法第二部分排序和順序統(tǒng)計(jì)學(xué)第六章堆排序第七章快速排序第八章線性時(shí)間排序第九章中位數(shù)和順序統(tǒng)計(jì)學(xué)

第2頁(yè)，共68頁(yè)，2023年，2月20日，星期六課程內(nèi)容及教學(xué)概述第三部分?jǐn)?shù)據(jù)結(jié)構(gòu)第十章基本數(shù)據(jù)結(jié)構(gòu)第十一章散列表第十二章二叉查找樹第十三章紅黑樹第十四章數(shù)據(jù)結(jié)構(gòu)的擴(kuò)展第四部分高級(jí)設(shè)計(jì)和分析技術(shù)第十五章動(dòng)態(tài)規(guī)劃第十六章貪心算法第十七章平攤分析第3頁(yè)，共68頁(yè)，2023年，2月20日，星期六課程內(nèi)容及教學(xué)概述第五部分高級(jí)數(shù)據(jù)結(jié)構(gòu)第十八章B樹第十九章二項(xiàng)堆第二十章斐波那契堆第二十一章用于不相交集合的數(shù)據(jù)結(jié)構(gòu)第六部分圖算法第二十二章圖的基本算法第二十三章最小生成樹第二十四章單源最短路徑第二十五章各對(duì)頂點(diǎn)之間的最短路徑第4頁(yè)，共68頁(yè)，2023年，2月20日，星期六第一部分基礎(chǔ)知識(shí)第一章算法在計(jì)算中的作用第二章算法入門第三章函數(shù)的增長(zhǎng)第四章遞歸式第五章概率分析和隨機(jī)算法這部分內(nèi)容主要介紹算法設(shè)計(jì)和分析問題，算法的表達(dá)方法、后面要用到的一些設(shè)計(jì)策略以及許多基本思想第5頁(yè)，共68頁(yè)，2023年，2月20日，星期六第一章算法在計(jì)算中的作用內(nèi)容提要1.1算法1.2作為一種技術(shù)的算法什么是算法？研究算法的目的？第6頁(yè)，共68頁(yè)，2023年，2月20日，星期六第一章算法在計(jì)算中的作用1.1算法簡(jiǎn)單來說，算法（algorithm)就是定義良好的計(jì)算過程，取一個(gè)或一組值作為輸入，并產(chǎn)生一個(gè)或一組輸出。也就是，算法是一系列的計(jì)算步驟，用來將輸入數(shù)據(jù)轉(zhuǎn)換成數(shù)出結(jié)果。第7頁(yè)，共68頁(yè)，2023年，2月20日，星期六1.1算法例如，排序問題描述如下。輸入：由n個(gè)數(shù)據(jù)構(gòu)成的序列<a1,a2,…,an>.輸出：對(duì)輸入序列的排序<a’1,a’2,…,a’n>，使得a’1≤a’2≤…≤a’n.排序是基本的操作，有許多好的算法。排序算法的衡量因素很多，涉及到：數(shù)據(jù)的項(xiàng)數(shù)、已經(jīng)排好的程度、對(duì)數(shù)據(jù)項(xiàng)取值可能的限制、存儲(chǔ)設(shè)備的類型（內(nèi)存、磁盤、磁帶）等第8頁(yè)，共68頁(yè)，2023年，2月20日，星期六1.1算法算法的正確性：如果一個(gè)算法對(duì)每個(gè)輸入都能得到正確的結(jié)果，并停止，則稱為是正確的。不正確的算法對(duì)某些輸入來說，可能不會(huì)停止，或得到的不是預(yù)期的結(jié)果。有時(shí)，如果算法的錯(cuò)誤率可以得到控制的話，有時(shí)也是有用的。算法的描述：自然語(yǔ)言、計(jì)算機(jī)語(yǔ)言等。要求：算法的規(guī)格說明必須提供關(guān)于代碼運(yùn)行的計(jì)算過程的精確描述。第9頁(yè)，共68頁(yè)，2023年，2月20日，星期六1.1算法算法可以解決哪些類型的問題？舉例互聯(lián)網(wǎng)信息：管理、操作、檢索、搜索引擎。互聯(lián)網(wǎng)中的路由選擇電子商務(wù)：信用卡號(hào)、密碼、銀行結(jié)單等的私密性與欺詐檢測(cè)。欺詐檢測(cè)物流配送第10頁(yè)，共68頁(yè)，2023年，2月20日，星期六1.1算法應(yīng)用舉例生物信息學(xué)領(lǐng)域：人類基因項(xiàng)目的目標(biāo)是：找出人類DNA中的所有100000種基因，確定構(gòu)成人類DNA的30億種化學(xué)基對(duì)的各種序列，儲(chǔ)存在數(shù)據(jù)庫(kù)中，并開發(fā)出用于分析的工具。

------每一步驟都需要復(fù)雜的算法。制造業(yè)：稀有資源的分配。。。。。第11頁(yè)，共68頁(yè)，2023年，2月20日，星期六1.1算法各領(lǐng)域的例子形式上存在較大差異，但其底層所涉及到的支撐技術(shù)具有許多共性。許多有趣算法的兩個(gè)共同特征：有很多候選的解決方案，其中大多數(shù)都不是所需要的。找到真正需要的解決方案往往不容易。有實(shí)際的應(yīng)用。最短路徑：運(yùn)輸公司成本；互聯(lián)網(wǎng)中：路由節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)算法必然涉及到數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的組織方式。不同特性和應(yīng)用場(chǎng)合。算法設(shè)計(jì)和分析技術(shù)面臨新的問題時(shí)所需要的技術(shù)第12頁(yè)，共68頁(yè)，2023年，2月20日，星期六1.1算法關(guān)于NP完全問題-----有趣的問題：迄今為止，沒有找出NP完全問題的有效解法，但也沒有人能證明NP完全問題的有效解法是不存在的。如果NP問題中的任何一個(gè)問題存在有效算法，則該集合中其他所有問題都存在有效算法。有幾個(gè)NP完全問題類似于（但又不完全同于）一些有著已知有效算法的問題，對(duì)一個(gè)陳述的一點(diǎn)小小改動(dòng)，就會(huì)對(duì)其一直最佳算法的效率帶來很大的變化。來自于實(shí)踐，有了解或研究的必要。避免不必要的徒勞。例如：配貨車的最短路徑規(guī)劃問題----旅行商問題。第13頁(yè)，共68頁(yè)，2023年，2月20日，星期六1.2作為一種技術(shù)的算法由于計(jì)算機(jī)的計(jì)算速度、存儲(chǔ)空間總是有一定的局限，因此，研究性能更好的算法成為與研究高性能硬件類似的技術(shù)。例：幻方問題（縱橫圖）將1～n２放在n＊n（n為奇數(shù)）的方陣中，使得任意一行任意一列以及兩條對(duì)角線上的所有元素之和均相等。如n=5時(shí)的方陣如下圖所示。15８１241716147５232220136432119121092251811第14頁(yè)，共68頁(yè)，2023年，2月20日，星期六這一問題如果采用試探的方法，在ｎ值較大時(shí)，將難以求出，因?yàn)榭赡艿臓顟B(tài)數(shù)是ｎ２！個(gè)。經(jīng)典的構(gòu)造方法如下：將數(shù)1放在第一行的中間元素，然后往左上的位置上放入下一個(gè)數(shù)。若左上的位置已有數(shù)，則將其放入該數(shù)的下一行中的同一列的位置上。若已是最左或最上面位置上的元素，則其下一個(gè)位置的尋找方法是：將方陣卷成一個(gè)紙筒，然后依此再按同樣的方向再找下一個(gè)位置，直到n×n個(gè)元素全部放入為止。1.2作為一種技術(shù)的算法15８１241716147５232220136432119121092251811第15頁(yè)，共68頁(yè)，2023年，2月20日，星期六1.2作為一種技術(shù)的算法ｎ＝５時(shí)的求解過程如下：１２

３

４

５

６

７８９１０１１１２１３１４１５１６１７１８１９２０２１２２２３２４２５第16頁(yè)，共68頁(yè)，2023年，2月20日，星期六第二章算法入門內(nèi)容提要插入排序算法分析算法設(shè)計(jì)第17頁(yè)，共68頁(yè)，2023年，2月20日，星期六2.1插入排序先從插入排序算法開始排序問題描述如下。輸入：由n個(gè)數(shù)據(jù)構(gòu)成的序列<a1,a2,…,an>.輸出：對(duì)輸入序列的排序<a’1,a’2,…,a’n>，使得a’1≤a’2≤…≤a’n.插入排序的基本思想：將待排序表看作是左右兩部分，其中左邊為有序區(qū)，右邊為無序區(qū)，整個(gè)排序過程就是將右邊無序區(qū)中的元素逐個(gè)插入到左邊的有序區(qū)中，以構(gòu)成新的有序區(qū)。類似于打牌時(shí)摸牌的過程，逐漸將抓到的牌插入到合適的位置上。

第18頁(yè)，共68頁(yè)，2023年，2月20日，星期六2.1插入排序偽代碼如下：voidinsert_sort(elementtypeA[n+1]){for(i=2;i<=n;i++)//i表示待插入元素的下標(biāo)

{temp=A［i］;//臨時(shí)保存待插入元素，以騰出A［i］的空間

j=i-1;//j指示當(dāng)前空位置的前一個(gè)元素

while(j>=1&&A［j］.key>temp.key)//搜索插入位置并騰空位

{A［j+1］=A［j］;j=j-1;}A［j+1］=temp;//插入元素

}}第19頁(yè)，共68頁(yè)，2023年，2月20日，星期六2.1插入排序求解過程簡(jiǎn)述循環(huán)不變式A12345n…………a1a2a3a4a5an

TempX第20頁(yè)，共68頁(yè)，2023年，2月20日，星期六2.1插入排序循環(huán)不變式與正確性證明證明3個(gè)性質(zhì)：初始化：循環(huán)的第一輪迭代開始前，應(yīng)該是正確的。保持：如果在循環(huán)的某次迭代之前是正確的，則在下一次迭代開始前，也應(yīng)該保持正確。終止：當(dāng)循環(huán)結(jié)束時(shí)，不變式給了一個(gè)有用的性質(zhì)，有助于表明算法是正確的。前兩個(gè)性質(zhì)成立時(shí)，就能保障循環(huán)不變式再循環(huán)的每一輪迭代開始前都是正確的。

------與數(shù)學(xué)歸納法類似。證明過程：類似于歸納法初始化的證明。保持的證明。終止的證明。第21頁(yè)，共68頁(yè)，2023年，2月20日，星期六2.2算法分析算法分析就是對(duì)算法所需要的資源進(jìn)行預(yù)測(cè)。資源涉及到：時(shí)間開銷內(nèi)存硬件資源通信帶寬嚴(yán)格來說，需要對(duì)相關(guān)資源建模，以準(zhǔn)確描述。例如，關(guān)于RAM、時(shí)間、硬件等的模型。然而，準(zhǔn)確的描述是困難的。所用的數(shù)學(xué)模型，如組合數(shù)學(xué)、概率論等構(gòu)建困難。指令的執(zhí)行時(shí)間如果太精細(xì)要求，也是困難的。資源、數(shù)據(jù)的規(guī)模等都存在較大差異。第22頁(yè)，共68頁(yè)，2023年，2月20日，星期六2.2算法分析插入算法的分析voidinsert_sort(elementtypeA[n+1]){for(i=2;i<=n;i++){temp=A［i］;j=i-1;while(j>=1&&A［j］.key>temp.key){A［j+1］=A［j］;j=j-1;}A［j+1］=temp;}}n次n-1次n-1次n-1次各次循環(huán)次數(shù)和n-1次第23頁(yè)，共68頁(yè)，2023年，2月20日，星期六2.2算法分析空間性能:需要一個(gè)記錄的輔助存儲(chǔ)空間。時(shí)間性能:與數(shù)據(jù)表初始狀態(tài)有關(guān)

最好（有序）最壞（逆序）平均

比較：

n-1(n+2)(n-1)/2O(n2)

移動(dòng)：

2(n-1)(n+4)(n-1)/2因而適用于基本有序，規(guī)模小的數(shù)據(jù)第24頁(yè)，共68頁(yè)，2023年，2月20日，星期六2.3算法設(shè)計(jì)算法設(shè)計(jì)涉及到多種技術(shù)例如：增量式方法，插入排序就是采用的這種方法：先排好數(shù)組A[1..i-1],然后再將A[i]插入其中，以構(gòu)成新的有序子數(shù)組。還有多種算法設(shè)計(jì)技術(shù)，例如：分治法動(dòng)態(tài)規(guī)劃法貪心法等。第25頁(yè)，共68頁(yè)，2023年，2月20日，星期六2.3.1分治法分治法(divide-and-conquer)許多問題的求解技術(shù)可以這樣進(jìn)行：原問題可以分解為若干子問題分別進(jìn)行求解，適當(dāng)綜合子問題的解，可以得到原問題的解。其中，在許多情況下，各子問題得求解方法與原問題的求解方法類似，因而可以采用遞歸技術(shù)來實(shí)現(xiàn)。例如：二分查找方法快速排序算法第26頁(yè)，共68頁(yè)，2023年，2月20日，星期六2.3.1分治法分治法在每一層遞歸上都有3個(gè)步驟：分解（Devide)：將原問題分解成一系列子問題；求解（Conquer):遞歸地求解各子問題，若子問題“足夠小”（遞歸出口），則直接求解。合并（combine)：合并子問題的解，以求解原問題的解。例如，歸并排序（mergesort）的操作：分解：分解數(shù)組為兩個(gè)n/2規(guī)模的數(shù)組；求解：對(duì)兩個(gè)子序列分別采用歸并排序進(jìn)行求解；合并：合并兩個(gè)已排序子序列，得到排序結(jié)果。其它例子：二分查找方法，快速排序算法第27頁(yè)，共68頁(yè)，2023年，2月20日，星期六2.3.1分治法歸并排序（mergesort）的操作分析：關(guān)鍵操作是合并：為此，引入一個(gè)函數(shù)Merge(A,p,q,r),其功能是：合并已排序子序列A[p..q]和A[q+1..r]，得到已排序子序列A[p..r]。

merge(A,p,q,r){len1=p-q+1;len2=q-r;for(i=1;i<=lenq;i++)L[i]=A[p+i-1];//復(fù)制到另外的數(shù)組中

for(i=1;i<=len2;i++)R[i]=A[q+i];i1=1;i2=1;L[len+1]=∞;R[len2]=∞;//設(shè)置監(jiān)視哨

for(k=p;k<=r;k++)if(L[i1]<=R[i2]){A[k]=L[i1];k++;i1++;}else{A[k]=L[i2];k++;i2++;}}第28頁(yè)，共68頁(yè)，2023年，2月20日，星期六2.3.2分治法分析正確性證明：

初始化：第一輪之前，即k=p時(shí)，是正確的。

保持：證明每一輪迭代正確。(之前正確，之后也正確)終止：最后一輪正確。第29頁(yè)，共68頁(yè)，2023年，2月20日，星期六2.3.2分治法分析性能分析：時(shí)間性能：分解：不費(fèi)時(shí)間求解：2T（n/2）合并：O(n)

2T（n/2）+O(n)=>整個(gè)排序：分析可參見樹形描述，可知為O(nlogn)空間性能：不能就地歸并，一倍的輔助制空間ABCGFDajara1a2apa3alapE第30頁(yè)，共68頁(yè)，2023年，2月20日，星期六第三章函數(shù)的增長(zhǎng)時(shí)間函數(shù)的描述:對(duì)給定的函數(shù)g(n),用O(g(n)表示函數(shù)集合：

O(g(n)={f(n)|存在常數(shù)c1,c2和n0,使得對(duì)所有的n>=n0，有0<=c1g(n)<=f(n)<=c2g(n)}

可以表示為f(n)=O(g(n)第31頁(yè)，共68頁(yè)，2023年，2月20日，星期六第四章遞歸式當(dāng)算法遞歸調(diào)用時(shí)，運(yùn)行時(shí)間通?？梢杂眠f歸式來表示。例如Merge_sort算法的時(shí)間函數(shù)T(n)：

O(1)n=1T(n)=2T（n/2）+O(n)n>1

解為O(nlogn)

如何求解？代換法，遞歸樹方法，主方法第32頁(yè)，共68頁(yè)，2023年，2月20日，星期六4.1代換法代換法求解的兩個(gè)步驟：（1）猜測(cè)解的形式（2）用數(shù)學(xué)歸納法找出使得解真正有效的常數(shù)只能用于容易猜測(cè)的情形。例，確定遞歸式2T（n/2）+n的解為此，先猜測(cè)T(n)=O(nlogn),

然后證明T(n)<=cnlogn(c是某個(gè)常數(shù)）先假設(shè)：對(duì)n/2成立，即T(n/2)<=cn/2log(n/2),

則T(n)=2T（n/2）+n<=2(cn/2log(n/2))+n<=cnlog(n/2)+n=cnlogn-cnlog2+n<=cnlogn

問題：取決于猜測(cè)第33頁(yè)，共68頁(yè)，2023年，2月20日，星期六4.2遞歸樹方法歸并排序算法分析時(shí)，用到了遞歸樹描述。每個(gè)節(jié)點(diǎn)代表：遞歸函數(shù)調(diào)用集合中的一個(gè)子問題的代價(jià)。將每一層內(nèi)的代價(jià)相加，得到一層的代價(jià)；各層的代價(jià)和，構(gòu)成總代價(jià)。更適合于分治法求解算法的分析描述。第34頁(yè)，共68頁(yè)，2023年，2月20日，星期六4.2遞歸樹方法T(n)=3T(n/4)=cn2的求解示例cn2T(n/4)T(n)(a)(b)T(n/4)T(n/4)cn2c(n/4)2T(n/16)c(n/4)2c(n/4)2T(n/16)T(n/16)T(n/16)T(n/16)T(n/16)T(n/16)T(n/16)T(n/16)(c)cn23/16c(n/4)29T(n/16)第35頁(yè)，共68頁(yè)，2023年，2月20日，星期六4.3主方法主方法（mastermethod)主方法給出求解如下形式的遞歸式方法：

T(n)=aT(n/b)+f(n)

其中，a>=1,b>1是常數(shù)

f(n)是漸近正的函數(shù)。描述了將規(guī)模為n的問題劃分為a個(gè)子問題的算法的運(yùn)行時(shí)間，每個(gè)子問題的規(guī)模為n/b。每個(gè)子問題的求解時(shí)間為T(n/b)，劃分和合并的時(shí)間為f(n).第36頁(yè)，共68頁(yè)，2023年，2月20日，星期六第二部分排序和順序統(tǒng)計(jì)學(xué)

排序是軟件設(shè)計(jì)中最常見的運(yùn)算之一，因而成為算法分析與設(shè)計(jì)中最常用的討論對(duì)象。已經(jīng)提出了許多排序算法。按照所用到的基本方法，可概括為：插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序等。排序——將數(shù)據(jù)表（a1,a2,……，an）調(diào)整為按關(guān)鍵字從?。ù螅┑酱螅ㄐ。┡帕械倪^程。排序問題描述如下。輸入：由n個(gè)數(shù)據(jù)構(gòu)成的序列<a1,a2,…,an>.輸出：對(duì)輸入序列的排序<a’1,a’2,…,a’n>，使得a’1≤a’2≤…≤a’n.第37頁(yè)，共68頁(yè)，2023年，2月20日，星期六第六章堆排序堆排序：利用堆進(jìn)行的排序。屬于選擇排序一類。定義：稱n個(gè)元素組成的序列(a1,a2,…，an)

為堆，當(dāng)且僅當(dāng)滿足下面關(guān)系。（其中ki是元素ai的關(guān)鍵字）

（1）ki≤k2i;ki≤k2i+1(2i≤n；2i+1≤n)

或 （2）ki≥k2i;

ki≥k2i+1 (2i≤n；2i+1≤n)如果將此序列對(duì)應(yīng)到編號(hào)的完全二叉樹，

a1a2a3a7a6a5a8a9a4a11a10a13a1212345678910111213…第38頁(yè)，共68頁(yè)，2023年，2月20日，星期六第六章堆排序如果將此序列對(duì)應(yīng)到編號(hào)的完全二叉樹，則堆的定義可用完全二叉樹中的有關(guān)術(shù)語(yǔ)解釋為：每一結(jié)點(diǎn)均不大于(或不小于）其左、右孩子結(jié)點(diǎn)的值。若序列(a1,a2,…,an)是堆，則堆頂(完全二叉樹的根)必為序列中的最小或最大值。將根最大的堆稱為大根堆，根最小的堆稱為小根堆.a1a2a3a7a6a5a8a9a4a11a10a13a1212345678910111213…ai≥a2i;ai≥

a2i+1第39頁(yè)，共68頁(yè)，2023年，2月20日，星期六第六章堆排序—堆示例1009080706065553050103020405065758090大根堆小根堆第40頁(yè)，共68頁(yè)，2023年，2月20日，星期六第六章堆排序—堆示例例：判斷下面數(shù)據(jù)是否是堆：(5,23,16,68,64,72,71,73,45,79,90,81,75,94,97)解：對(duì)應(yīng)的二叉樹形式如下：52316686472717345799081759497123456789101112131415不是堆！第41頁(yè)，共68頁(yè)，2023年，2月20日，星期六第六章堆排序堆排序思想（約定進(jìn)行增排序，因而采用大根堆）如果初始序列是堆，則可通過反復(fù)執(zhí)行如下操作而最終得到一個(gè)有序序列：篩選過程即輸出根：即將根（第一個(gè)元素）與當(dāng)前子序列中的最后一個(gè)元素交換。調(diào)整堆：將輸出根之后的子序列調(diào)整為堆。如果初始序列不是堆，則首先要將其先建成堆，然后再按（1）的方式來實(shí)現(xiàn)。第42頁(yè)，共68頁(yè)，2023年，2月20日，星期六第六章堆排序由此可知，實(shí)現(xiàn)堆排序需要解決兩個(gè)問題：（1）如何由一個(gè)無序序列建成一個(gè)堆？（2）如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個(gè)新的堆？問題（2）的解決方法是：在輸出堆頂元素之后，以堆中最后一個(gè)元素替代之，此時(shí)根結(jié)點(diǎn)的左、右子樹均為堆，則僅需自上至下進(jìn)行調(diào)整即可。我們稱自堆頂至葉子的調(diào)整過程為“篩選”。問題1的解決方法是：從一個(gè)無序序列建堆的過程就是一個(gè)反復(fù)“篩選”的過程。若將此序列看成是一個(gè)完全二叉樹，則最后一個(gè)非終端結(jié)點(diǎn)是第?n/2?個(gè)元素，由此“篩選”只需從第?n/2?個(gè)元素開始。第43頁(yè)，共68頁(yè)，2023年，2月20日，星期六1009080706065553050100509050輸出根：100705090第六章堆排序第44頁(yè)，共68頁(yè)，2023年，2月20日，星期六第六章堆排序907080506065553050100308030輸出根：1006530909080第45頁(yè)，共68頁(yè)，2023年，2月20日，星期六第六章堆排序voidsift(elementtypeA[],intn,intk,intm)//對(duì)數(shù)組中下標(biāo)為1～n中的元素中的序號(hào)不大于m的以k為根的子序列調(diào)整{x=A[k];finished=FALSE；

i=k;j=2*i;//i指示空位，j先指向左孩子結(jié)點(diǎn)

while(j<=m&&!finished){if(j<m&&A[j].key<A[j+1].key)j=j+1;//讓j指向左右孩子中的最大者

if(x.key>=A[j].key)finished=TRUE;//根最大

else{A[i]=A[j];//大的孩子結(jié)點(diǎn)值上移

i=j;j=2*j;}//繼續(xù)往下篩選

}A[i]=x;}第46頁(yè)，共68頁(yè)，2023年，2月20日，星期六如何由一個(gè)無序序列建成一個(gè)堆？通過反復(fù)調(diào)用篩選操作來實(shí)現(xiàn)。建堆過程要從下往上逐棵子樹地進(jìn)行篩選，即根的下標(biāo)按照從n/2到1的次序?qū)⒏髯訕湔{(diào)整為堆。第六章堆排序第47頁(yè)，共68頁(yè)，2023年，2月20日，星期六第六章堆排序例：由初始序列（12,15,30,80,100,46,78,33,90,86,64,55,120,230,45）建大根堆1215308010046783390866455120230452345678910111213141512307812046908023030783010015861523012120125512建成的堆：(230,100,120,90,86,55,78,33,80,15,64,12,46,30,45)

第48頁(yè)，共68頁(yè)，2023年，2月20日，星期六第六章堆排序voidheap_sort(elementtypeA[],intn){for(i=n/2;i>=1,i--)sift(A,i,n);//建初始堆

for(i=n;i>=2;i--){A[i]<==>A[1];//輸出根

sift(A,1,i-1);//調(diào)整子序列為堆

}}算法正確性證明：初始化：保持：終止：第49頁(yè)，共68頁(yè)，2023年，2月20日，星期六第六章堆排序算法時(shí)間復(fù)雜度分析：

voidsift(elementtypeA[],intn,intk,intm)//對(duì)數(shù)組中下標(biāo)為1～n中的元素中的序號(hào)不大于m的以k為根的子序列調(diào)整{x=A[k];finished=FALSE；

i=k;j=2*i;//i指示空位，j先指向左孩子結(jié)點(diǎn)

while(j<=m&&!finished){if(j<m&&A[j].key<A[j+1].key)j=j+1;//讓j指向左右孩子中的最大者

if(x.key>=A[j].key)finished=TRUE;//根最大

else{A[i]=A[j];//大的孩子結(jié)點(diǎn)值上移

i=j;j=2*j;}//繼續(xù)往下篩選

}A[i]=x;}

O(nlog2n)a1a2a3a7a6a5a8a9a4a11a10a13a1212345678910111213…第50頁(yè)，共68頁(yè)，2023年，2月20日，星期六第七章快速排序基本思想：分治法

將數(shù)據(jù)表劃分為左右兩部分，其中：左邊的所有元素都小于右邊的所有元素；然后，對(duì)左右兩部分分別進(jìn)行快速排序。劃分方法：選定一個(gè)參考點(diǎn)（中間元素），所有元素與之相比較，小的放左邊，大的放右邊。第51頁(yè)，共68頁(yè)，2023年，2月20日，星期六第七章快速排序具體劃分方法：選擇第一個(gè)元素作為中間元素。劃分：(1)先保存該元素的值到其它位置，騰出其空間。(2)從后往前搜索一個(gè)比中間數(shù)小的元素，并將其放置到前面的這個(gè)空位上。(3)從前往后搜索一個(gè)比中間數(shù)大的元素，并將其放置到后面的這個(gè)位置上。重復(fù)(2)，(3)，直到兩邊搜索的空位重合時(shí)為止，此時(shí)將中間元素放在該空位中。第52頁(yè)，共68頁(yè)，2023年，2月20日，星期六用快速排序算法對(duì)數(shù)據(jù)表從小到大進(jìn)行排序。

A=(12,5,4,19,25,1,34,7,10,23,8,5)第七章快速排序解：(125419251347102385)5x=12

12

5419

8

25

2310

134

7

()()

71

548

105()()12

19

232534()

4515

7

810()()()12

252319()341

4

55

87101219

252334()()第53頁(yè)，共68頁(yè)，2023年，2月20日，星期六第七章快速排序voidpartition(elementtypeA[n],ints,intt,int*cutpoint)//對(duì)數(shù)組A中下標(biāo)為s～t的子表進(jìn)行劃分{x=A[s];//保存中間元素，騰出空位

i=s;j=t;while(i!=j){while(i<j&&A[j].key>x.key)j--;if(i<j){A[i]=A[j];i=i+1;}while(i<j&&A[i].key<x.key)i++;if(i<j){A[j]=A[i];j=j-1;}}A[i]=x;*cutpoint=i;}第54頁(yè)，共68頁(yè)，2023年，2月20日，星期六第七章快速排序//對(duì)數(shù)組A中下標(biāo)從s到t的元素組成的子表快速排序voidQuick_sort(elementtypeA[n],ints,intt){if(s<t){partition(A,s,t,*i);//劃分

Quicksort(A,s,*i-1);//對(duì)前面子表快速排序

Quicksort(A,*i+1,t);//對(duì)后面子表快速排序

}}第55頁(yè)，共68頁(yè)，2023年，2月20日，星期六第七章快速排序時(shí)間復(fù)雜度分析：（可先畫出其遞歸樹，再分析）一般情況(每次等分子表):因此，T(n)=2T（n/2）+O(n)=>整個(gè)排序：分析可參見樹形描述，可知為O(nlogn)O(nlog2n)（a1a2a3an

）表長(zhǎng)為n（a1’a2’)x(a3’an’）表長(zhǎng)為n/2（）（）（）（）（）每個(gè)表長(zhǎng)為1nn/2n/2---n---n---nlogn…第56頁(yè)，共68頁(yè)，2023年，2月20日，星期六第七章快速排序最壞情況（每次劃分的結(jié)果是1：k-1）：T(n)=T（n-1）+c(n)T(n)=O(n2)快速排序的平均時(shí)間接近于最佳時(shí)間，例如，即使是每次的劃分是9：1。T(n)=T（9n/10）+T(n/10)+c(n)仍是O(nlogn)數(shù)量級(jí)的。

nn/1081n/100---cn---cn---cnLog10/9n…1log10n9n/10第57頁(yè)，共68頁(yè)，2023年，2月20日，星期六第七章快速排序正確性證明：初始化：保持：終止：voidpartition(elementtypeA[n],ints,intt,int*cutpoint)//對(duì)數(shù)組A中下標(biāo)為s～t的子表進(jìn)行劃分{x=A[s];//保存中間元素，騰出空位

i=s;j=t;while(i!=j){while(i<j&&A[j].key>x.key)j--;if(i<j){A[i]=A[j];i=i+1;}while(i<j&&A[i].key<x.key)i++;if(i<j){A[j]=A[i];j=j-1;}}A[i]=x;*cutpoint=i;}第58頁(yè)，共68頁(yè)，2023年，2月20日，星期六第八章線性時(shí)間排序8.1排序算法時(shí)間下界前述排序算法都是比較排序：元素間的次序基于元素間的比較時(shí)間復(fù)雜度下界為O(nlgn).排序性能分析的決策樹模型以3個(gè)元素的比較為例第59頁(yè)，共68頁(yè)，2023年，2月20日，星期六8.1排序算法時(shí)間下界以3個(gè)元素的比較為例內(nèi)部節(jié)點(diǎn)：對(duì)應(yīng)一個(gè)比較操作分支：對(duì)應(yīng)一次比較的一種情況葉子節(jié)點(diǎn)：對(duì)應(yīng)一個(gè)排列1：2≤>2：31：3(1,2,3)1：3(2,1,3)2：3(1,3,2)(3,1,2)(2,3,1)