1、第十二章算法與數(shù)據(jù)結(jié)構(gòu),12.1算法的基本概念,該節(jié)知識(shí)點(diǎn)所占試題比重為12%，屬于重點(diǎn)考查對象，基本上每次必考，主要考查算法的定義和對算法復(fù)雜度的理解。歷次試題分值在04分之間波動(dòng)。,12.1.1考點(diǎn)1：算法的定義,算法是對一個(gè)問題求解步驟的一種描述，是求解問題的方法，它是指令的有限序列，其中每條指令表示一個(gè)或者多個(gè)操作。一般來說，一個(gè)算法具有以下5個(gè)主要特性。 有窮性：一個(gè)算法（對任何合法的輸入）在執(zhí)行有窮步后能夠結(jié)束，并且在有限的時(shí)間內(nèi)完成。 確定性：算法中的每一步都有確切的含義。 可行性：算法中的操作能夠用已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。 輸入：一個(gè)算法有零個(gè)或者多個(gè)輸入，零個(gè)輸入

2、就是算法本身確定了初始條件。 輸出：一個(gè)算法有一個(gè)或者多個(gè)輸出，以反映出數(shù)據(jù)加工的結(jié)果。,12.1.2 考點(diǎn)2：算法復(fù)雜度,算法復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度，是衡量一個(gè)算法好壞的度量。 1、時(shí)間復(fù)雜度：基本操作重復(fù)執(zhí)行的次數(shù)的階數(shù) T(n)=o(f(n) 2、空間復(fù)雜度：是算法所需空間的度量。 G（n）= O(f(n),例1：NXN矩陣相乘 for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; ,12.2 數(shù)據(jù)結(jié)構(gòu)的定義,該節(jié)知識(shí)點(diǎn)所占試題比重為12%，屬于重點(diǎn)考查對象，基本上每次必考，主要考查數(shù)據(jù)的

3、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。歷次試題分值在04分之間波動(dòng)。,12.2.1考點(diǎn)1：什么是數(shù)據(jù)結(jié)構(gòu),一、基本概念和術(shù)語 數(shù)據(jù)（data)所有能輸入到計(jì)算機(jī)中去的描述客觀事物的符號(hào) 數(shù)據(jù)元素（data element）數(shù)據(jù)的基本單位，也稱節(jié)點(diǎn)（node）或記錄（record） 數(shù)據(jù)項(xiàng)（data item）有獨(dú)立含義的數(shù)據(jù)最小單位，也稱域(field) 數(shù)據(jù)結(jié)構(gòu)（data structure)數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合,數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu)分為： 順序存儲(chǔ)結(jié)構(gòu)借助元素在存儲(chǔ)器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系 鏈?zhǔn)?/p>

4、存儲(chǔ)結(jié)構(gòu)借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,鏈?zhǔn)酱鎯?chǔ),h,12.2.2考點(diǎn)2：數(shù)據(jù)結(jié)構(gòu)的圖形表示,根據(jù)數(shù)據(jù)元素之間關(guān)系的不同，通常有4種結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖狀結(jié)構(gòu)。,12.3線性表,線性表一般和其他知識(shí)點(diǎn)結(jié)合起來出題。在每次所考的數(shù)據(jù)結(jié)構(gòu)、棧、隊(duì)列、鏈表、查找、排序等試題中，均涉及線性表的概念。,12.3.1考點(diǎn)1：線性表,一、線性結(jié)構(gòu)特點(diǎn)：在數(shù)據(jù)元素的非空有限集中 存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素 存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素 除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有

