算法設(shè)計實例教程 課件全套 第1-9章 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)-算法設(shè)計實例教程- 高級算法-算法設(shè)計實例教程

算法設(shè)計實例教程教學(xué)分析目錄CONCENTS123456789第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第2章基礎(chǔ)算法第3章排序算法第4章查找第5章字符串和高精度運算第6章圖論算法第7章動態(tài)規(guī)劃算法第8章計算幾何基礎(chǔ)第9章高級算法1.1.1數(shù)組本節(jié)介紹一種最基本的數(shù)據(jù)結(jié)構(gòu)——數(shù)組，稍微有一些編程基礎(chǔ)的讀者肯定對這一數(shù)據(jù)結(jié)構(gòu)不陌生。數(shù)組是一個由若干同類型變量組成的集合，在使用時只要滿足這個條件都可以看作數(shù)組的使用案例。數(shù)組（Array）是具有相同類型的數(shù)據(jù)元素的有序集合。數(shù)組中的每一數(shù)據(jù)元素通常稱為數(shù)組元素，數(shù)組元素用下標(biāo)識別，下標(biāo)的個數(shù)取決于數(shù)組的維數(shù)。數(shù)組是可以在內(nèi)存中連續(xù)存儲多個元素的結(jié)構(gòu)，在內(nèi)存中的分配也是連續(xù)的。常用數(shù)組類型為一維、二維數(shù)組1.1常見的數(shù)據(jù)結(jié)構(gòu)1.1.1數(shù)組（2）二維數(shù)組。對于二維數(shù)組，可以將其轉(zhuǎn)化為一維數(shù)組來考慮?？梢詫⒍S數(shù)組看作是元素為一維數(shù)組的一維數(shù)組。該數(shù)組以m行n列的矩陣形式表示。（1）一維數(shù)組。該數(shù)組具有n個元素，由于它的每個元素只有一個下標(biāo)，因此它是一維數(shù)組。1.數(shù)組的定義一維數(shù)組定義的一般形式為：類型符數(shù)組名[常量表達(dá)式]。1.1.1數(shù)組1inta[15]//定義了一個有15個整型元素的數(shù)組a二維數(shù)組定義的一般形式為：類型符

數(shù)組名[常量表達(dá)式][常量表達(dá)式]。具體實現(xiàn)如下：1floatb[3][5]//定義了一個浮點型的二維數(shù)組b，是一個3×5（3行5列）的數(shù)組2.數(shù)組的引用引用一維數(shù)組的表示形式為：數(shù)組名[下標(biāo)]。引用二維數(shù)組的表示形式為：數(shù)組名[下標(biāo)][下標(biāo)]。具體實現(xiàn)如下：1.1.1數(shù)組1inta[15]2k=a[10]//引用數(shù)組a中序號為10的元素，并將值賦給k1intc[3][5]

2c[2][4]=20//引用數(shù)組c中序號為2的行中序號為4的列的元素，并將該元素賦值為203.數(shù)組的初始化(1)直接賦初值在使用數(shù)組時，如果程序中涉及的數(shù)據(jù)簡單，程序員往往會直接給數(shù)組賦初值進(jìn)行初始化。直接賦初值進(jìn)行初始化一般有以下幾種類型。1.1.1數(shù)組1inta[5]={0,1,2,3,4}//對一維數(shù)組元素賦初值2intb[10]={0,1,2,3,4}//只給數(shù)組中一部分元素賦初值，其他元素為03intc[]={0,1,2,3,4}//初始化了一個有5個元素的數(shù)組c4intd[2][3]={{1,2,3},{0,1,2}}//分行給二維數(shù)組賦初值5inte[2][3]={{1},{0}}//給各行的第一列元素賦初值，其余元素自動為06intf[][3]={1,2,3,0,1,2}//初始化了一個2行3列的數(shù)組f3.數(shù)組的初始化(2)循環(huán)方法在使用數(shù)組時，如果程序中涉及的數(shù)據(jù)量大且復(fù)雜，程序員會考慮用for循環(huán)進(jìn)行初始化。具體使用方法如下：1.1.1數(shù)組1inta[5]；

2for(inti=0;i<5;i++)

3{

4a[i]=I;

5}//初始化數(shù)組a，與inta[5]={0,1,2,3,4}效果相同3.數(shù)組的初始化(3)memset函數(shù)方法在使用數(shù)組時，為了優(yōu)化代碼結(jié)構(gòu)提高效率，程序員會考慮使用memset函數(shù)進(jìn)行初始化。memset包含在頭文件string.h中，函數(shù)原型為：memset(void*s,intch,size_tn)。函數(shù)解釋：將s所指向的某一塊內(nèi)存中的后n個字節(jié)的內(nèi)容全部設(shè)置為ch指定的ASCII值，第一個參數(shù)為指定的內(nèi)存地址，第三個參數(shù)指定塊的大小，這個函數(shù)通常為新申請的內(nèi)存做初始化工作，其返回值為s。具體用法如下：1.1.1數(shù)組1inta[5];

2memset(a,0,sizeof(int)*5);//初始化數(shù)組a[5]，將所有元素都賦為04.數(shù)組的銷毀1)循環(huán)方法同初始化一樣，利用for循環(huán)來清空數(shù)組來完成數(shù)組的銷毀。具體實現(xiàn)如下：1.1.1數(shù)組1chara[]”"aaaaaaaa";//定義字符數(shù)組2for(unsignedinti=0;i<strlen(a);i++)

3{

4 a[i]='\0';//for循環(huán)清空數(shù)組5}4.數(shù)組的銷毀2)memset函數(shù)方法數(shù)組的初始化中已經(jīng)介紹了memset函數(shù)的用法。以下是利用memset函數(shù)銷毀數(shù)組的具體實現(xiàn)：1.1.1數(shù)組1chara[]="aaaaaaaa";//定義字符數(shù)組2memset(a,0,sizeofa);//清空數(shù)組鏈表是由一個或多個包含數(shù)據(jù)域（Data）和指針域（Next）的結(jié)點（Node）連接而成的表結(jié)構(gòu)。數(shù)據(jù)域內(nèi)存儲的是元素本身的數(shù)據(jù)信息，指針域內(nèi)存儲的是下一個結(jié)點存儲位置信息，單個鏈表結(jié)點如圖1-1所示。指向鏈表的第一個結(jié)點為頭結(jié)點，頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，也可以存儲表長度等附加信息。鏈表的最后一個節(jié)點為尾結(jié)點，尾結(jié)點指針域為空（NULL）。常見的鏈表類型有單鏈表、單向循環(huán)鏈表和雙向鏈表。1.1.2鏈表圖1-1單個鏈表結(jié)點結(jié)構(gòu)圖單鏈表中的每個結(jié)點的指針域只指向下一個結(jié)點，整個鏈表是無環(huán)的，如圖1-2所示1.1.2鏈表圖1-2單鏈表單向循環(huán)鏈表中，尾結(jié)點的指針域指向頭結(jié)點，鏈表中存在環(huán)，遍歷鏈表不會有NULL出現(xiàn)，如圖1-3所示。圖1-3單向循環(huán)鏈表雙向鏈表中的每個節(jié)點指針域分為前向指針（Prior）和后向指針（Next），前向指針指向該結(jié)點的前一個結(jié)點，后向指針則指向后一個結(jié)點，如圖1-4所示。圖1-4雙向鏈表1.初始化鏈表操作算法思想：在初始狀態(tài)，鏈表中沒有元素結(jié)點，只有一個頭結(jié)點，因此需要動態(tài)產(chǎn)生頭結(jié)點，并將其后向指針置為空?？梢酝ㄟ^調(diào)用C語言的動態(tài)分配庫函數(shù)malloc()，向系統(tǒng)申請結(jié)點，算法如下：1.1.2鏈表1intInit_L()

2{

3 LNode*H;

4 if(H=(LNode*)malloc(sizeof(LNode)))//頭結(jié)點5 {H->next=NULL;return1;}//設(shè)置后向指針為空6 elsereturn0;

7}1.堆棧堆棧（Stack）又稱棧，是限定僅在某一端進(jìn)行插入和刪除的特殊表結(jié)構(gòu)。允許進(jìn)行插入和刪除的一端稱為棧頂（Top），另一端則稱為棧底（Bottom）。處于棧頂位置的元素稱為棧頂元素，處于棧底位置的元素稱為棧底元素。不含任何元素的棧稱為空棧。將元素插入棧頂?shù)牟僮鹘凶鲞M(jìn)棧，將棧頂元素刪除的操作叫做出棧。圖1-5描述了堆棧的結(jié)構(gòu)，元素出棧如圖1-6所示，元素進(jìn)棧如圖1-7所示。：1.1.3堆棧和隊列圖1-5堆棧結(jié)構(gòu)圖

圖1-6出棧

