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

第二章數(shù)據(jù)結(jié)構(gòu)與算法2.1基本要求1.學(xué)習(xí)目的與要求數(shù)據(jù)結(jié)構(gòu)主要研究把具有一定邏輯關(guān)係的一批數(shù)據(jù)按某種存儲方式存放在計算機(jī)的存儲器中,并在這批數(shù)據(jù)上定義一系列操作.如何操作就是算法問題,算法與數(shù)據(jù)結(jié)構(gòu)是相互聯(lián)繫的.算法總是建立在一定數(shù)據(jù)結(jié)構(gòu)上的,合理的數(shù)據(jù)結(jié)構(gòu)可以使算法簡單高效.學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的目的,是理解和掌握各種數(shù)據(jù)結(jié)構(gòu)的定義及基本操作的實現(xiàn),理解掌握典型的算法思想,算法設(shè)計方法和計算算法的時間複雜度.2.本章重點⑴線性表,順序表和鏈錶,掌握線性表的概念,兩種存儲結(jié)構(gòu),優(yōu)缺點及兩種存儲結(jié)構(gòu)上的基本操作⑵棧與隊列,棧和隊列的概念,順序棧,鏈棧的操作,棧的應(yīng)用,循環(huán)隊列,循環(huán)鏈隊列的操作⑶串的基本運算和模式匹配,串的基本運算的含義,瞭解模式匹配算法和時間複雜度⑷多維數(shù)組和廣義表,多維數(shù)組及特殊矩陣的地址公式,廣義表的運算和存儲⑸樹和二叉樹,樹,二叉樹的定義,術(shù)語,二叉樹的性質(zhì),存儲,遍歷,應(yīng)用,線索二叉樹的概念,樹與二叉樹的關(guān)係⑹圖的存儲及其操作,圖的定義,術(shù)語,圖的存儲,圖的遍歷,圖的操作(最小生成樹,拓?fù)渑判?關(guān)鍵路徑,最短路徑)⑺表和樹的查找,表和樹的概念,平均比較次數(shù),二叉排序樹和平衡二叉樹的插入,刪除,瞭解B-樹的定義⑻Hash技術(shù),哈希表構(gòu)造,解決衝突的方法及哈希表的查找⑼排序算法,直接插入排序,冒泡排序,簡單選擇排序,快速排序,堆排序,歸并排序和希爾排序算法和時間發(fā)雜度,瞭解基數(shù)排序,外排序的概念和算法⑽算法設(shè)計方法,分治法,遞推法,貪心法,回溯法,動態(tài)規(guī)劃發(fā)和分支界法2.2基本內(nèi)容2.2.1數(shù)據(jù)結(jié)構(gòu)與算法概念數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)DS=(A,R),其中A是數(shù)據(jù)元素的非空有限集合,R是定義在A上的關(guān)係的非空有限集合,結(jié)構(gòu)就元素之間的關(guān)係算法,就是解決問題的方法和步驟算法的時間複雜度,算法語句中重複執(zhí)行的次數(shù)(或稱語句頻度),或算法中基本操作次數(shù),一般用數(shù)量級O()來描述2.2.2線性表線性表的定義,線性表是n(n>=0)個元素的有限序列,當(dāng)n=0時,稱為空表,當(dāng)n>0時,線性表通常表示為(a1,a2,a3,……,an),其中a1無前驅(qū),an無後繼,其餘結(jié)點有且只有一個前驅(qū)和一個後繼線性表的存儲,線性表有順序存儲和鏈?zhǔn)酱鎯煞N結(jié)構(gòu)順序存儲結(jié)構(gòu),在連續(xù)的存儲空間中依次存儲線性表的各個元素,具體用一維數(shù)組來得到連續(xù)的存儲空間順序存儲的結(jié)構(gòu)特點,存儲位置上直接反映了元素的邏輯關(guān)係,不需要指出前驅(qū)後繼,操作特點,便於查找,不便於插入,刪除鏈?zhǔn)酱鎯Y(jié)構(gòu),在任意(連續(xù)或不連續(xù))的存儲空間中存放線性表的各元素,所以每個結(jié)點要帶指針指出前驅(qū)後繼,用動態(tài)分配空間實現(xiàn).單鏈結(jié)構(gòu),結(jié)點的指針域中只有一根指針指向後繼,最後一個結(jié)點的指針值未null,每個結(jié)點只能找到後繼,不能找到前驅(qū),便於插入,刪除,不便於查找單循環(huán)結(jié)構(gòu),最後一個結(jié)點的指針指向首結(jié)點,特點便於插入和刪除,尤其是在首端和尾端插入刪除更方便雙鏈結(jié)構(gòu),每個結(jié)點帶有指向前驅(qū)和指向後繼的兩個指針,優(yōu)點查找結(jié)點的前驅(qū)和後繼方便,缺點是存儲空間開銷比較大線性表的操作,主要有初始化,判空表,求表長度,查找,插入和刪除靜態(tài)數(shù)組#DefineArSize10TypedefStruct{ElemTypeelem[ArSize];Intlength;}SqList;voidinitList(sqList*L){L->length=0;}動態(tài)數(shù)組TypedefStruct{Elemtype*elem;Intlength,ArSize;}sqlist;voidinitlist(sqllist*L,intn){L->elem=(Elemtype*)malloc(n*Sizeof(Elemtype));L->ArSize=n;L->length=0;}查找時間複雜度O(1)插入O(n/2),刪除O((n-1)/2)鏈?zhǔn)酱鎯Y(jié)構(gòu)TypeDefStructNode{ElemtypeData;StructNode*next;}LNode;LNode*initLK(){Lnode*head;Head=Null;ReturnHead;}查找元素平均比較次數(shù)O((n+1)/2)查找,刪除O(1)例在非空的雙鏈錶中刪除指針P所指向的結(jié)點.P->Front->Next=P->NextP->Next->Front=P->Front在非空的雙鏈錶中指針P所指向的結(jié)點前插入一個新結(jié)點QQ->Next=PQ->Front=P->FrontP->Front->Next=QP-Front=Q2.2.3棧和隊列1.棧,是一種只能在表的某一端(首端)進(jìn)行操作的線性數(shù)據(jù)結(jié)構(gòu),棧的操作主要有進(jìn)棧和出棧.是先進(jìn)後出的(FILO)棧的存儲結(jié)構(gòu),有順序棧和鏈棧靜態(tài)數(shù)組棧#DefineSSize10TypeDefStruct{Elemtypeelem[SSize];inttop;}SqSnode;進(jìn)棧Sqsnodes;s.elem[s.top++]=e;出棧e=s.elem[--s.top]棧空s.top==0棧滿s.top=SSize動態(tài)數(shù)組棧TypeDefStruct{Elemtype*elem,*top;intSSize;}dsnode;dsnodes;進(jìn)棧*s.top++=e;出棧e=*--s.top;空棧s.top==s.elem滿棧s.top==s.elem+s.ssize鏈棧TypeDefStructnode{Elemtypedata;Structnode*Next;}lsnode;進(jìn)棧lsnode*top,*p;p=newlsnode;p->data=e;p->Next=top;top=p;出棧p=top;e=p->data;top=top->Next;delete(p);空棧top==null例算術(shù)表達(dá)式a+b*c/(d-e)-f的逆波蘭表達(dá)式:解法一:1.置空棧2.順序掃描3.a數(shù)字優(yōu)先級為0直接出棧結(jié)果a4.+優(yōu)先級為3,入棧5.b數(shù)字直接出棧結(jié)果ab6.*優(yōu)先級為5.入棧7.c數(shù)字直接出棧結(jié)果abc8./優(yōu)先級為5,棧頂元素>=當(dāng)前元素,出棧,當(dāng)前元素入棧結(jié)果abc*9.(直接入棧10.d數(shù)字直接出棧結(jié)果abc*d11.-優(yōu)先級為3,入棧12.e直接出棧結(jié)果abc*de13.)出棧,直到)結(jié)果abc*de-14.-優(yōu)先級為3,棧頂元素>=當(dāng)前元素,出棧,當(dāng)前元素入棧結(jié)果abc*de-/+15.f直接出棧結(jié)果abc*de-/+f16.掃描完畢順序輸出棧結(jié)果abc*de-/+f-解法二:後根序遍歷二叉樹:abc*de-/+f-2.隊列,隊列是一種只能在表的尾端進(jìn)行插入操作,在首端進(jìn)行刪除操作的線性數(shù)據(jù)結(jié)構(gòu),他是先進(jìn)先出的(FIFO)線性表.隊列的存儲結(jié)構(gòu),有順序隊列和循環(huán)隊列循環(huán)隊列#DefineQSize10TypeDefStruct{Elemtypeelem[QSize];intfront,rear;}sqQnode;進(jìn)隊sqqnodeQ;q.rear=(q.rear+1)%QSize;q.elem[q.rear]=e;出隊q.font=(q.font+1)%Qsize;e=q.elem[q.font];空隊q.font=q.rear;隊滿q.front=(q.rear+1)%QSize;循環(huán)鏈隊列TypeDefStructnode{Elemtypedata;Structnode*next;}lqnode;進(jìn)隊lqnode*rear,*p;p=newlqnode;p->data=e;p->next=rear->next;rear->next=p;rear=p;出隊設(shè)循環(huán)隊列Q,則當(dāng)前循環(huán)隊列中元素的個數(shù)是(q.rear-q.front+qsize)%qsize2.2.4串串,字串的定義,串是有限個字符組成的序列,子串是串中任意長度的連續(xù)字符構(gòu)成的序列.串的存儲,串的運算.模式匹配算法和kmp算法i=i–j+2;i=i–j+2;j=1;例已知主串s=’ABBABA’,子串t=’ABA’,求樸素的模式匹配算法查找子串t比較的次數(shù),答案是8,位置是42.2.5數(shù)組和廣義表數(shù)組的定義,N維數(shù)組Ab1b2b3…bn,A中的每個元素A[j1,j2…jn],1為每一維數(shù)組的下界,bi為第i維的上界數(shù)組的存儲,順序存儲(以行序為主序,以列序為主序),壓縮存儲(三角陣,對角陣),稀疏矩陣,三元組順序存儲,十字鏈錶存儲廣義表定義,廣義表(a1,a2,…an),其中ai是原子或表,求表頭head,表尾tail,求深度表的深度為括號的重數(shù).長度為外括號里逗號的個數(shù).C=(A，B)=((x，(a，b))，((x，(a，b))，y))長度是2,深度是4稀疏矩陣的三元組表示0060000030008000000005000070三元組((1,3,6),(2,2,3),(2,6,8),(4,1,5),(4,6,7))2.2.6樹和二叉樹1.二叉樹定義,二叉樹是由一個特定的結(jié)點(無前驅(qū))稱為跟結(jié)點和兩個互不相交的左子樹,右子樹組成,其中左子樹,右子樹本身是二叉樹術(shù)語結(jié)點的度,結(jié)點的後繼數(shù)葉子,度為零的結(jié)點,也稱終端結(jié)點,葉子外的結(jié)點也稱內(nèi)結(jié)點結(jié)點的層次,樹根為第一層,根的後繼為第二層,以此類推編號樹的深度,樹的最大層次數(shù),也稱樹的高度滿二叉樹,樹中每一層上的元素都達(dá)到最多的二叉樹,即i層有2i-1個元素完全二叉樹,樹中除底層h的結(jié)點外,其餘層上必須有2i-1個元素,並且底層的結(jié)點都集中在底層的左端豐滿二叉樹,樹中除底層h的結(jié)點外,其餘層上必須有2i-1個元素二叉樹的性質(zhì),二叉樹第i層上最多有2i-1個元素,深度為h的二叉樹最多有2h-1個結(jié)點,設(shè)n0,n1分別為二叉樹中度為0和度為2的結(jié)點數(shù)目,則有n0=n2+1,n個結(jié)點的二叉樹其樹的深度範(fàn)圍[log2h]+1~~n二叉樹的存儲順序存儲,舍用於完全二叉樹,結(jié)點下標(biāo)i的父結(jié)點為[i/2],二叉鏈錶,每個結(jié)點帶有指向左右孩子的兩個指針,三叉鏈錶每個結(jié)點帶有指向左右孩子和指向父結(jié)點的指針二叉樹的遍歷前序遍歷,先訪問根結(jié)點,然後前序訪問左子樹,再前序遍歷又子樹中序遍歷,先中序遍歷左子樹,然後訪問根結(jié)點,再中跟序遍歷又子樹后序遍歷,先后序遍歷左子樹,再后序遍歷又子樹,再訪問根結(jié)點線索二叉樹,當(dāng)二叉樹用二叉鏈錶存儲時,二叉鏈錶有n個結(jié)點,則存在n+1指針域為空,可以利用這些空指針域存放某種遍歷次序下的前驅(qū)和後繼結(jié)點的指針,這種二叉樹就稱為線索二叉樹前序線索二叉樹中序線索二叉樹後序線索二叉樹霍夫曼樹(Huffman),又稱最優(yōu)二叉樹,他是n個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中帶權(quán)路徑長度WPL最小的二叉樹主要用途是實現(xiàn)數(shù)據(jù)的壓縮例給出一段報文,字符集為{a,b,c,d,e,f}各字符出現(xiàn)的頻度是{45,13,12,16,9,5}若給每個字符等長編碼(a,000b,001c,010d,011e,100f,101)則總長度=3*100=300若按霍夫曼編碼((a,0b,101c,100d,111e,1101f,1100))則總長度=45*1+(13+12+16)*3+(9+5)*4=224數(shù)據(jù)壓縮率=224/300*100%=74.7%假設(shè)用於通信的電文由字元集{a,b,c,d,e,f,g,h}中的字母構(gòu)成，這8個字母在電文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}