5、一個(gè)前驅(qū) 除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼,二、線性表的邏輯結(jié)構(gòu) 定義：一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列,例 英文字母表（A,B,C,.Z)是一個(gè)線性表,特征： 元素個(gè)數(shù)n表長度，n=0空表 1in時(shí) ai的直接前驅(qū)是ai-1，a1無直接前驅(qū) ai的直接后繼是ai+1，an無直接后繼,12.3.2考點(diǎn)2：線性表的順序存儲(chǔ)結(jié)構(gòu) 它用一組地址連續(xù)的存儲(chǔ)單元來存儲(chǔ)線性表的元素。 線性表中第i+1個(gè)元素的存儲(chǔ)位置loc(ai+1)和第i個(gè)元素的存儲(chǔ)位置loc（ai）滿足以下關(guān)系： Loc(ai+1)=loc(ai)+S其中： S一個(gè)元素占用的存儲(chǔ)單元個(gè)數(shù) LOC(ai)線性表第i個(gè)元

6、素的地址 特點(diǎn)： 實(shí)現(xiàn)邏輯上相鄰物理地址相鄰 實(shí)現(xiàn)隨機(jī)存取 實(shí)現(xiàn)：可用C語言的一維數(shù)組實(shí)現(xiàn),12.3.2考點(diǎn)2：線性表的順序存儲(chǔ)結(jié)構(gòu),線性表的第i個(gè)元素的存儲(chǔ)位置為： Loc(ai)=loc(a1)+(i-1)s 其中，loc(a1)表示第1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置，一般被稱為線性表的基地址。,12.3.3考點(diǎn)3：線性表的插入和刪除操作,線性表的插入操作是指在線性表的第i個(gè)元素與第i1個(gè)元素之間插入一個(gè)新的數(shù)據(jù)元素a，使長度為n的線性表 （a1，ai,ai+1,an） 變成長度為n1的線性表 （a1，ai,a,ai+1,an） 算法時(shí)間復(fù)雜度T(n) 在長度為n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的

7、元素的平均次數(shù)為：n/2,12.3.3考點(diǎn)3：線性表的插入和刪除操作,刪除操作是在線性表中刪除一個(gè)元素ai，使長度為n的線性表 （a1，ai,ai+1,an） 變成長度為n-1的線性表 （a1，ai-1,ai+1,an） 算法時(shí)間復(fù)雜度T(n) 在長度為n的線性表中刪除一個(gè)元素所需移動(dòng)的元素的平均次數(shù)為(n-1)/2,12.4棧,該節(jié)知識(shí)點(diǎn)所占試題比重為12%，屬于重點(diǎn)考查對象，基本上每次必考，主要考查棧的定義、存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算。歷次試題分值在02分之間波動(dòng)。,12.4.1 考點(diǎn)1：什么是棧,棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。 允許插入和刪除的一端叫做棧頂，另一端叫做棧底。 不含有

8、元素的棧叫做空棧。,12.4.2 考點(diǎn)2：棧的順序存儲(chǔ)結(jié)構(gòu),棧的順序存儲(chǔ)結(jié)構(gòu)是利用一組連續(xù)地址的存儲(chǔ)單元來存儲(chǔ)從棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)一個(gè)指針top指示棧頂元素在順序棧中的位置，一個(gè)指針base指示棧底元素的位置。,12.4.3 考點(diǎn)3：棧的插入和刪除運(yùn)算,棧的插入和刪除運(yùn)算只能在棧頂進(jìn)行。,12.5隊(duì)列,該節(jié)知識(shí)點(diǎn)占試題比重為12%，屬于一般考查對象，主要考查隊(duì)列的定義、存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算。從歷次試題來看，隊(duì)列還沒有單獨(dú)出過試題，一般以和其他知識(shí)點(diǎn)結(jié)合起來的試題形式出現(xiàn)。歷次試題分值在02分之間波動(dòng)。,12.5.1 考點(diǎn)1：什么是隊(duì)列,隊(duì)列是限定了插入和刪除操作的線性表。它只允許在表