圖1-7進(jìn)棧1.堆棧堆棧的基本操作除了進(jìn)棧、出棧外，還有初始化棧、判?？铡⑷ｍ斣?、判棧滿等操作。初始條件：棧S不存在。操作結(jié)果：構(gòu)造一個空棧S。（1）初始化棧：InitStack(S)初始條件：棧S已存在且非滿。操作結(jié)果：若棧S不滿，則將元素x插入S的棧頂。（2）進(jìn)棧：Push(S,X)初始條件：棧S已存在且非空。操作結(jié)果：刪除棧S中的棧頂元素，也稱為＂退棧＂、＂刪除”或出““彈。（3）出棧：Pop(S)1.1.3堆棧和隊列2.隊列隊列（Queue）又稱隊，是限定僅在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的表結(jié)構(gòu)。允許插入的一端叫隊尾（Rear），允許刪除的一端叫隊頭（Front）。在隊尾插入數(shù)據(jù)元素的操作稱為入隊，從隊頭刪除數(shù)據(jù)元素的操作稱為出隊。這和我們?nèi)粘Ｉ钪械呐抨牞F(xiàn)象是一致的，比如火車站排隊買票，銀行排隊辦理業(yè)務(wù)等，都是先來的先辦理，晚來的則排在隊尾等待。1.1.3堆棧和隊列圖1-8隊列結(jié)構(gòu)圖1.樹樹（Tree）是n（n≥0）個結(jié)點構(gòu)成的有限集合（不妨用T表示）。當(dāng)n=0時，稱該樹為空樹（Emptytree）。當(dāng)n>0時也就是為非空樹，它有一個特殊的結(jié)點，稱之為該樹的根結(jié)點（Root），其余結(jié)點被分割成m個不相交的子集,,…，，其中每一個子集，又為一棵樹，分別稱之為T的子樹（Subtree）。如圖1-9所示，（a）表示只有根結(jié)點A的樹，（b）是由8個結(jié)點組成的樹，其根結(jié)點為結(jié)點A，它有3棵子樹且分別以B、C、D為根，而以B為根的子樹又可以分為2棵子樹且分別以E、F為根，以C為根的子樹又有一棵子樹且以G為根。1.1.4樹和圖圖1-9樹的示例樹有以下基本術(shù)語：1.1.4樹和圖(1)結(jié)點的度在樹中，結(jié)點擁有子樹的個數(shù)稱為結(jié)點的度。例如，在圖1-9(b)中，結(jié)點A的度為3,結(jié)點B的度為2，結(jié)點C的度為1，結(jié)點D的度為0。(2)樹的度樹的度是樹內(nèi)各結(jié)點的度的最大值。例如，在圖1-9(b)中，樹的度為3。(3)葉結(jié)點度為0的結(jié)點為葉結(jié)點，也稱為葉子或終端結(jié)點。例如，在圖1-9(b)中，結(jié)點D、F、G、H均為葉結(jié)點。二叉樹：1.1.4樹和圖二叉樹（Binarytree）是n(n≥0)個結(jié)點的有窮集合B與B上關(guān)系的集合R構(gòu)成的結(jié)構(gòu)。當(dāng)n=0時，稱該二叉樹為空二叉樹。當(dāng)n>0時也就是為非空二叉樹，它為包含了一個根結(jié)點以及兩棵不相交的、分別稱之為左子樹與右子樹的二叉樹。二叉樹有兩種特殊的形態(tài)，分別是滿二叉樹和完全二叉樹。二叉樹的遍歷：二叉樹是一種比較有用的折中方案，它進(jìn)行添加、刪除元素操作都很快，并且在查找元素方面也有很多的算法優(yōu)化，所以，二叉樹是數(shù)組和鏈表這兩種數(shù)據(jù)結(jié)構(gòu)的優(yōu)化方案，在處理大批量的動態(tài)數(shù)據(jù)方面非常有用。二叉樹在查找元素時需要進(jìn)行遍歷，常見的遍歷方式有先序遍歷、中序遍歷和后序遍歷，下面將會詳細(xì)介紹。2.圖圖（Graph）是一種網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)，它由非空的頂點集合和描述頂點之間關(guān)系的集合組成。其形式化的定義如下：Graph=(V,E)V中的數(shù)據(jù)元素通常稱為頂點（Vertex），V是具有相同特性頂點的集合。E是兩個頂點之間關(guān)系——邊（Edge）的集合。1.1.4樹和圖圖1-11(a)中所有的邊都是沒有方向的，也就是說(vi,vj)和(vj,vi,)表示同一條邊，這樣的圖則稱為無向圖（undirectedgraph），無向圖里的邊都為無向邊。圖1-11(b)中所有的邊都是有方向的，也就是說<vi,vj>和<vj,vi>表示不同的邊，這樣的圖則稱為有向圖（directedgraph），有向圖里的邊都為有向邊，為了區(qū)別于無向邊，也稱為弧。有向邊<vi,vj>方向是從vi到vj，一般稱vi為弧尾（Tail）或初始點（initialnode），稱vj為弧頭（Head）或終端點（terminalnode）。1.1.4樹和圖圖1-11圖圖有以下基本術(shù)語：(1)鄰接點、相關(guān)邊若無向圖中的兩個頂點vi,vj之間存在一條邊(vi,vj)，則稱vi和vj互為鄰接點。同時稱邊(vi,vj)依附于頂點vi和頂點vj。邊(vi,vj)則是與頂點vi,和vj相關(guān)聯(lián)的邊。如圖1-11(a)無向圖G1中，與v5相關(guān)聯(lián)的邊是(v2,v5)，(v3,v5)，(v4,v5)。在有向圖中，若存在弧<vi,vj>，也稱相鄰接，但要區(qū)分弧的頭和尾。稱弧<vi,vj>與頂點vi和頂點vj相關(guān)聯(lián)。1.1.4樹和圖圖的遍歷：與樹的遍歷類似，圖的遍歷也是許多操作的基礎(chǔ)，例如，求連通分量、求最小生成樹和拓?fù)渑判虻榷家詧D的遍歷為基礎(chǔ)。1.1.4樹和圖從圖中指定的頂點出發(fā)，按照指定的搜索方法訪問圖的所有頂點且每個頂點僅被訪問一次，這個過程稱為圖的遍歷。圖的遍歷方法主要有兩種方法：深度優(yōu)先搜索遍歷（Depth-FirstSearch，DFS）和廣度優(yōu)先搜索遍歷（Breadth-FirstSearch，BFS）。1.1.4樹和圖(1)深度優(yōu)先搜索從圖中指定的頂點v出發(fā)，先訪問v，然后依次從v的未被訪問的鄰接點出發(fā)，直至圖中所有和v有路徑相通的頂點都被訪問到為止。具體流程如下：連通圖的深度優(yōu)先搜索遍歷方法：a)首先訪問v，然后從v的未被訪問過的鄰接點中任取一個頂點w，訪問w；b)再從w的未被訪問過的鄰接點中任取一個頂點s，訪問s；1.1.4樹和圖(1)深度優(yōu)先搜索c)依此類推，直至一個頂點的所有鄰接點均被訪問過，則依照先前的訪問次序回退到最近被訪問過的頂點，若它還有未被訪問過的鄰接點，則從這些未被訪問過的鄰接點中任取一個重復(fù)以上過程，直至圖中所有頂點均被訪問過為止。非連通圖的深度優(yōu)先搜索遍歷方法：若是連通圖，則一次遍歷便可訪問圖中的所有頂點。若是非連通圖，則一次遍歷僅能訪問開始頂點所在連通分量中的所有頂點，其他連通分量中的頂點則無法訪問到。因此，對于非連通圖，在遍歷完一個連通分量之后，還要再選擇一個開始頂點，遍歷下一個連通分量，重復(fù)這個過程，直至圖中的所有頂點均被訪問過為止。散列表是表的特殊存儲形式。這種存儲形式體現(xiàn)不出元素之間的邏輯關(guān)系，元素完全是“孤立地、松散地”存儲在散列表中。散列表中進(jìn)行插入、刪除和查找等操作效率級高，因此被廣泛地應(yīng)用在程序設(shè)計中。散列表（Hashtable），也稱哈希表，是根據(jù)關(guān)鍵碼值而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，來加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，也稱哈希函數(shù)，記為H(key)，存放記錄的數(shù)組叫做散列表。在構(gòu)造散列表時，不同的關(guān)鍵字可能映射到表中同一個位置，這種現(xiàn)象稱為沖突。散列表中映射到同一位置的數(shù)據(jù)元素稱為同義詞。選擇不同的散列函數(shù)，造成沖突的情況會不同，當(dāng)然沖突是沒法完全避免的，也因此如何構(gòu)造合適的散列函數(shù)來減少沖突是編程者的重要工作。1.1.5散列表瑞士計算機(jī)科學(xué)家N.Wirth指出“程序＝數(shù)據(jù)結(jié)構(gòu)＋算法”。它描述了計算機(jī)程序是由組織信息的數(shù)據(jù)結(jié)構(gòu)和處理信息的算法組成。二者相輔相成，不可分割。1.2.1算法及性質(zhì)算法就是求解問題的一系列步驟的集合。它以一組值作為輸入，并產(chǎn)生一組值作為輸出。通常用計算機(jī)程序來實現(xiàn)算法，計算機(jī)執(zhí)行程序中的語句，實現(xiàn)對問題的求解。1.2算法算法的性質(zhì)：所有的算法都必須滿足以下性質(zhì)?？尚行裕核惴ㄖ忻枋龅牟僮鞫际怯靡呀?jīng)實現(xiàn)的基本運算組成的。有窮性：算法必須在有限步或有限的時間內(nèi)完成。確定性：算法中每一條指令必須有確切的含義，不能有二義性。有輸入：算法應(yīng)該有零或多個輸入量。有輸出：算法應(yīng)該有一個或多個輸出量。算法的有窮性是算法和程序的分界點，程序并不要求在有限的步驟內(nèi)或有限的時間內(nèi)結(jié)束，比如操作系統(tǒng)，而算法卻有這個要求。。1.2算法算法的設(shè)計準(zhǔn)則：當(dāng)求解某類問題時，可能有多種算法供選擇。究竟哪個算法是“好”的算法，下面給出一些衡量準(zhǔn)則。1.2算法正確性：算法應(yīng)該達(dá)到預(yù)期的結(jié)果，滿足問題的需求。顯然，這是衡量算法的首要準(zhǔn)則?？勺x性：算法應(yīng)該易于理解、易于實現(xiàn)和易于調(diào)試，以免造成歧義。健壯性：算法不但能夠處理合法數(shù)據(jù)，而且對輸入的非法數(shù)據(jù)也能夠做出反應(yīng)，不致產(chǎn)生不可預(yù)料的后果。高效性：算法執(zhí)行的時間要短（時間效率），占用的存儲空間要少（空間效率）。一個算法的性能優(yōu)劣往往通過算法復(fù)雜度來衡量。算法的復(fù)雜性體現(xiàn)在運行該算法時計算機(jī)所需資源的多少上。在計算機(jī)中最重要的資源是時間資源和空間資源。因此，算法復(fù)雜度包括時間復(fù)雜度和空間復(fù)雜度兩個方面。時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量，計算工作量通常指算法執(zhí)行所需要耗費的時間，時間越短，算法效率越高。而空間復(fù)雜度是指執(zhí)行這個算法所需要的存儲空間。1.2.2算法性能評價1.3本章小結(jié)算法設(shè)計實例教程教學(xué)分析目錄CONCENTS123456789第2章基礎(chǔ)算法第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第3章排序算法第4章查找第5章字符串和高精度運算第6章圖論算法第7章動態(tài)規(guī)劃算法第8章計算幾何基礎(chǔ)第9章高級算法2.1分治法2.1.1分治法的基本概念分治法，從字面意思理解就是分而治之，其本質(zhì)就是將一個原本規(guī)模較大的問題分解為若干規(guī)模較小且更容易求解的子問題，分別求解每個子問題，對求解出的結(jié)果進(jìn)行合并得到原問題的最終解答。第2章基礎(chǔ)算法2.1分治法2.1.1分治法的基本概念使用分治法設(shè)計算法，通常包括以下三個步驟：第2章基礎(chǔ)算法（1）分解：將要求解的問題劃分成若干規(guī)模較小的同類子問題，且每個子問題是相互獨立的；（2）求解：當(dāng)子問題的規(guī)模足夠小，能夠使用較簡單的方法解決時，對子問題進(jìn)行求解；（3）合并：合并子問題的解，構(gòu)成最終的答案時間限制：1000ms內(nèi)存限制：32MB問題描述設(shè)有n＝2k個運動員要進(jìn)行網(wǎng)球循環(huán)賽?，F(xiàn)要設(shè)計一個滿足以下要求的比賽日程表：(1)每個選手必須與其他n-1個選手各賽一次；(2)每個選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。輸入說明一個正整數(shù)n，表示參加比賽的運動員的數(shù)量，其中n=2K(k>0)。2.1.2分治法應(yīng)用舉例1：循環(huán)賽日程表輸出說明一個n×n的二維矩陣，其中第0列依次是每一位運動員的編號（運動員的編號從1開始），剩下的n-1列是循環(huán)賽的編排表，其中第i行第j（j>0）列的數(shù)值表示編號為i+1的運動員在第j天遇到的運動員的編號。輸入樣例8輸出樣例1234567821436587341278564321876556781234658721437856341287654321輸出說明輸入樣例輸出樣例算法分析下面我們從最簡單的情況（即，假設(shè)只有2名運動員）開始，分析循環(huán)賽日程表問題的結(jié)構(gòu)特征。當(dāng)只有兩位運動員時（即n=2），分別是：運動員1號和運動員2號，顯然他們之間只需要安排一場比賽就可以了，而這場比賽也只需要安排在第一天就可以結(jié)束，因此比賽日程安排可以用如下的一個2×2的二維矩陣A表示：2.1.2分治法應(yīng)用舉例1：循環(huán)賽日程表圖中所示，矩陣第0列的兩個元素A[0][0]和A[1][0]分別表示運動員的編號1號和2號，而第1列的元素值則表示第1天所有的對陣安排。其中，A[0][1]的值為2，表示1號選手在第1天遇到的是2號運動員，A[1][1]的值為1，表示2號選手在第1天遇到的是1號運動員。從這個分析，我們也可以得出一個顯然的結(jié)論，即這個日常安排表是一個對稱矩陣。當(dāng)n=4時，將有4位運動員參與循環(huán)賽。這4位運動員可以兩兩分為一組，比如1號與2號為一組，3號與4號為一組，每一組可以在同一天各自進(jìn)行循環(huán)賽。比如在比賽的第1天，在第一組是1號與2號，第二組是3號與4號比賽，因此數(shù)組的第1列的值分別為[2,1,4,3]。第二天和第三天兩組交叉運動員，數(shù)組的第2列的值分別為[2,1,4,3]第二天第一組的1號運動員分別對陣3號和4號，第二組的3號運動員分別對陣1號和2號。得到的日程安排表如下所示：圖2-12名運動員的對陣矩陣圖2-24名運動員的對陣矩陣通過觀察由4名運動員組成的比賽日程安排表，我們可以發(fā)現(xiàn)它可以分解為2個兩人組比賽日常表的組合，將矩陣右上角2×2子矩陣的值直接復(fù)制到左下角，同樣，矩陣左上角的2×2子矩陣也被復(fù)制到了右下角。由于這個4×4的矩陣具有的對稱性，我們只需要關(guān)注位于左上和右上的兩個2×2子矩陣的值的特點。左上的2×2子矩陣元素包括A[0][0]、A[0][1]、A[1][0]、A[1][1]，它代表的是1號運動員與2號運動員的賽程安排，填入的值分別為1、2、2、1。右上的2×2子矩陣元素包括A[0][2]、A[0][3]、A[1][2]、A[1][3]它代表的是3號運動員與4號運動員的賽程安排，填入的值分別為3、4、4、3。但是我們可以換個視角再來看這組值的特點，即A[0][0+2]、A[0+0][1+2]、A[1+0][0+2]、A[1+0][1+2]，它們的值分別是1+2、2+2、2+2、1+2。發(fā)現(xiàn)規(guī)律了嗎？右上子矩陣的值=左上的子矩陣+2。而這個2正是右上子矩陣相對于左上子矩陣在坐標(biāo)上的偏移量。由此，我們可以按照這樣的規(guī)律分別填寫每一個2×2子矩陣的值。2.1.2分治法應(yīng)用舉例1：循環(huán)賽日程表我們可以將該規(guī)律推廣到n=2k的情況。按照分治的策略，將所有運動員平均分為兩組，n個運動員的比賽日程表就可以通過兩個n/2個運動員的比賽日程表來決定。如果分解后的小組成員的數(shù)量依然大于2，則可以使用分治法繼續(xù)對運動員進(jìn)行分割，直到每一組都只包含兩個運動員，就可以直接得到一個2×2的比賽日程表。這是一個典型的可以用分治法來解決的問題。將一個原本規(guī)模為n的問題逐層分解，而且每個子問題的結(jié)構(gòu)都與原問題形式相同且相互獨立，直到子問題的解可以輕而易舉地獲得，就可以通過遞歸地解決這些子問題，然后合并各個子問題地解得到原問題的解。2.1.2分治法應(yīng)用舉例1：循環(huán)賽日程表時間限制：1000ms內(nèi)存限制：65536KB問題描述求兩個不超過200位的非負(fù)整數(shù)的積。輸入說明有兩行，每行是一個不超過200位的非負(fù)整數(shù)，沒有多余的前導(dǎo)0。輸出說明一行，即相乘后的結(jié)果。結(jié)果里不能有多余的前導(dǎo)0，即如果結(jié)果是342，那么就不能輸出為0342。輸入樣例1234567890098765432100輸出樣例12193263111263526900002.1.3分治法應(yīng)用