(1)為這8個字母設(shè)計哈夫曼編碼。

霍夫曼演算法(1)由給定的n個權(quán)值{w0,w1,w2,…,wn-1}，構(gòu)造具有n棵擴(kuò)充二叉樹的森林F={T0,T1,T2,…,Tn-1}，其中每一棵擴(kuò)充二叉樹Ti只有一個帶有權(quán)值wi的根結(jié)點，其左、右子樹均為空(2)重複以下步驟,直到F中僅剩下一棵樹為止①在F中選取兩棵根結(jié)點的權(quán)值最小的擴(kuò)充二叉樹,做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和②在F中刪去這兩棵二叉樹③把新的二叉樹加入F假設(shè)用於通信的電文由字元集{a,b,c,d,e,f,g,h}中的字母構(gòu)成，這8個字母在電文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}森林F:選取最小權(quán)值的兩棵樹,構(gòu)成二叉樹并加入F重複選取最小權(quán)值的兩棵樹,構(gòu)成二叉樹并加入F重複選取最小權(quán)值的兩棵樹,構(gòu)成二叉樹并加入F重複選取最小權(quán)值的兩棵樹,構(gòu)成二叉樹并加入F重複選取最小權(quán)值的兩棵樹,構(gòu)成二叉樹并加入F重複選取最小權(quán)值的兩棵樹,構(gòu)成二叉樹并加入F,直到F剩下一棵樹為止2.樹和森林樹是由一個特定的結(jié)點(無前驅(qū))稱為跟和m個互不相交的子樹組成,當(dāng)m=0時稱為空數(shù)樹的存儲,樹的遍歷(前跟序遍歷,后跟序遍歷)樹與二叉樹的轉(zhuǎn)換,樹用孩子兄弟法表示即為二叉樹森林,是樹的集合,將每棵樹的根看成兄弟關(guān)係,用數(shù)的孩子兄弟法表示,即為二叉樹2.2.7圖1.圖的定義圖G=(V,E),其中V是頂點的有窮非空集合,E是V中頂點的序偶組成的有窮集,這些序偶稱為邊2.基本術(shù)語鄰接點,若存在一條邊<Vi,Vj>,則再無向圖中稱Vi和Vj互為鄰接點,在有向圖中稱Vj是Vi的鄰接點完全圖,圖G中任意兩點都鄰接,無向完全圖有n(n-1)/2條邊,有向完全圖有n(n-1)條邊邊n=6,頂點V=4,所有接點的度之和為12度,入度和出度,無向圖中頂點V依附(關(guān)聯(lián))的邊數(shù)稱為V的度,對於有向圖分為入度和出度,V的入度之指邊的箭頭指向V的入邊數(shù)目,V的出度是箭頭離開V的出邊數(shù)目,圖中所有接點度數(shù)之和等於圖邊數(shù)的兩倍連通和連通圖,在無向圖中,Vi到Vj有路徑,則稱Vi和Vj時連通的,若圖G中任意兩個頂點都是連通的則稱G是連通圖連通分量,無向圖G中的極大連通子圖稱為圖G的連通分量強(qiáng)連通圖和強(qiáng)連通分量,在有向圖中,如任意兩個頂點Vi和Vj都連通,即Vi和Vj存在路徑,從Vj到Vi也存在路徑,則稱為強(qiáng)連通圖,有向圖G中的極大強(qiáng)連同子圖稱為G的強(qiáng)連通分量網(wǎng),邊帶權(quán)的圖,也稱帶權(quán)圖生成樹,連通圖G有N個頂點,取G中n個頂點,取連接n個頂點的n-1條邊所得的子圖稱為G的生成樹3.圖的存儲結(jié)構(gòu)鄰接矩陣,設(shè)圖G=(V,E)有n個頂點,則G的鄰接矩是一個n階方陣A[i][j]=1(有邊)0(無邊)鄰接鏈錶,把圖的每個頂點Vi建立一個單鏈錶,把與Vi相鄰接的頂點放在一個鏈錶中4.圖的遍歷深度優(yōu)先DFS,首先訪問指定的起始頂點V,然後選取與V鄰接的未被訪問的任意一個接點w訪問之,再選取與w鄰接的未被訪問的任意一接點訪問之,重複進(jìn)行如上訪問,當(dāng)達(dá)到一個所有鄰接點都被訪問過時,則依次退回到最近被訪問過的接點,若他有鄰接未被訪問,從這些未被訪問的接點中選取一個頂點,重複開始訪問過程,直到所有頂點都被訪問為止結(jié)果:125436aabcdefgh結(jié)果:abdhefcg廣度優(yōu)先(BFS),首先選取指定的起始頂點V,然後選取與V鄰接的全部頂點w1,w2…wt再依次訪問與w1,w2…wt鄰接的未被訪問的頂點,直到全部訪問ababcdefgh結(jié)果:124536結(jié)果:abfcdehg5.最小生成樹,在圖中所有生成樹權(quán)最小的樹Prim算法從0開始,選取權(quán)最小的與2相連權(quán)值最小的與5相連權(quán)值最小的不能產(chǎn)生回路,所以回走,選擇與2相連的權(quán)值最小的再選擇與1相連的權(quán)值最小的接點Kruskal算法選取圖中權(quán)最小的選取圖中權(quán)最小的選取圖中權(quán)最小的選取圖中權(quán)最小的選取圖中權(quán)最小的Prim算法時間複雜度O(N^2)適合稠密度,Kruskal時間複雜度O(elog2e)適合稀疏圖6.拓?fù)渑判?就是對一個有向無環(huán)圖(AOV)中的各點排成一個具有前後次序的線性序列,方法,找到無前驅(qū)(入度為零)的頂點輸出并將其每個後繼頂點的前驅(qū)數(shù)(入度)減一,值到所有頂點都輸出V1,2,3,5,4,67.關(guān)鍵路徑,帶權(quán)有向圖(AOE)中從源點(表示工程的開始)到匯點(表示工程的結(jié)束)的長度最長的路徑稱為關(guān)鍵路徑V1,3,4,68.最短路徑,Dijkstra算法Dijkstra算法1.從V1開始,與V1相連的路徑V1~V2=====3V1~V3=====2選取最短路徑V1~V3中的V3做起點,V1~V3=====2V1~V2=====3V1~V3~V4=====6V1~V3~V6=====5選取最短路徑V1~V2=====3中的V2做起點V1~V3~V4=====6V1~V3~V6=====5V1~V2~V5======6V1~V2~V4======5選取最短路徑V1~V2~V4中的V4左起點V1~V3~V4=====6V1~V3~V6=====5V1~V2~V5======6V1~V2~V4~V6======7得到最短的路徑為{V1~V2=3V1~V3=2V1~V2~V4=5V1~V2~V5=6V1~V3~V6=5}2.2.8查找1.查找概念查找表,同一數(shù)據(jù)類型的元素構(gòu)成的集合靜態(tài)查找表,在查找操作時不對查找表的長度進(jìn)行修改動態(tài)查找表,是在查找過程中動態(tài)生成的,即查找時若所找元素不存在則插入平均查找長度ASL(AverageSearchLength)ASL=∑PiCi2.靜態(tài)查找表上的查找方法順序查找,待查找元素依次與查找表中的元素比較,ASL=O(n)二分查找,待查找元素與查找表中間的元素比較,若小,則在前半段中用同樣的方法查找,若大,則在后半段用同樣的方法查找,ASL=O(Log2N)分塊查找,當(dāng)查找表局部有序時,將查找表分成如干塊,塊內(nèi)元素不一定有序,對塊建立索引,索引是按關(guān)鍵字有序的,查找方法是先順序查找塊,再順序查找塊內(nèi)元素.當(dāng)塊長為n時,最小的ASL=O(Sqr(n))3.動態(tài)查找表的查找⑴二叉排序數(shù)非空二叉樹中的任意結(jié)點A,若K有左子樹,則左子樹中的每個結(jié)點的值都小於K,若K有右結(jié)點,則右子樹中的所有結(jié)點的值都大於等於K的值,中序遍歷二叉樹得到升序序列插入2刪除15⑵平衡二叉樹(AVL)非空的平衡二叉樹中的任意結(jié)點K,K的左子樹和右子樹的深度之差絕對值不超過1設(shè)有關(guān)鍵碼序列{20,35,40,15,30,25,38}，圖7-3給出了平衡二叉樹樹的構(gòu)造過程，結(jié)點旁邊標(biāo)出的是該結(jié)點的平衡因數(shù).平衡因子等於該結(jié)點左子樹與右子樹之差⑶B-樹⑷哈希表及其查找哈希表,設(shè)哈希函數(shù)H(Key),結(jié)點的存儲方法為H(關(guān)鍵字)=存儲位置.按這種方法得到的存儲結(jié)構(gòu)圖稱為哈希表解決哈希衝突的方法:當(dāng)哈希函數(shù)不是一對一時則產(chǎn)生衝突開放地址法Hi=(H(key)+di)Modm其中,M為哈希表的長度,Di為曾量當(dāng)Di=1,2,3…M-1時,稱為線性探測再散列當(dāng)Di=1^2,-1^,2^2,-2^2….±K^2時,稱為二次探測再散列鏈地址法練習(xí)1.已知關(guān)鍵字序列4,7,9,10,15,21,33,48,52,61,3,1.寫出用二分查找方法查找關(guān)鍵字52的比較次數(shù)和等概率的平均查找長度構(gòu)造平衡二叉樹1.RR型2.RR型3.RL型4.RL型5.RL型6.RL型7.LL型2.2.9排序1.排序的概念排序,將無序序列調(diào)整為有序序列穩(wěn)定性,若待排序記錄有相同關(guān)鍵字,排序后相同關(guān)鍵字的相對位置發(fā)生變化,則稱該排序算法不穩(wěn)定,否則為穩(wěn)定內(nèi)部排序,指帶排序記錄全部存放在內(nèi)存中排序的排序過程外部排序,在排序過程中,需對外存進(jìn)行訪問的排序過程2.簡單排序(1)直接插入排序基本思想,將無序的序列中從第二個開始的每個元素依次插入到有序序列,當(dāng)序列有n個元素時,則進(jìn)行n-1次插入C語言描述voidinsertsort(intr[],intn){inti,j;for(i=2;i<=n;i++){if(r[i]<r[i-1]){r[0]=r[i];j=i-1;do{r[j+1]=r[j];j--;}while(r[0]<r[j]);r[j+1]=r[0];}}}VBA描述PublicSubInsertSort()DimArr(10)AsIntegerFori=1To10Arr(i)=Int(Rnd()*100)Cells(i,1).Value=Arr(i)NextFori=2To10IfArr(i)<Arr(i-1)ThenTmp=Arr(i)j=iDoTmp=Arr(j)Arr(j)=Arr(j-1)Arr(j-1)=Tmpj=j-1LoopWhileTmp<Arr(j-1)EndIfNextiFori=1To10Cells(i,2).Value=Arr(i)NextEndSub時間複雜度O(n^2)(2)冒泡排序基本思想,小的往上冒方法,從無序序列的最後元素開始往前兩兩比較,第一次冒出最小的元素,第二次在剩餘的序列中冒出第二小的,這樣共要冒出n-1個元素C語言描述VoidBubbleSort(intr[],intn){inti,j,tag,tmp;for(i=0;i<n-1;i--){tag=0;for(j=n-1;j=i+1;j--){if(r[j]<r[j-1]){tmp=r[j];r[j]=r[j-1];r[j-1]=tmp;tag=1;}if(tag==0)break;}}}VBA語言描述PublicSubBubbleSort()DimArr(10)AsIntegerFori=1To10Arr(i)=Int(Rnd()*100)Cells(i,1).Value=Arr(i)NextFori=1To10flag=0Forj=10Toi+1Step-1IfArr(j)<Arr(j-1)Thentmp=Arr(j)Arr(j)=Arr(j-1)Arr(j-1)=tmpflag=1EndIfNextjIfflag=0ThenExitForEndIfNextiFori=1To10Cells(i,2).Value=Arr(i)NextEndSub時間複雜度O(n^2)(3)簡單選擇排序基本思想,第一次從無序序列中選出第一小的元素,然後從剩下的序列中選出第二小的元素,這樣共選出n-1小的數(shù)C語言描述VoidSelectSort(intr[],intn){inti,jk,tmp;for(i=0;i<=n-1;i++){k=i;for(j=i+1;j<n;j++){if(r[j]<r[k])k=j;}if(i!=k){tmp=r[i];r[i]=r[k];r[k]=tmp;}}}VBA語言描述PublicSubSelectSort()DimArr(10)AsIntegerFori=1To10Arr(i)=Int(Rnd()*100)Cells(i,1).Value=Arr(i)NextFori=1To10k=iForj=i+1To10IfArr(j)<Arr(k)Thenk=jEndIfNextjIfi<>kThentmp=Arr(i)Arr(i)=Arr(k)Arr(k)=tmpEndIfNextiFori=1To10Cells(i,2).Value=Arr(i)NextEndSub時間複雜度O(n^2),不穩(wěn)定排序算法3.先進(jìn)排序(1)希爾排序基本思想,先將整個待排序列分割成若干子序列,然後對各個子序列分別進(jìn)行直接插入排序PublicSubShellSort()DimArr(10)AsIntegerFori=1To10Arr(i)=Int(Rnd()*100)Cells(i,1).Value=Arr(i)Nexth=5DoWhileh>0Fori=hTo10IfArr(i)<Arr(i-1)Thentmp=Arr(i)j=iDotmp=Arr(j)Arr(j)=Arr(j-1)Arr(j-1)=tmpj=j-1LoopWhiletmp<Arr(j-1)EndIfNextih=h-2LoopFori=1To10Cells(i,2).Value=Arr(i)NextEndSub不穩(wěn)定,時間複雜度O(nlog2n)(2)快速排序基本思想,選取第一個結(jié)點,以它的關(guān)鍵字和序列中所有其他關(guān)鍵字比較,小的放前面,大的放後面,然後分別對這兩部份重複上述過程,直到?jīng)]部份只剩一個結(jié)點為止PublicSubKuaisu()DimArr(10)AsIntegerFori=1To10Arr(i)=Int(Rnd()*100)Cells(i,1).Value=Arr(i)NextCallKuaisusort(Arr(),1,10)Fori=1To10Cells(i,2).Value=Arr(i)NextEndSubPublicFunctionPartition(Tarr()AsInteger,LeftAsInteger,RightAsInteger)AsIntegerPivot=Tarr(Left)low=LeftHight=RightDoWhile(low<>Hight)IfTarr(Hight)>PivotThenHight=Hight-1ElseIfTarr(low)<=PivotThenlow=low+1ElseTmp=Tarr(low)Tarr(low)=Tarr(Hight)Tarr(Hight)=TmpEndIfLoopTarr(Left)=Tarr(low)Tarr(low)=PivotPartition=lowEndFunctionPublicSubKuaisusort(Tarr()AsInteger,LeftAsInteger,RightAsInteger)IfLeft<RightThenPt=Partition(Tarr(),Left,Right)CallKuaisusort(Tarr(),Left,Pt-1)CallKuaisusort(Tarr(),Pt+1,Right)EndIfEndSub不穩(wěn)定,時間複雜度O(nlog2n)(3)堆排序堆的定義,n個元素的序列{k1,k2,…,kn}當(dāng)且僅當(dāng)所有關(guān)鍵字都滿足下列關(guān)係時稱為堆,ki<=k2iandki<=k2i+1(小跟堆),其中i<=1<=n/2基本思想,建堆VBA描述PublicSubDuiSort()DimArr(10)AsIntegerFori=1To10Arr(i)=Int(Rnd()*100)Cells(i,1).Value=Arr(i)Nextj=10DoWhilej>0Fori=(j\2)To1Step-1m=2*in=2*i+1Ifn<jThenIfArr(i)<Arr(n)Thentmp=Arr(i)Arr(i)=Arr(n)Arr(n)=tmpEndIfEndIfIfArr(i)<Arr(m)Thentmp=Arr(i)Arr(i)=Arr(m)Arr(m)=tmpEndIfNexttmp=Arr(j)Arr(j)=Arr(1)Arr(1)=tmpj=j-1LoopFori=1To10Cells(i,2).Value=Arr(i)NextEndSub不穩(wěn)定,時間複雜度O(nlog2n)(4)并歸排序基本思想,將兩個或多個有序序列合併成一個新的有序序列(5)基數(shù)排序基本思想,4.外排序2.2.10常見算法設(shè)計方法1.分治法基本思想,將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題,這些子問題互相獨立且與原問題相同,遞歸地解決這些子問題,然後將各個子問題的解合併得到原來問題的解二分查找,快速排序就是典型的例子2.遞推法基本思想,在n=1時能方便得到解,當(dāng)?shù)玫絾栴}規(guī)模為i-1的解后,由問題的遞推性質(zhì)能從已求的規(guī)模為1,2,3…i-1的一系列解構(gòu)造出問題為i的解F(n)=1n<=2F(n-1)+F(n-2)n>2VBA語言描述PublicFunctionFibonacci(AAsInteger)AsIntegerIfA<=2ThenRst=1El