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

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

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

３

４

５

６

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

第十八頁，共六十八頁，編輯于2023年，星期三2.1插入排序偽代碼如下：voidinsert_sort(elementtypeA[n+1]){for(i=2;i<=n;i++)//i表示待插入元素的下標(biāo)

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

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

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

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

}}第十九頁，共六十八頁，編輯于2023年，星期三2.1插入排序求解過程簡述循環(huán)不變式A12345n…………a1a2a3a4a5an

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

------與數(shù)學(xué)歸納法類似。證明過程：類似于歸納法初始化的證明。保持的證明。終止的證明。第二十一頁，共六十八頁，編輯于2023年，星期三2.2算法分析算法分析就是對算法所需要的資源進(jìn)行預(yù)測。資源涉及到：時間開銷內(nèi)存硬件資源通信帶寬嚴(yán)格來說，需要對相關(guān)資源建模，以準(zhǔn)確描述。例如，關(guān)于RAM、時間、硬件等的模型。然而，準(zhǔn)確的描述是困難的。所用的數(shù)學(xué)模型，如組合數(shù)學(xué)、概率論等構(gòu)建困難。指令的執(zhí)行時間如果太精細(xì)要求，也是困難的。資源、數(shù)據(jù)的規(guī)模等都存在較大差異。第二十二頁，共六十八頁，編輯于2023年，星期三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次第二十三頁，共六十八頁，編輯于2023年，星期三2.2算法分析空間性能:需要一個記錄的輔助存儲空間。時間性能:與數(shù)據(jù)表初始狀態(tài)有關(guān)

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

比較：

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

移動：

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

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

保持：證明每一輪迭代正確。(之前正確，之后也正確)終止：最后一輪正確。第二十九頁，共六十八頁，編輯于2023年，星期三2.3.2分治法分析性能分析：時間性能：分解：不費(fèi)時間求解：2T（n/2）合并：O(n)

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

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

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

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

解為O(nlogn)

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

然后證明T(n)<=cnlogn(c是某個常數(shù)）先假設(shè)：對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

問題：取決于猜測第三十三頁，共六十八頁，編輯于2023年，星期三4.2遞歸樹方法歸并排序算法分析時，用到了遞歸樹描述。每個節(jié)點(diǎn)代表：遞歸函數(shù)調(diào)用集合中的一個子問題的代價。將每一層內(nèi)的代價相加，得到一層的代價；各層的代價和，構(gòu)成總代價。更適合于分治法求解算法的分析描述。第三十四頁，共六十八頁，編輯于2023年，星期三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)第三十五頁，共六十八頁，編輯于2023年，星期三4.3主方法主方法（mastermethod)主方法給出求解如下形式的遞歸式方法：

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

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

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

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

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

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

第四十八頁，共六十八頁，編輯于2023年，星期三第六章堆排序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)整子序列為堆

}}算法正確性證明：初始化：保持：終止：第四十九頁，共六十八頁，編輯于2023年，星期三第六章堆排序算法時間復(fù)雜度分析：

voidsift(elementtypeA[],intn,intk,intm)//對數(shù)組中下標(biāo)為1～n中的元素中的序號不大于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…第五十頁，共六十八頁，編輯于2023年，星期三第七章快速排序基本思想：分治法

將數(shù)據(jù)表劃分為左右兩部分，其中：左邊的所有元素都小于右邊的所有元素；然后，對左右兩部分分別進(jìn)行快速排序。劃分方法：選定一個參考點(diǎn)（中間元素），所有元素與之相比較，小的放左邊，大的放右邊。第五十一頁，共六十八頁，編輯于2023年，星期三第七章快速排序具體劃分方法：選擇第一個元素作為中間元素。劃分：(1)先保存該元素的值到其它位置，騰出其空間。(2)從后往前搜索一個比中間數(shù)小的元素，并將其放置到前面的這個空位上。(3)從前往后搜索一個比中間數(shù)大的元素，并將其放置到后面的這個位置上。重復(fù)(2)，(3)，直到兩邊搜索的空位重合時為止，此時將中間元素放在該空位中。第五十二頁，共六十八頁，編輯于2023年，星期三用快速排序算法對數(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()()第五十三頁，共六十八頁，編輯于2023年，星期三第七章快速排序voidpartition(elementtypeA[n],ints,intt,int*cutpoint)//對數(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;}第五十四頁，共六十八頁，編輯于2023年，星期三第七章快速排序//對數(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);//對前面子表快速排序

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

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

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

nn/1081n/100---cn---cn---cnLog10/9n…1log10n9n/10第五十七頁，共六十八頁，編輯于2023年，星期三第七章快速排序正確性證明：初始化：保持：終止：voidpartition(elementtypeA[n],ints,intt,int*cutpoint)//對數(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;}第五十八頁，共六十八頁，編輯于2023年，星期三第八章線性時間排序8.1排序算法時間下界前述排序算法都是比較排序：元素間的次序基于元素間的比較時間復(fù)雜度下界為O(nlgn).排序性能分析的決策樹模型以3個元素的比較為例第五十九頁，共六十八頁，編輯于2023年，星期三8.1排序算法時間下界以3個元素的比較為例內(nèi)部節(jié)點(diǎn)：對應(yīng)一個比較操作分支：對應(yīng)一次比較的一種情況葉子節(jié)點(diǎn)：對應(yīng)一個排列1：2≤>2：31：3(1,2,3)1：3(2,1,3)2：3(1,3,2)(3,1,2)(2,3,1)