舉例2：大整數(shù)乘法算法分析由于編程語言提供的基本數(shù)值數(shù)據(jù)類型表示的數(shù)值范圍有限，當(dāng)兩個大數(shù)進(jìn)行相乘運算時，很可能會超過計算機(jī)數(shù)值的表示范圍，從而導(dǎo)致計算溢出錯誤。比如，一個longint類型數(shù)值由4個字節(jié)組成，其可以表示范圍是（-231~231-1，即-2147483648~2147483647）。當(dāng)兩個longint整型相乘，其結(jié)果最大會到達(dá)2的62次方，遠(yuǎn)遠(yuǎn)超過了longint類型能夠表示的范圍。因此，用直接的相乘運算不能滿足較大規(guī)模的高精度數(shù)值計算，需要利用其他方法間接完成計算，于是產(chǎn)生了大數(shù)運算。對兩個整數(shù)相乘，最直觀的方法就是列豎式。在程序中，我們可以定義兩個int類型的數(shù)組A和B，把兩個大整數(shù)按位進(jìn)行存儲，再把數(shù)組中的元素按照豎式的要求進(jìn)行逐位相乘得到中間結(jié)果，然后將所有的中間結(jié)果相加得到最終結(jié)果。但是這種方法的性能如何呢？我們可以計算一下它的算法復(fù)雜度。由于兩個大整數(shù)的所有數(shù)位都需要一一彼此相乘，假設(shè)整數(shù)A有m位，整數(shù)B有n位，則總共需要進(jìn)行m*n次相乘操作，即算法復(fù)雜度為O(m*n)。如果兩個大整數(shù)的位數(shù)相近，那么算法復(fù)雜度就是O(n2)。我們可以利用分治法設(shè)計找到比O(n2)復(fù)雜度更低的算法。假設(shè)需要相乘的兩個整數(shù)為：123456*54321首先將大整數(shù)按照數(shù)位平均分成高數(shù)位和低數(shù)位兩部分，如下圖所示：2.1.3分治法應(yīng)用舉例2：大整數(shù)乘法第一步，分解：將2個大整數(shù)A(n位）、B(m位)按照各自的位數(shù)分解為兩部分：AH和AL、BH和BL，其中AH表示大整數(shù)A的高位，AL表示大整數(shù)A的低位，它們的位數(shù)是n/2位；同樣的，BH表示大整數(shù)B的高位，BL表示大整數(shù)B的低位，它們的位數(shù)是m/2位。這兩個位數(shù)分別為n位和m位的大整數(shù)經(jīng)過拆分后的乘積運算就轉(zhuǎn)換成了四個乘積運算AH*BH、AH*BL、AL*BH、AL*BL，而每個乘數(shù)的位數(shù)變?yōu)榱嗽瓉淼囊话?。第二步，求解子問題：繼續(xù)對每個乘法運算進(jìn)行分解，直到分解后的乘數(shù)位數(shù)能夠直接運算時停止分解，進(jìn)行乘法運算并記錄結(jié)果。第三步，合并：將計算出的結(jié)果相加并回溯，求出最終結(jié)果。圖2-3大整數(shù)的分解示意圖2.2.1遞歸法的基本概念遞歸是計算機(jī)科學(xué)中一個非?；A(chǔ)和關(guān)鍵的概念，也是我們在設(shè)計算法時常用的基本技能。如果一個函數(shù)可以在其函數(shù)內(nèi)部調(diào)用本身，這種調(diào)用方式被稱為遞歸（recursive）。遞歸算法就是通過定義和使用遞歸函數(shù)來求解問題的計算方法。使用遞歸有時可以用簡單易理解的方式有效地解決一些復(fù)雜的問題問題，簡化代碼的編寫，提高程序的可讀性，但如果遞歸使用不當(dāng)反而會適得其反。為了使用遞歸算法，首先要設(shè)計遞歸函數(shù)。遞歸函數(shù)每次調(diào)用自身時必須要縮小計算問題的范圍，從而使得輸入變得更加精細(xì)，逐步接近問題的答案。2.2遞歸法下面通過一個例子來說明遞歸的思想。假設(shè)我們想要計算整數(shù)n的階乘n!，即計算1~n之間所有整數(shù)的乘積。比如1！=1，2!=2×1，3!=3×2×1，...，n!=n×(n-1)×(n-2)…×1。2.2遞歸法一種直觀的計算方法就是使用循環(huán)，如以下代碼所示：intF(intn){ints=1,i;if(n<=0)return0;for(i=1;i<=n;i++)s=s*i;returns;對于該問題我們也可以使用遞歸的方式加以描述，如下所示：使用遞歸方式定義的求階乘函數(shù)，如以下代碼所示：intF(intn){if(n==1)return1;returnn*F(n-1);}如上所示，要計算F(n)，要先計算F(n-1)，依次類推，這意味著每一次遞歸都通過嵌套調(diào)用函數(shù)自身來完成計算，而每次傳遞給被調(diào)用函數(shù)的參數(shù)會更接近終止條件。比如，在求解階乘的函數(shù)中，當(dāng)n==1時，該條件路徑中不再包含遞歸調(diào)用，此時就可以立刻得到本次函數(shù)調(diào)用的計算結(jié)果，我們將n==1作為遞歸調(diào)用的終止條件。F(1)完成計算后，會將計算結(jié)果通過return語句返回給調(diào)用它的F(2)，以此類推，通過函數(shù)調(diào)用的逐級返回，直到調(diào)用的起點就可以得到最終的答案，遞歸過程結(jié)束。。2.2遞歸法使用遞歸方式定義的求階乘函數(shù)，如以下代碼所示：intF(intn){if(n==1)return1;returnn*F(n-1);}F(5)的計算結(jié)果依賴于5*F(4)，而F(4)的結(jié)果依賴于4*F(3)，以此類推，直到F(1)，而根據(jù)函數(shù)定義，當(dāng)n==1時，函數(shù)直接返回1，因此F(1)是本輪遞歸調(diào)用的終點。然后函數(shù)依次帶著結(jié)果返回上一級調(diào)用，返回過程如下圖所示：2.2遞歸法下面以F(5)的計算過程為例，其函數(shù)遞歸調(diào)用的過程可以用如下的一條鏈表示：圖2-4F(5)的遞歸過程圖2-5F(5)的遞歸返回過程從上面調(diào)用和返回的過程可以看出，遞歸調(diào)用是一個先進(jìn)后出的過程，最先被調(diào)用的F(5)最后返回，而最后被調(diào)用的F(1)則最先返回。每一次函數(shù)調(diào)用的過程信息都會被系統(tǒng)自動保存在一個叫做棧的內(nèi)存空間中，只有函數(shù)返回時，當(dāng)前函數(shù)所占用的?？臻g才會被釋放。顯然，隨著輸入?yún)?shù)n的增大，需要消耗的棧空間也會越來越大。在現(xiàn)代計算機(jī)系統(tǒng)中，每個程序所能夠使用的?？臻g是一種有限的內(nèi)存資源，當(dāng)棧空間消耗殆盡時，就會發(fā)生程序異常退出等嚴(yán)重錯誤。2.2遞歸法因此，在使用遞歸策略設(shè)計遞歸算法時應(yīng)注意以下幾點：（2）遞歸雖然為編程提供了簡單的解決方案，但是由于每一次遞歸調(diào)用時都需要將函數(shù)的返回值、局部變量等信息保存在棧中，當(dāng)遞歸嵌套的次數(shù)太多時，有可能因為消耗太多的內(nèi)存而造成棧溢出錯誤。下面通過具體的實例來分析遞歸的應(yīng)用。（1）遞歸函數(shù)每嵌套調(diào)用一次，都應(yīng)縮小求解問題的規(guī)模，直到子問題的規(guī)模小到能夠直接給出解答而不再進(jìn)行遞歸調(diào)用，稱之為遞歸結(jié)束條件；時間限制：1000ms內(nèi)存限制：32MB問題描述編寫一個求斐波那契數(shù)列的遞歸函數(shù)，輸入n值，使用該遞歸函數(shù)，輸出如樣例輸出的斐波那契數(shù)列。輸入說明一個整型數(shù)n輸出說明題目可能有多組不同的測試數(shù)據(jù)，對于每組輸入數(shù)據(jù)，按題目的要求輸出相應(yīng)的斐波那契圖形。輸入樣例6輸出樣例0011011230112358011235813210112358132134552.2.2遞歸應(yīng)用舉例1：斐波那契數(shù)列算法分析斐波那契數(shù)列的定義如下：數(shù)列中第1個是0，第2個數(shù)是1，后續(xù)的每個數(shù)字都是其前兩個數(shù)字之和。例如，當(dāng)數(shù)列長度為6時，該數(shù)列的前6個數(shù)依次是：0、1、1、2、3、5。對于該問題，我們可以使用循環(huán)方式來實現(xiàn)，函數(shù)定義如下：longlongintfib_loop(intn){inti,tmp,num1=0,num2=1;//初始情況下，num1記錄第1項的值為0，num2記錄第2項的值為1if(n==0||n==1)returnn;//當(dāng)n為0或1時，函數(shù)直接返回結(jié)果else//否則循環(huán)計算前n-1項和n-2項for(i=0;i<n-1;i++){tmp=num1+num2;num1=num2;num2=tmp;}returntmp;}由于當(dāng)輸入?yún)?shù)為n時，函數(shù)內(nèi)部的循環(huán)體執(zhí)行了n次，所以循環(huán)算法的時間復(fù)雜度是O(n)?！，F(xiàn)在我們使用遞歸的方式來解決該問題。從代碼的表達(dá)形式上看，遞歸更能夠直接體現(xiàn)計算的本質(zhì)要求，從而簡化程序的設(shè)計?，F(xiàn)在我們要創(chuàng)建一個遞歸函數(shù)，當(dāng)輸入為n時，返回相應(yīng)的斐波那契數(shù)列的第n項數(shù)值。函數(shù)定義如下：longlongintfib_rec(intn){if(n==0||n==1)returnn;elsereturnfib_rec(n-1)+fib_rec(n-2);}從函數(shù)的定義可以看出，如果要計算數(shù)列的第n項，當(dāng)n為0或1時，函數(shù)能夠直接返回結(jié)果，而當(dāng)n≥2時，則只需要遞歸的調(diào)用函數(shù)自身，分別計算第n-1項和第n-2項。下面以fib_rec(5)的計算過程為例，其函數(shù)遞歸調(diào)用的過程可以用下圖表示：2.2.2遞歸應(yīng)用舉例1：斐波那契數(shù)列2.2.2遞歸應(yīng)用舉例1：斐波那契數(shù)列圖2-6F(5)的遞歸調(diào)用樹如圖所示，F(xiàn)(5)的計算結(jié)果依賴于F(3)和F(4)，而F(3)依賴于F(2)和F(1)，以此類推，得到一棵遞歸樹。其中，只有F(0)和F(1)是葉子節(jié)點，其他節(jié)點F(n)都是具有兩個子節(jié)點F(n-1)和F(n-2)的父節(jié)點。當(dāng)函數(shù)調(diào)用到達(dá)子節(jié)點后，遞歸調(diào)用結(jié)束，開始向父節(jié)點返回計算結(jié)果。在解決了生成斐波那契數(shù)列的第任意n項數(shù)的計算問題后，我們回到原問題的需求。該問題要求根據(jù)輸入數(shù)據(jù)n，輸出n行斐波那契數(shù)列，第1行數(shù)列長度為1，第2行長度為3，每一行都比前一行多兩個數(shù)，依次類推，第n行的長度為2*n-1。因此可以利用雙重循環(huán)依次輸出。時間限制：1000ms內(nèi)存限制：32MB問題描述某商場正在舉辦飲料促銷活動。每購買一瓶飲料可收集一個瓶蓋，憑3個瓶蓋可以再換一瓶該飲料，并且可以一直循環(huán)下去，但不允許賒賬。如果小明一開始購買了n瓶飲料，在不浪費任何一個瓶蓋的情況下，盡可能地?fù)Q購，那么最后小明一共最多能得到多少瓶飲料。輸入說明一個整數(shù)n，表示最初購買的飲料數(shù)量（0<n<10000）輸出說明題目可能有多組不同的測試數(shù)據(jù)，對于每組輸入數(shù)據(jù)，輸出實際得到的飲料數(shù)。輸入樣例200300輸出樣例299449：2.2.4遞歸應(yīng)用舉例2：飲料換購2.2.4遞歸應(yīng)用舉例2：飲料換購算法分析假設(shè)小明當(dāng)前有n瓶飲料，則意味著有n個飲料瓶蓋子，若n＜3，則收集的瓶蓋數(shù)不足以進(jìn)行1次換購，因此通過換購得到的飲料數(shù)為0。若n≥3，則收集的瓶蓋數(shù)足夠參與換購，且每3個瓶蓋可以換一瓶，因此換購得到的飲料數(shù)為n/3，還余下n%3不足以參加換購，因此這一輪換購后得到的飲料瓶數(shù)為（n/3+n%3），而這正是參與下一輪的換購的飲料瓶蓋的數(shù)量。以此類推，每一輪能夠參與換購的瓶蓋數(shù)都取決于上一輪換購剩下的飲料瓶數(shù)量，而且換購的規(guī)則是一樣的，因此這是一個明顯的遞歸過程。由于每次換購都會使得剩下的飲料瓶數(shù)越來越少，因此遞歸的終止條件也很明顯，就是當(dāng)n小于3時，就不能再換購了，遞歸結(jié)束。由此，我們可以構(gòu)建一個遞歸表達(dá)式，用來計算當(dāng)飲料瓶數(shù)為n時，能夠換購得到的飲料瓶數(shù)量，如下：drink(n)用來計算當(dāng)飲料數(shù)為n時，能夠通過換購得到的新增飲料的數(shù)量。顯然，當(dāng)n小于3時，是無法換購得到任何飲料的。而當(dāng)n大于等于3時，首先可以用n個瓶蓋換得得n/3瓶飲料，然后用(n/3+n%3)個瓶蓋繼續(xù)參加下一輪的換購。時間限制：1000ms內(nèi)存限制：32MB問題描述編寫程序，輸出前n個正整數(shù)的全排列（n<10）。輸入說明一個整數(shù)n（0<n<10）輸出說明輸出1到N的全排列。每種排列占一行，數(shù)字間無空格。排列的輸出順序為字典序。輸入樣例3輸出樣例1231322132313123212.2.4遞歸應(yīng)用舉例3：輸出全排列算法分析對n個有序排列的數(shù)進(jìn)行全排列輸出，可以使用遞歸的方式來解決。算法的核心是遞歸地交換元素在數(shù)列中的位置，即將每個元素放到余下n-1個元素組成的隊列最前方，然后對剩余元素進(jìn)行全排列，依次遞歸下去。比如包含3個有序數(shù)的基準(zhǔn)排列為：123首先將1放到數(shù)列開頭的位置（跟第1個元素交換），然后對原隊列中剩余的子隊列23使用遞歸的方式進(jìn)行全排列。得到結(jié)果：123;132其次將2放到最前方（跟第1個元素交換），然后排列余下的13，然后將2放回原處得到結(jié)果：213；231以此類推，直到原隊列中所有的數(shù)都作為輸出隊列的排頭進(jìn)行了全排列處理。2.3.1枚舉法的基本概念枚舉法，也稱為窮舉法或暴力求解法，是依賴于計算機(jī)的強(qiáng)大計算能力來窮盡每一種可能的情況，從而達(dá)到求解問題的目的。這種策略的效率并不高，但適用于一些沒有明顯規(guī)律可循，或者難以將問題分解為子問題的場合。枚舉法的本質(zhì)就是從所有候選答案中搜索正確的解，因為在解決某些問題時，可能沒有辦法按一定的規(guī)律從眾多的候選答案中找出正確的解，只能對所有的候選答案逐個進(jìn)行判斷，如果滿足要求，則找到了正確答案，否則繼續(xù)對下一個候選答案進(jìn)行判斷。由此我們可以知道，在使用窮舉算法時，如果候選答案的集合很大，那么明確候選答案的搜索范圍和搜索策略可以在一定程度上提高算法的策略，要盡可能避免做大量無效的搜索。2.3枚舉法時間限制：1000ms內(nèi)存限制：32MB問題描述用小于等于n元去買100只雞，大雞5元/只，小雞3元/只,還有1/3元每只的一種小雞，分別記為x只,y只,z只。編程求解x,y,z所有可能解。輸入說明測試數(shù)據(jù)有多組，輸入n。輸出說明對于每組輸入,請輸出x,y,z所有可行解，按照x，y，z依次增大的順序輸出。輸入樣例40輸出樣例x=0,y=0,z=100x=0,y=1,z=99x=0,y=2,z=98x=1,y=0,z=99。2.3.2枚舉法應(yīng)用舉例1：百雞百錢算法分析按照窮舉法的策略，我們首先抽象出數(shù)學(xué)模型，建立方程組，設(shè)公雞為x，母雞為y,小雞為z，則三個變量滿足以下等式：雞：x+y+z=100錢：5x+3y+1/3z=100按照這個數(shù)學(xué)模型，我們可以建立一個三層的嵌套循環(huán)，依次判斷每一種可能的組合是否滿足等式的要求，代碼如下：#include<stdio.h>#include<stdlib.h>intmain(){intn;floatx,y,z;while(scanf("%d",&n)!=EOF){for(x=0;x*5<=n;x++)for(y=0;y*3<=n;y++)for(z=100;z>=0;z--)if(x*5+y*3+z/3<=n&&x+y+z==100)printf("x=%g,y=%g,z=%g\n",x,y,z);}return0;}時間限制：1000ms內(nèi)存限制：65536KB問題描述雞兔同籠,共有頭k個,腳n只,求雞和兔各有多少只?輸入說明輸入兩個整數(shù)，其中k代表頭的個數(shù)，n代表腳的個數(shù)。輸出說明輸出雞的數(shù)量和兔的數(shù)量。輸入樣例1740輸出樣例雞有12只，兔有5只2.3.3枚舉法應(yīng)用舉例2：雞兔同籠問題算法分析針對這個問題，我們可以根據(jù)我們的常識（每只雞和兔子都有一個頭，雞有兩只腳，兔子有四只腳）建立一個方程組，設(shè)有x只雞，y只兔子，那么就可以利用x和y的關(guān)系建立如下等式：由于雞或者兔子的數(shù)量都不會超過k個，假設(shè)雞是x個，那兔子就是（k-x）個。我們可以把x的值依次用0~k之間的整數(shù)值逐個代入到第二個等式中加以檢驗，符合等式成立條件的就是我們需要的答案，因此這道題可以使用枚舉法實現(xiàn)。時間限制：1000ms內(nèi)存限制：65535KB問題描述春天是鮮花的季節(jié)，水仙花就是其中最迷人的代表，數(shù)學(xué)上有個水仙花數(shù)，他是這樣定義的：“水仙花數(shù)”是指一個三位數(shù)，它的各位數(shù)字的立方和等于其本身，比如：153=1^3+5^3+3^3?，F(xiàn)在要求輸出所有在m和n范圍內(nèi)的水仙花數(shù)。輸入說明輸入數(shù)據(jù)有多組，每組占一行，包括兩個整數(shù)m和n（100<=m<=n<=999）。輸出說明對于每個測試實例，要求輸出所有在給定范圍內(nèi)的水仙花數(shù)，就是說，輸出的水仙花數(shù)必須大于等于m,并且小于等于n，如果有多個，則要求從小到大排列在一行內(nèi)輸出，之間用一個空格隔開;如果給定的范圍內(nèi)不存在水仙花數(shù)，則輸出no;每個測試實例的輸出占一行。輸入樣例100120300380輸出樣例no3703712.3.3枚舉法應(yīng)用舉例3：水仙花數(shù)2.3.3枚舉法應(yīng)用舉例3：水仙花數(shù)算法分析判斷一個數(shù)是否為水仙花數(shù)，只需要將該數(shù)的每一位依次取出，計算各位數(shù)字的立方和等于其本身。因此這道題只需要對給定范圍內(nèi)的每一個數(shù)據(jù)依次測試就可以了，如果符合要求就輸出該數(shù)。如果指定范圍內(nèi)一個水仙花數(shù)都沒有，就輸出no。代碼如下：#include<stdio.h>#include<stdlib.h>intmain(){intstart,end,i,a,b,c,flag=0;while(scanf("%d%d",&start,&end)!=EOF){flag=0;//設(shè)置一個標(biāo)志變量，值為0則表示目前還未找到水仙花數(shù)，否則值為1for(i=start;i<=end;i++){a=i/100;b=(i-a*100)/10;c=i%10;if(i==a*a*a+b*b*b+c*c*c){printf("%d",i);flag=1;}}flag?printf("\n"):printf("no\n");}return0;}時間限制：1000ms內(nèi)存限制：65535KB問題描述孿生素數(shù)（也稱為孿生質(zhì)數(shù)、雙生質(zhì)數(shù)）是指一對素數(shù)，它們之間相差2，它們之間的距離已經(jīng)近得不能再近了，就像孿生兄弟一樣。例如3和5，5和7，11和13，10016957和10016959等等都是孿生素數(shù)。試求出給定區(qū)間的所有孿生素數(shù)對。（按照第一個數(shù)的大小排序輸出）。輸入說明多組數(shù)據(jù)，每行數(shù)據(jù)兩個數(shù)a，b，代表a、b之間的區(qū)間(1<=a<=b<=1000000)輸出說明輸出區(qū)間內(nèi)所有的孿生素數(shù)對。輸入樣例120輸出樣例3557111317192.3.3枚舉法應(yīng)用舉例4：孿生素數(shù)2.3.3枚舉法應(yīng)用舉例4：孿生素數(shù)算法分析在指定的數(shù)據(jù)范圍中尋找孿生素數(shù)，可以使用枚舉法，逐一對范圍內(nèi)的數(shù)據(jù)做如下判斷：（1）這個數(shù)是否為素數(shù)，（2）這個數(shù)加2是不是素數(shù)？如果兩個條件都滿足，就說明它們是孿生素數(shù)。那么如何判斷一個數(shù)n是否為素數(shù)呢？方法一：正向判斷，凡是能被某個數(shù)整除的數(shù)都不是素數(shù)，因此用整數(shù)區(qū)間[2,n-1]中的數(shù)逐一去整除n，如果都不能整除，則n是素數(shù)。方法二：反向篩選，如果有某個數(shù)i，那么凡是值為i*j的數(shù)都不是素數(shù)，將所有這些不是素數(shù)的數(shù)標(biāo)記出來，剩下的數(shù)都是素數(shù)。這種素數(shù)測試方法就是著名埃拉托色尼篩選法。它是由大約公元前240年的希臘數(shù)學(xué)家埃拉托色尼設(shè)計的。（埃拉托色尼是亞歷山大城的圖書館館長，他是第一個計算出地球直徑的人。）時間限制: 1000ms內(nèi)存限制: 65535KB問題描述輸入兩個正整數(shù)，求其最大公約數(shù)。輸入說明測試數(shù)據(jù)有多組，每組輸入兩個正整數(shù)。輸出說明對于每組輸入,請輸出其最大公約數(shù)。輸入樣例4914輸出樣例72.3.4枚舉法應(yīng)用舉例5：最大公約數(shù)2.3.4枚舉法應(yīng)用舉例5：最大公約數(shù)算法分析能夠整除一個整數(shù)的整數(shù)稱為其的約數(shù)。比如12的約數(shù)有1、2、3、4、6和12。如果一個數(shù)既是數(shù)A的約數(shù)，又是數(shù)B的約數(shù)，稱為A，B的公約數(shù)。其中公約數(shù)中值最大的哪個整數(shù)被稱為最大公約數(shù)。方法一：枚舉法根據(jù)最大公約數(shù)的定義，可以使用枚舉法依次找到能夠同時整除兩個整數(shù)的整數(shù)，并找出其中的最大值。這個算法雖然能夠解決問題，但是效率較低，其最差情況下，算法復(fù)雜度為O(min(a,b))。方法二：歐幾里得算法（遞歸法）計算兩個整數(shù)最大公約數(shù)有一個著名的算法叫輾轉(zhuǎn)相除法。該算法是已知最古老的算法，最早被記錄在公元前300年前古希臘數(shù)學(xué)家歐幾里得的著作《幾何原本》中,所以被命名為歐幾里得算法。歐幾里得算法的計算原理基于以下定義：定理：兩個整數(shù)的最大公約數(shù)等于其中較小的那個數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)。最大公約數(shù)（GreatestCommonDivisor）縮寫為GCD。gcd(a,b)=gcd(b,amodb)(不妨設(shè)a>b且r=amodb,r不為0)比如49和14，49除以14商3余7,那么49和14的最大公約數(shù)，等同于14和7的最大公約數(shù)。這樣，我們成功的把兩個較大整數(shù)之間的運算簡化成兩個較小整數(shù)之間的運算。以此類推，通過逐步遞歸的方式，直到兩個數(shù)之間可以直接整除，就可以得到最終的結(jié)果。遞歸方式的算法復(fù)雜度不太好算，可以近似為O(log(max(a,b)))。2.4.1貪心法的基本概念貪婪算法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪心法在求解問題時，一般都包含一系列步驟，每一步都有一組選擇，每次都選擇當(dāng)前最優(yōu)的選項。即，從問題的初始解開始，根據(jù)當(dāng)前已有的信息做出選擇，通過選擇局部最優(yōu)解的方式逐步逼近問題的目標(biāo)。雖然貪心法獲得的解答未必是最優(yōu)解，看似“目光短淺”，但是相比較通過窮舉所有可能而去找最優(yōu)解的方式，貪心法的效率更高。在一些情況下，貪心法能夠獲得最優(yōu)解的近似解。2.4貪心法采用貪心法求最優(yōu)化問題的算法，希望通過局部最優(yōu)的選擇達(dá)到全局最優(yōu)的選擇。我們在遇到具體問題時，往往分不清對哪些問題可以用貪心算法，對哪些問題不可以用貪心算法。實際上，如果問題具有兩個特性：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，則可以用貪心算法。2.4貪心法（1）貪心選擇性質(zhì)。貪心選擇性質(zhì)指原問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇得到。應(yīng)用同一規(guī)則，將原問題變?yōu)橐粋€相似的、但規(guī)模更小的子問題，而后的每一步都是當(dāng)前最優(yōu)的選擇。這種選擇依賴于已做出的選擇，但不考慮對后續(xù)步驟的影響。因此運用貪心算法解決的問題在程序的運行過程中不需要回溯。當(dāng)達(dá)到算法中的某一步不能再繼續(xù)前進(jìn)時，就停止算法，給出近似解。（2）最優(yōu)子結(jié)構(gòu)性質(zhì)。當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題是否可以用貪心算法求解的關(guān)鍵。時間限制：1000ms內(nèi)存限制：32MB問題描述在超市購物，收銀員找零錢時，有10元、5元、2元和1元四種不同的紙幣可以選擇，收銀員需要找到一種紙幣數(shù)最少的找零錢方案。輸入說明測試數(shù)據(jù)有多組，輸入n。輸出說明對于每組輸入,請輸出最優(yōu)的零錢方案。輸入樣例43輸出樣例10:45:02:11:12.4.2貪心法應(yīng)用舉例1：找零錢2.4.2貪心法應(yīng)用舉例1：找零錢算法分析該問題的最優(yōu)子結(jié)構(gòu)是每次都選擇當(dāng)前小于零錢余額的最大面值的紙幣，代碼如下：intmain(){inti,money;intvalue[4]={1,2,5,10};intnum[4]={0};//記錄每種紙幣的數(shù)量while(scanf("%d",&money)!=EOF){for(i=3;i>=0;i--){num[i]=money/value[i];money=money-num[i]*value[i];}for(i=3;i>=0;i--)printf("%d:%d\n",value[i],num[i]);}return0;時間限制：1000ms內(nèi)存限制：32MB問題描述輸入一個以字符串表示的非負(fù)整數(shù)n和一個整數(shù)k，移除這個數(shù)中的k位數(shù)字后，剩下的數(shù)字按原次序排列組成一個新的數(shù)。程序計算的結(jié)果是得到一個最小的數(shù)。提示：1≤k≤n.length≤105，除了0本身之外，n不含任何前導(dǎo)零。輸入說明第一行輸入一個整數(shù)n；第二行輸入一個整數(shù)k輸出說明輸出一個整數(shù)。輸入樣例14322193輸出樣例12192.4.3貪心法應(yīng)用舉例2：刪除K位數(shù)字算法分析現(xiàn)在以輸入1432219為例，假設(shè)k=1，即只刪除其中的一個數(shù)字，使得剩下的數(shù)按原順序組合后得到的數(shù)值最小，則結(jié)果應(yīng)為132219，即刪除4。假設(shè)k=2，刪除其中的兩個數(shù)字，則結(jié)果應(yīng)為12219，依次類推，我們發(fā)現(xiàn)最優(yōu)解就是從高位依次遍歷每一個數(shù)位，只要發(fā)現(xiàn)第一個數(shù)，它大于位于其右邊相鄰的數(shù)，就可以刪除這個數(shù)，因為刪除之后高位減小。每一次選擇刪除一個數(shù)的時候，是在前一次刪除操作的基礎(chǔ)上進(jìn)行的，因為留下的數(shù)總是當(dāng)前最優(yōu)解，而且每一次選擇都是找到第一個左邊大于右邊的數(shù)，這符合貪心法中的最優(yōu)子結(jié)構(gòu)特征。在這個題中，局部的最優(yōu)解能夠得到最終的全局最優(yōu)解。2.5本章小結(jié)算法設(shè)計實例教程教學(xué)分析目錄CONCENTS123456789第3章排序算法第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第2章基礎(chǔ)算法第4章查找第5章字符串和高精度運算第6章圖論算法第7章動態(tài)規(guī)劃算法第8章計算幾何基礎(chǔ)第9章高級算法排序算法是算法設(shè)計中最基本的算法之一。排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。第3章排序算法排序算法的穩(wěn)定性：如果兩個數(shù)值相等的數(shù)，在排序前和排序后能保持兩個數(shù)在序列中前后位置順序不變的排序算法稱為穩(wěn)定排序，否則為不穩(wěn)定排序。例如，有Ai=Aj，排序前Ai在Aj的前面，排序后Ai仍然還在Aj的前面，這時候就稱為穩(wěn)定排序，否則，就稱為不穩(wěn)定排序。時間復(fù)雜度：對排序數(shù)據(jù)的總操作次數(shù)。反映當(dāng)n變化時，操作次數(shù)呈現(xiàn)什么規(guī)律?？臻g復(fù)雜度：指算法在計算機(jī)內(nèi)執(zhí)行時所需存儲空間的度量，它也是數(shù)據(jù)規(guī)模n的函數(shù)。3.1排序的相關(guān)概念冒泡排序（BubbleSort）是一種簡單實用的排序算法。它是從隊列首部開始，依次比較兩個相鄰的數(shù)據(jù)，如果順序錯誤就把它們進(jìn)行交換，直至沒有數(shù)據(jù)可以交換為止。在這個過程中，待排序的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端，就如同水池中的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。3.2冒泡排序在使用冒泡排序時，首先應(yīng)該確定是進(jìn)行升序排序還是降序排序。升序排序就是將待排列的數(shù)據(jù)按照從小到大的順序排序，當(dāng)升序排序時，需要較大的數(shù)向后“沉”，而將較小的數(shù)向前“冒”。降序排序則正好相反，它是將待排列得數(shù)據(jù)按照從大到小的順序排序，它需要較小的數(shù)向后“沉”，而將較大的數(shù)向前“冒”。第1步：比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。第2步：對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。第3步：針對所有的元素重復(fù)以上的步驟，除了最后一個。第4步：持續(xù)每次對越來越少的元素重復(fù)步驟1~3，直到?jīng)]有任何一對數(shù)字需要比較。3.2.1冒泡排序算法描述例如，將序列“5，4，3，2，1”變成升序“1，2，3，4，5”的“冒泡排序”的示意圖如圖3.1。從圖中可以看出隨著“5”逐漸“沉”下去，“1”逐漸“冒”了上來。重復(fù)沉“4”“3”“2”“1”會冒到最頂上。3.2.1冒泡排序算法描述圖3.1冒泡原理示意【例3.1】冒泡排序時間限制：1000ms內(nèi)存限制：32MB問題描述編寫一個程序：從鍵盤上輸入整數(shù)個數(shù)n（n<255），按照冒泡排序的思想，對n個整數(shù)進(jìn)行升序排序，最后輸出排序結(jié)果。輸入說明輸入的數(shù)據(jù)之間空一格，最后一個回車。輸出說明打印輸出的時候空一格。輸入樣例9876543210輸出樣例01234567893.2.2冒泡排序程序?qū)崿F(xiàn)舉例問題分析：首先需要建立一個int類型的數(shù)組arr存儲待排序數(shù)據(jù)，然后利用冒泡排序?qū)?shù)組中的數(shù)據(jù)進(jìn)行排序。如果是n個數(shù)排序，共需要n-1輪排序。這就需要建立一個循環(huán)結(jié)構(gòu)。設(shè)置一個循環(huán)控制變量i，通過控制變量i實現(xiàn)n-1輪排序。令i=1作為循環(huán)的初始條件，用“i<=n-1”作為循環(huán)控制表達(dá)式，用“i++”作為循環(huán)控制變量的改變。循環(huán)體完成數(shù)組的每輪排序比較。循環(huán)語句如下：for(i=1;i<=n-1;i++){//每輪比較的程序代碼}冒泡排序使用了兩層循環(huán)嵌套，外層循環(huán)稱為遍歷。例如，第一輪遍歷就是外層循環(huán)的第一次迭代。在每次內(nèi)層循環(huán)的迭代過程中，對列表中剩余的未排序元素進(jìn)行排序，直到最高值冒泡到最后為止。第一輪遍歷將進(jìn)行N-1次比較，第二輪遍歷將進(jìn)行N-2次比較，而每輪后續(xù)遍歷將比前一輪減少一次比較操作。當(dāng)待排序序列是有序的時候（最好情況），比較次數(shù)為n-1次，沒有數(shù)據(jù)交換，此時時間復(fù)雜度為O(n)；當(dāng)待排序序列是逆序的時候（最壞的情況），當(dāng)初始序列從大到小逆序時，需要進(jìn)行n-1趟排序，進(jìn)行n(n-1)/2次比較和交換，此時的時間復(fù)雜度為O(n2)?？臻g復(fù)雜度：冒泡排序只需要一個臨時變量來交換數(shù)據(jù)，所以為O(1)。3.2.3冒泡排序算法分析選擇排序(SelectionSort)是一種簡單直觀的排序算法。它的基本思想：首先在待排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。

3.3選擇排序（SelectionSort）n個記錄的選擇排序可經(jīng)過n-1輪選擇排序得到有序結(jié)果。具體算法描述如下：3.3.1選擇排序算法描述第1步：待排序序列為R[1..n]，有序序列為空；第2步：第i趟排序(i=1,2,3…,n-1)開始時，當(dāng)前有序序列和無序序列（待排序列）分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無序序列中選出關(guān)鍵字最小的記錄R[k]，將它與無序序列的第1個記錄R交換，使R[1..i]和R(i+1..n)分別變?yōu)橛涗泜€數(shù)增加1個的新有序序列和記錄個數(shù)減少1個的新無序序列；第3步：n-1趟結(jié)束，數(shù)組有序了。