9、的一端進(jìn)行插入操作，而在另外一端進(jìn)行刪除操作。隊(duì)列中，允許插入元素的一端稱為隊(duì)尾，允許刪除元素的一端稱為隊(duì)頭。,12.5.2 考點(diǎn)2：隊(duì)列的順序存儲(chǔ)結(jié)構(gòu),與順序棧類似，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)是利用一組連續(xù)地址的存儲(chǔ)單元來存儲(chǔ)從隊(duì)頭到隊(duì)尾的數(shù)據(jù)元素，同時(shí)附設(shè)一個(gè)指針front指示隊(duì)頭元素在隊(duì)列中的位置，一個(gè)指針rear指示隊(duì)尾元素的位置。當(dāng)插入新的隊(duì)列元素時(shí)，rear增1；當(dāng)刪除隊(duì)頭元素時(shí)，front增1。,12.5.3 考點(diǎn)3：隊(duì)列的插入和刪除運(yùn)算,隊(duì)列只允許在表的一端進(jìn)行插入，而在表的另外一端進(jìn)行刪除，和我們生活中的隊(duì)列一樣是按照先進(jìn)先出的原則，所以隊(duì)列又稱為先進(jìn)先出的線性表。,12.6 線性單

10、鏈表、雙向鏈表與循環(huán)鏈表,該節(jié)知識(shí)點(diǎn)占試題比重為3%，屬于非重點(diǎn)考查對象，主要考查線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及基本運(yùn)算。,12.7樹,該節(jié)知識(shí)點(diǎn)所占試題比重為31%，屬于重點(diǎn)考查對象，每次必考，主要考查二叉樹的定義、存儲(chǔ)結(jié)構(gòu)及3種遍歷算法。,12.7.1 考點(diǎn)1：樹的定義,樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。 樹是n（n0）個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m（m0）個(gè)互不相交的有限集T1，T2，Tm，其中每一個(gè)集合本身又是一棵樹，稱為子樹。,第六章 樹和二叉樹,樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，以分支關(guān)系描述數(shù)據(jù)元素之間的層次結(jié)

11、構(gòu) 6.1 樹 定義：樹(tree)是n(n 0)個(gè)結(jié)點(diǎn)的有限集合T，其中： 有且僅有一個(gè)特殊的結(jié)點(diǎn)，稱為樹的根結(jié)點(diǎn)(root) 當(dāng)n1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集合T1,T2,Tm，其中每一個(gè)集合本身又是一棵樹，稱為根的子樹(subtree) 特點(diǎn)： 樹中至少有一個(gè)結(jié)點(diǎn)根結(jié)點(diǎn) 樹中各子樹是互不相交的集合,根,子樹,T1=B,E,F,K,L,T2=C,G,T3=D,H,I.J.M,T=A,T=A,B,C,D,M,樹的特點(diǎn)： 1.樹的根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，除根之外的所有結(jié)點(diǎn)都有且只有一個(gè)前驅(qū)結(jié)點(diǎn)； 2.樹中所有的結(jié)點(diǎn)可以有0個(gè)或多個(gè)后繼結(jié)點(diǎn)。 下圖所示結(jié)構(gòu)均不是樹結(jié)

12、構(gòu)：,基本術(shù)語 結(jié)點(diǎn)(node)表示樹中的數(shù)據(jù)元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹的分支 結(jié)點(diǎn)的度(degree)結(jié)點(diǎn)擁有的子樹個(gè)數(shù) 樹的度樹中所有結(jié)點(diǎn)的度的最大值 葉子(leaf)結(jié)點(diǎn)度為0的結(jié)點(diǎn) 分支結(jié)點(diǎn)除葉子結(jié)點(diǎn)外的所有結(jié)點(diǎn) 孩子(child)結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子 雙親(parents)孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親,基本術(shù)語 兄弟(sibling)具有同一雙親的孩子結(jié)點(diǎn) 結(jié)點(diǎn)的層次(level)從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層 深度(depth)樹中結(jié)點(diǎn)的最大層次數(shù) 有序樹樹中各結(jié)點(diǎn)的子樹按照從左到右的次序安排 無序樹與上一情況相反 森林(forest)m(m0)棵互不