例如，將序列“53，64，28，72，1”變成升序“1，28，53，64，72”的“選擇排序”的第一輪操作如圖3.3所示。從圖中可以看出隨著待排序序列中的元素“1”首先被“選擇”出來與數(shù)組下標(biāo)為0的元素“53”交換位置，然后在待排序序列“64，28，72，53”中繼續(xù)“選擇”最小的元素“28”與數(shù)組下標(biāo)為1的元素“64”交換位置，重復(fù)相同的操作，直至待排序序列完全有序。

圖3-3第一輪選擇排序示意圖3.3.1選擇排序算法描述【例3.2】選擇排序時間限制：1000ms內(nèi)存限制：32MB問題描述編寫一個算法實現(xiàn)選擇排序思想，并將亂序數(shù)列變成升序數(shù)列。輸入說明第一行輸入數(shù)據(jù)元素的個數(shù)，第二行為待排序的數(shù)據(jù)元素，輸入的數(shù)據(jù)之間空一格，最后一個回車。輸出說明打印輸出的時候空一格，尾數(shù)后沒有空格。輸入樣例1071468952310輸出樣例12345678910

3.3.2選擇排序算法實現(xiàn)舉例3.3.2選擇排序算法實現(xiàn)舉例問題分析根據(jù)題意和選擇排序的基本思想，可以定義變量n存儲待排序的元素個數(shù)，然后根據(jù)第一行輸入的數(shù)值n動態(tài)分配存儲空間大小arr=(int*)malloc(sizeof(int)*n)，而在選擇排序的過程中，在每一輪排序中找到數(shù)值最小的元素，并臨時存儲在minIdx中，直到本輪循環(huán)結(jié)束for(inti=0;i<n-1;i++){intminIdx=i;for(intj=i+1;j<n;j++){if(arr[minIdx]>arr[j]){minIdx=j;}}后把值最小元素“放”到arr[i]的位置。temp=arr[minIdx];arr[minIdx]=arr[i];arr[i]=temp;選擇排序是一種簡單直觀的排序算法，無論待排序序列是正序還是逆序，每?輪的最?（最大）值都需要?較到最后才能確定，那么，最壞情況和最好情況下都需要?較n-1次，再加上遍歷整個序列的O(n)，總的復(fù)雜度為O(n2)，平均復(fù)雜度也是O(n2)。所以，選擇排序比較適合數(shù)據(jù)規(guī)模不大的情形。空間復(fù)雜度方面，選擇排序只需要?個額外用來存放“臨時最?值”的空間，除此之外，不占用額外的內(nèi)存，所以空間復(fù)雜度為O(1)，同時，選擇排序是不穩(wěn)定排序。。

3.3.3選擇排序算法分析插入排序（Insertion-Sort）是一種簡單直觀的排序算法。它的工作原理是將未排好序的元素?個個地插?到已排好序（開始時為空）的序列中，插?時，需要與已排好序的元素進(jìn)?多次?較，直到找到合適（比前一個元素大，比后一個元素小或者比前一個元素小，比后一個元素大）的位置插?，?原來已排好序的部分元素可能需要進(jìn)?后移操作，最后形成有序序列。

3.4插入排序（InsertionSort）第4步：重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；第6步：重復(fù)步驟2~5，直到序列有序。

第5步：將新元素插入到該位置后；第2步：取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；第1步：從第一個元素開始，此時，只有一個元素，該元素可以看作已排序；第3步：如果該元素（已排序）大于新元素，將該元素移到下（后移）一位置；一般來說，插入排序一般都采用in-place在數(shù)組上實現(xiàn)。具體算法描述如下：3.4.1插入排序算法描述例如，將序列“5，4，3，2，1”變成升序“1，2，3，4，5”的“插入排序”的操作如圖3.4所示。3.4.1插入排序算法描述圖3-4插入排序示意圖【例3.4】插入排序時間限制：1000ms內(nèi)存限制：32MB問題描述實現(xiàn)插入排序算法，并將亂序數(shù)列變成升序數(shù)列。輸入說明第一行輸入數(shù)據(jù)元素的個數(shù)，第二行為待排序的數(shù)據(jù)元素，輸入的數(shù)據(jù)之間空一格，最后一個回車。輸出說明打印輸出的時候空一格，尾數(shù)后沒有空格。輸入樣例1023846815473271450輸出樣例234152347685071843.4.2插入排序算法實現(xiàn)舉例3.4.2插入排序算法實現(xiàn)舉例算法分析定義兩個變量i和j分別的控制外層循環(huán)和內(nèi)層循環(huán)，然后依次取出待排序序列中的各個元素存儲在val中，用val與未排序序列中元素arr[j]比較，直到找到val的“位置”，經(jīng)過n1輪排序即可得到有序序列，核心參考代碼如下：1voidsort_array(int*arr,intn)

2{

3for(inti=1;i<n;i++){

4intval=arr[i];

5for(intj=i-1;j>=0;j--){

6if(val<arr[j]){//待插入的元素小于當(dāng)前元素的值，7arr[j+1]=arr[j];//當(dāng)前元素向后移動一個位置8arr[j]=val;

9}

10else{

11break;

12}

13}

14}

15}空間復(fù)雜度：插入排序在實現(xiàn)上，一般采用in-place在數(shù)組上實現(xiàn)，即只需用到O(1)的額外空間，因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。時間復(fù)雜度：最壞情況：當(dāng)待排序序列正好為逆序狀態(tài)，?先遍歷整個序列，然后?個個地將待插?元素放在已排序的序列最前?，之后的所有元素都需向后移動?位，所以?較和移動的時間復(fù)雜度都是O(n)，再加上遍歷整個序列的復(fù)雜度，總復(fù)雜度為O(n2)。最好情況：當(dāng)待排序序列正好為正序狀態(tài)，則遍歷完整個序列，當(dāng)插?元素時，只?較?次就夠了，所以時間復(fù)雜度為O(n)。平均情況：當(dāng)被插?的元素放在已排序的序列中間位置時，為平均情況，?較和移動的時間復(fù)雜度為O(n2)，所以總的時間復(fù)雜度依然為O(n2)。穩(wěn)定性：插?排序的?較是從有序序列的末尾開始，也就是想要插?的元素和已經(jīng)有序的最?者開始?起，如果?它?則直接插?在其后?，否則?直往前找直到找到它該插?的位置。如果遇見?個和插?元素值相等的，那么插?元素把想插?的元素放在相等元素的后?。值相等元素的前后順序沒有改變，所以插?排序是穩(wěn)定的。3.4.3插入排序算法分析歸并排序是建立在歸并操作上的一種有效的排序算法。其基本思想是將已有序的子序列合并，得到完全有序的序列，即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。歸并排序算法是基于分治策略而設(shè)計的。在被稱為劃分的第一階段中，算法將數(shù)據(jù)遞歸地分成兩部分，直到數(shù)據(jù)的規(guī)模小于定義的閾值。在被稱為歸并的第二階段中，算法不斷地進(jìn)行歸并和處理，直到得到最終的結(jié)果。3.5歸并排序（MergeSort）3.5.1歸并排序算法描述01第1步：把長度為n的輸入序列分成兩個長度為n/2的子序列；02第2步：對這兩個子序列分別采用歸并排序；03第3步：將兩個排序好的子序列合并成一個最終的排序序列。例如：將待排序序列[25,6,93,17,41,86,32,79,58]排成升序序列[6,17,25,32,41,58,79,86,93]的歸并操作如圖3.5所示。3.5.1歸并排序算法描述圖3-5歸并排序示意圖【例3.6】合并兩個序列時間限制：1000ms內(nèi)存限制：32MB問題描述輸入兩個遞增的序列，輸出合并這兩個序列后的遞增序列。輸入說明每個測試案例包括3行：第一行為1個整數(shù)n（1<=n<=1000000）表示這兩個遞增序列的長度。第二行包含n個整數(shù)，表示第一個遞增序列。第三行包含n個整數(shù)，表示第二個遞增序列。輸出說明對應(yīng)每個測試案例，輸出合并這兩個序列后的遞增序列。輸入樣例413572468輸出樣例12345678。3.5.2歸并排序算法實現(xiàn)舉例：算法分析將兩個遞增序列合并成為一個遞增序列，常規(guī)的操作是將第二個遞增追加到第一個遞增序列的后面，然后進(jìn)行冒泡排序就可以得到一個遞增序列。但是，當(dāng)問題規(guī)模增大時，時間復(fù)雜度急劇增加，本題嘗試用歸并排序思想來解決。因歸并的方法采用了分治的策略，性能大大提升，歸并排序和選擇排序一樣，性能不受輸入數(shù)據(jù)的影響，但其性能比選擇排序大大提升，因為其時間復(fù)雜度一直為O(nlogn），不過，帶來的代價是需要額外的內(nèi)存空間。時間復(fù)雜度：歸并排序的時間主要消耗在劃分序列和合并序列上，由于采?遞歸?式進(jìn)?合并，如果集合長度為n，那么劃分的層數(shù)就是logn，每一層進(jìn)行歸并操作的運算量是n。所以，歸并排序的時間復(fù)雜度等于每一層的運算量×層級數(shù)，即O(nlogn)，?且不管元素是否基本有序都需要進(jìn)行類似操作，所以該算法的最優(yōu)時間復(fù)雜度和最差時間復(fù)雜度及平均時間復(fù)雜度都相同。空間復(fù)雜度：歸并排序是需要用到額外空間的，但是每次歸并所創(chuàng)建的額外空間都會隨著方法結(jié)束而釋放，因此單次歸并操作開辟的最大空間是n。所以，歸并排序的空間復(fù)雜度是O(n)。歸并排序是穩(wěn)定排序算法。3.5.3歸并排序算法分析快速排序和冒泡排序一樣，也是交換類排序?法。其基本思想是通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。3.6快速排序（QuickSort）快速排序使用分治法來把一個序列分為兩個子序列。具體算法描述如下：3.6.1快速排序算法描述第1步：從數(shù)列中挑出一個元素，稱為“基準(zhǔn)”（pivot）；第2步：將所有元素比基準(zhǔn)值小的集中在基準(zhǔn)左邊（或者右邊），所有元素比基準(zhǔn)值大的集中在基準(zhǔn)的右邊（或者左邊，相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置，這個稱為分區(qū)（partition）操作；第3步：采用遞歸（recursive）思想把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序再一次進(jìn)行快速排序。第4步：重復(fù)以上過程，直到序列有序。例如：將待排序序列[59,16,83,97,21,45,3,74,68]排成升序序列[3,16,21,45,59,68,74,83,97]的快速排序的第一輪操作如圖3.6所示?？焖倥判虮闅v開始的時候是從后面j往前遍歷，當(dāng)元素值大于pivot時j--；元素值小于pivot時，j保持不變，并且將j指向的值替換i指向的值，i++；這時，i從前往后遍歷，小于pivot的值就i++；遇到大于pivot的元素時，i不變，并且將i指向的值替換j指向的值，j--，這樣交替進(jìn)行，直到