13、相交的樹的集合,結(jié)點(diǎn)A的度：3 結(jié)點(diǎn)B的度：2 結(jié)點(diǎn)M的度：0,葉子：K，L，F(xiàn)，G，M，I，J,結(jié)點(diǎn)A的孩子：B，C，D 結(jié)點(diǎn)B的孩子：E，F(xiàn),結(jié)點(diǎn)I的雙親：D 結(jié)點(diǎn)L的雙親：E,結(jié)點(diǎn)B，C，D為兄弟 結(jié)點(diǎn)K，L為兄弟,樹的度：3,結(jié)點(diǎn)A的層次：1 結(jié)點(diǎn)M的層次：4,樹的深度：4,A,D,H是M的祖先 I是A,D的子孫,6.2 二叉樹 定義 定義：二叉樹是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成 特點(diǎn) 每個(gè)結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn)) 二叉樹的子樹有左、右之分，且其次序不能任意顛倒,基本形態(tài),二叉樹性質(zhì)

14、性質(zhì)1 ：在二叉樹的第i層上至多有2i1結(jié)點(diǎn) i2,i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，2i1201是對的。 假設(shè)對所有j(1ji)命題成立，即第j層上至多有2j1個(gè)結(jié)點(diǎn)。那么，第i-1層至多有 2i2 個(gè)結(jié)點(diǎn)。 又二叉樹每個(gè)結(jié)點(diǎn)的度至多為2 第i層上最大結(jié)點(diǎn)數(shù)是第i-1層的2倍，即22i22i1 故命題得證,證明：用歸納法證明之,二叉樹性質(zhì),證明：由性質(zhì)1，可得深度為k 的二叉樹最大結(jié)點(diǎn)數(shù)是,性質(zhì)2：深度為k的二叉樹至多有2k1 個(gè)結(jié)點(diǎn)(k1),性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1,證明：n1為二叉樹T中度為1的結(jié)點(diǎn)數(shù) 因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均

15、小于或等于2 所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2 又二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè) 分支進(jìn)入 設(shè)B為分支總數(shù)，則n=B+1 又：分支由度為1和度為2的結(jié)點(diǎn)發(fā)出， B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1,幾種特殊形式的二叉樹 滿二叉樹 定義：一棵深度為k且有2k1 個(gè)結(jié)點(diǎn)的二 叉,特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù),樹稱為滿二叉樹。,幾種特殊形式的二叉樹,完全二叉樹 定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對應(yīng)時(shí)，稱為 特點(diǎn) 葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn) 對任一結(jié)點(diǎn)，

16、若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l 或l+1,證明：設(shè)所求完全二叉樹的深度為k，由完全二叉樹定義及性質(zhì)2可得：2k-1-1n2k-1 或 2k-1n2k 取對數(shù)后有：k-1log2nk，即log2nklog2n+1 又k必為整數(shù)， k=log2n+1,性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為,log2n+1,性質(zhì)5：如果對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)，則對任一結(jié)點(diǎn)i(1in)，有： (1) 如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無雙 親；如果i1，則其雙親是i/2 (2) 如果2in，則結(jié)點(diǎn)i無左孩子；如果 2in，則其左孩子是2i (3) 如果2i+1

17、n，則結(jié)點(diǎn)i無右孩子；如果 2i+1n，則其右孩子是2i+1,二叉樹的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu) 實(shí)現(xiàn)：按滿二叉樹的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹中的數(shù)據(jù)元素 特點(diǎn)： 結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中 浪費(fèi)空間，適于存滿二叉樹和完全二叉樹,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉鏈表,typedef struct node datatype data; struct node *lchild, *rchild; JD;,在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域,12.7.5 考點(diǎn)5：二叉樹的遍歷,遍歷：按照一定次序訪問樹中的所有結(jié)點(diǎn)， 且每個(gè)結(jié)點(diǎn)僅被訪問一次的過程。,遍歷二叉樹的方法 先序遍歷：先訪問根結(jié)點(diǎn),然后分別先序遍

18、歷左子樹、右子樹 中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后中序遍歷右子樹 后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點(diǎn) 按層次遍歷：從上到下、從左到右訪問各結(jié)點(diǎn),D L R,先序遍歷序列：A B D C,先序遍歷:,若二叉樹為空，遍歷結(jié)束。否則 （1）訪問根結(jié)點(diǎn)； （2）先序遍歷根結(jié)點(diǎn)的左子樹； （3）先序遍歷根結(jié)點(diǎn)的右子樹。,L D R,中序遍歷序列：B D A C,中序遍歷:,若二叉樹為空，遍歷結(jié)束。否則 （1）中序遍歷根結(jié)點(diǎn)的左子樹； （2）訪問根結(jié)點(diǎn)； （3）中序遍歷根結(jié)點(diǎn)的右子樹。,L R D,后序遍歷序列： D B C A,后序遍歷:,若二叉樹為空，遍歷結(jié)束。否則 （1）

19、后序遍歷根結(jié)點(diǎn)的左子樹； （2）后序遍歷根結(jié)點(diǎn)的右子樹； （3）訪問根結(jié)點(diǎn)。,先序遍歷：,中序遍歷：,后序遍歷：,層次遍歷：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,12.8 查找算法,該節(jié)知識(shí)點(diǎn)占試題比重為9%，屬于一般考查對象，主要考查順序查找和二分查找。歷次試題分值在02分之間波動(dòng)。,12.8 查找算法,查找表由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合 關(guān)鍵字是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素 查找也叫檢索，是根據(jù)給定的某個(gè)值，在表中確定一

20、個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素,12.8 查找算法,查找方法評價(jià) 時(shí)間復(fù)雜度 空間復(fù)雜度 平均查找長度ASL(Average Search Length)：為確定記錄在表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值叫查找算法的,12.8.1考點(diǎn)1：順序查找 查找過程：從表的一端開始逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較,64,監(jiān)視哨,比較次數(shù)=5,比較次數(shù)： 查找第n個(gè)元素： 1 查找第n-1個(gè)元素：2 . 查找第1個(gè)元素： n 查找第i個(gè)元素： n+1-i 查找失?。?n+1,順序查找方法的ASL,12.8.2 考點(diǎn)2：二分查找 查找過程：每次將待查記錄所在區(qū)間縮小一半 適用條件：采用

21、順序存儲(chǔ)結(jié)構(gòu)的有序表 算法實(shí)現(xiàn) 設(shè)表長為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn),k為給定值 初始時(shí)，令low=1,high=n,mid=(low+high)/2 讓k與mid指向的記錄比較 若k=rmid.key，查找成功 若krmid.key，則low=mid+1 重復(fù)上述操作，直至lowhigh時(shí)，查找失敗,算法描述,12.9排序算法,該節(jié)知識(shí)點(diǎn)所占試題比重為9%，屬于一般考查對象，主要考查交換類排序、選擇類排序及插入類排序。從歷次試題來看，以選擇題和填空題的形式出現(xiàn)，分值有波動(dòng)，如圖2-28所示。,12.9.1 考點(diǎn)1：排序概述,10.1概述 排序?qū)⒁粋€(gè)數(shù)

22、據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列叫 排序分類 按待排序記錄所在位置 內(nèi)部排序：待排序記錄存放在內(nèi)存 外部排序：排序過程中需對外存進(jìn)行訪問的排序 按排序依據(jù)原則 插入排序：直接插入排序、折半插入排序、希爾排序 交換排序：冒泡排序、快速排序 選擇排序：簡單選擇排序、堆排序 歸并排序：2-路歸并排序 基數(shù)排序,12.9.2 考點(diǎn)2：插入類排序,直接插入排序 基本思想：順序地把待排序列中的各個(gè)記錄按其關(guān)鍵字的大小，插入到已排序序列中的適當(dāng)位置 排序過程：整個(gè)排序過程為n-1趟插入，即先將序列中第1個(gè)記錄看成是一個(gè)有序子序列，然后從第2個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序 直接插入排序方法是穩(wěn)定的。,例,49 38 65 97 76 13 27,i=2 38 (38 49) 65 97 76 13 27,i=3 65 (38 49 65) 97 76 13 27,i=4 97 (38 49 65 97) 76 13 27,i=5 76 (38 49 65 76 97) 13 27,i=6 13 (13 38 49