1、常考基礎必知必會A. 排序： 排序有幾種，各種排序的比較，哪些排序是穩定的，快排的算法; B. 查找：哈希查找、二叉樹查找、折半查找的對比，哈希映射和哈希表的區別?C. 鏈表和數組的區別，在什么情況下用鏈表什么情況下用數組?D. 棧和隊列的區別?E. 多態，舉例說明;overload和override的區別?F. 字符串有關的函數，比如讓你寫一個拷貝字符串的函數啊，或者字符串反轉啊什么的。strcpy和memcpy?G. 繼承、多繼承?H. 面向對象有什么好處?I. 說說static的與眾不同之處，如果一個變量被聲明為static，它會被分配在哪里?在什么時候分配空間等?J. 什么是虛函數、純

2、虛函數、虛的析構函數，用途?K. 內存泄漏及解決方法?網絡部分：OSI模型7層結構，TCP/IP模型結構?B. TCP/UDP區別?C. TCP建立連接的步驟?D. 香農定理?二叉樹三種遍歷的非遞歸算法(背誦版)1.先序遍歷非遞歸算法#define maxsize 100typedef struct Bitree Elemmaxsize; int top;SqStack;void PreOrderUnrec(Bitree t) SqStack s; StackInit(s); p=t; while (p!=null | !StackEmpty(s) while (p!=null) /遍歷左子樹

3、 visite(p-data); push(s,p); p=p-lchild; /endwhile if (!StackEmpty(s) /通過下一次循環中的內嵌while實現右子樹遍歷 p=pop(s); p=p-rchild; /endif /endwhile /PreOrderUnrec2.中序遍歷非遞歸算法#define maxsize 100typedef struct Bitree Elemmaxsize; int top;SqStack;void InOrderUnrec(Bitree t) SqStack s; StackInit(s); p=t; while (p!=null

4、 | !StackEmpty(s) while (p!=null) /遍歷左子樹 push(s,p); p=p-lchild; /endwhile if (!StackEmpty(s) p=pop(s); visite(p-data); /訪問根結點 p=p-rchild; /通過下一次循環實現右子樹遍歷 /endif /endwhile/InOrderUnrec3.后序遍歷非遞歸算法#define maxsize 100typedef enumL,R tagtype;typedef struct Bitree ptr; tagtype tag;stacknode;typedef struct

5、 stacknode Elemmaxsize; int top;SqStack;/后序遍歷void PostOrderUnrec(Bitree t) SqStack s; stacknode x; StackInit(s); p=t; do while (p!=null) /遍歷左子樹 x.ptr = p; x.tag = L; /標記為左子樹 push(s,x); p=p-lchild; while (!StackEmpty(s) &s.Elems.top.tag=R) x = pop(s); p = x.ptr; visite(p-data); /tag為R，表示右子樹訪問完畢，故訪問根結

6、點 if (!StackEmpty(s) s.Elems.top.tag =R; /遍歷右子樹 p=s.Elems.top.ptr-rchild; while (!StackEmpty(s);/PostOrderUnrec3.后序遍歷非遞歸算法#define maxsize 100typedef enumL,R tagtype;typedef struct Bitree ptr; tagtype tag;stacknode;typedef struct stacknode Elemmaxsize; int top;SqStack;/后序遍歷void PostOrderUnrec(Bitree

7、t) SqStack s; stacknode x; StackInit(s); p=t; do while (p!=null) /遍歷左子樹 x.ptr = p; x.tag = L; /標記為左子樹 push(s,x); p=p-lchild; while (!StackEmpty(s) &s.Elems.top.tag=R) x = pop(s); p = x.ptr; visite(p-data); /tag為R，表示右子樹訪問完畢，故訪問根結點 if (!StackEmpty(s) s.Elems.top.tag =R; /遍歷右子樹 p=s.Elems.top.ptr-rchild

8、; while (!StackEmpty(s);/PostOrderUnrec2、線性表(1) 性表的鏈式存儲方式及以下幾種常用鏈表的特點和運算：單鏈表、循環鏈表，雙向鏈表，雙向循環鏈表。(2)單鏈表的歸并算法、循環鏈表的歸并算法、雙向鏈表及雙向循環鏈表的插入和刪除算法等都是較為常見的考查方式。(3)單鏈表中設置頭指針、循環鏈表中設置尾指針而不設置頭指針以及索引存儲結構的各自好處。3、棧與隊列你可以問一下自己是不是已經知道了以下幾點：(1)棧、隊列的定義及其相關數據結構的概念，包括：順序棧，鏈棧，共享棧，循環隊列，鏈隊等。棧與隊列存取數據(請注意包括：存和取兩部分)的特點。(2)遞歸算法。棧與

9、遞歸的關系，以及借助棧將遞歸轉向于非遞歸的經典算法：n!階乘問題，fib數列問題，hanoi問題，背包問題，二叉樹的遞歸和非遞歸遍歷問題，圖的深度遍歷與棧的關系等。其中，涉及到樹與圖的問題，多半會在樹與圖的相關章節中進行考查。(3)棧的應用：數值表達式的求解，括號的配對等的原理，只作原理性了解，具體要求考查此為題目的算法設計題不多。(4)循環隊列中判隊空、隊滿條件，循環隊列中入隊與出隊(循環隊列在插入時也要判斷其是否已滿，刪除時要判斷其是否已空)算法。【循環隊列的隊空隊滿條件為了方便起見，約定：初始化建空隊時，令front=rear=0,當隊空時：front=rear，當隊滿時：front=r

10、ear 亦成立，因此只憑等式front=rear無法判斷隊空還是隊滿。有兩種方法處理上述問題：(1)另設一個標志位以區別隊列是空還是滿。(2)少用一個元素空間，約定以“隊列頭指針front在隊尾指針rear的下一個位置上”作為隊列“滿”狀態的標志。隊空時： front=rear，隊滿時： (rear+1)%maxsize=front】如果你已經對上面的幾點了如指掌，棧與隊列一章可以不看書了。注意，我說的是可以不看書，并不是可以不作題哦。循環隊列的主要操作：(1)創建循環隊列(2)初始化循環隊列(3)判斷循環隊列是否為空(4)判斷循環隊列是否為滿(5)入隊、出隊/空出頭尾之間的一個元素不用#in

11、clude#include#define MAXSIZE 100typedef structintelemMAXSIZE;intfront, rear;Quque; /定義隊頭int initQue(Quque *q) /初始化(*q)-front=0;(*q)-rear=0;int isFull(Quque *q)if(q-front=(q-rear+1)%MAXSIZE)/判滿(空出一個元素不用) 劉勉剛return 1;elsereturn 0;int insertQue(Quque *q,int elem)if(isFull(*q)return -1;(*q)-elem(*q)-rea

12、r=elem;(*q)-rear=(*q)-rear+1)%MAXSIZE;/插入return0;int isEmpty(Quque *q)if(q-front=q-rear)/判空return 1;elsereturn 0;int deleteQue(Quque * q,int *pelem)if(isEmpty(*q)return 0;*pelem=(*q)-elem(*q)-front;(*q)-front=(*q)-front +1)%MAXSIZE;return0;4、串串一章需要攻破的主要堡壘有：1. 串的基本概念，串與線性表的關系(串是其元素均為字符型數據的特殊線性表)，空串與空

13、格串的區別，串相等的條件;2. 串的基本操作，以及這些基本函數的使用，包括：取子串，串連接，串替換，求串長等等。運用串的基本操作去完成特定的算法是很多學校在基本操作上的考查重點。3. 順序串與鏈串及塊鏈串的區別和聯系，實現方式。4. KMP算法思想。KMP中next數組以及nextval數組的求法。明確傳統模式匹配算法的不足，明確next數組需要改進。可能進行的考查方式是：求next和nextval數組值，根據求得的next或nextval數組值給出運用KMP算法進行匹配的匹配過程。5、多維數組和廣義表矩陣包括：對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式：三元

14、組，帶輔助行向量的二元組，十字鏈表存儲。掌握將稀疏矩陣的三元組或二元組向十字鏈表進行轉換的算法。6、樹與二叉樹樹一章的知識點包括：二叉樹的概念、性質和存儲結構，二叉樹遍歷的三種算法(遞歸與非遞歸)，在三種基本遍歷算法的基礎上實現二叉樹的其它算法，線索二叉樹的概念和線索化算法以及線索化后的查找算法，最優二叉樹的概念、構成和應用，樹的概念和存儲形式，樹與森林的遍歷算法及其與二叉樹遍歷算法的聯系，樹與森林和二叉樹的轉換。(1) 二叉樹的概念、性質和存儲結構考查方法可有：直接考查二叉樹的定義，讓你說明二叉樹與普通雙分支樹(左右子樹無序)的區別;考查滿二叉樹和完全二叉樹的性質，普通二叉樹的五個性質：A.

15、第i層的最多結點數，B.深度為k的二叉樹的最多結點數，C.n0=n2+1的性質，D.n個結點的完全二叉樹的深度，E. 順序存儲二叉樹時孩子結點與父結點之間的換算關系(root從1開始，則左為：2*i，右為：2*i+1)。二叉樹的順序存儲和二叉鏈表存儲的各自優缺點及適用場合，二叉樹的三叉鏈表表示方法。(2) 二叉樹的三種遍歷算法這一知識點掌握的好壞，將直接關系到樹一章的算法能否理解，進而關系到樹一章的算法設計題能否順利完成。二叉樹的遍歷算法有三種：先序，中序和后序。其劃分的依據是視其每個算法中對根結點數據的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸算法，理解其執行的實際步驟，并且應該熟練掌握三種

16、遍歷的非遞歸算法。由于二叉樹一章的很多算法，可以直接根據三種遞歸算法改造而來(比如：求葉子個數)，所以，掌握了三種遍歷的非遞歸算法后，對付諸如：“利用非遞歸算法求二叉樹葉子個數”這樣的題目就下筆如有神了。(3) 可在三種遍歷算法的基礎上改造完成的其它二叉樹算法：求葉子個數，求二叉樹結點總數，求度為1或度為2的結點總數，復制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結點，刪除值為n的某個指定結點，諸如此類等等等等。如果你可以熟練掌握二叉樹的遞歸和非遞歸遍歷算法，那么解決以上問題就是小菜一碟了。(4) 線索二叉樹：線索二叉樹的引出，是為避免如二叉樹遍歷時的遞歸求解。眾所周知，遞歸雖然形

17、式上比較好理解，但是消耗了大量的內存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險，為了避免此類情況，線索二叉樹便堂而皇之地出現了。對于線索二叉樹，應該掌握：線索化的實質，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題(如：查找某一類線索二叉樹中指定結點的前驅或后繼結點就是一類常考題)。(5) 最優二叉樹(哈夫曼樹)：最優二叉樹是為了解決特定問題引出的特殊二叉樹結構，它的前提是給二叉樹的每條邊賦予了權值，這樣形成的二叉樹按權相加之和是最小的。最優二叉樹一節，直接考查算法源碼的很少，一般是給你一組數據，要求你建立基于這組數據的最優二叉樹，并求出其最小權值之和，此類題目不

18、難，屬送分題。(6) 樹與森林：二叉樹是一種特殊的樹，這種特殊不僅僅在于其分支最多為2以及其它特征，一個最重要的特殊之處是在于：二叉樹是有序的!即：二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹。 樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷算法：先根與后根(對于森林而言稱作：先序與后序遍歷)。此二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應關系的：先根遍歷對應二叉樹的先序遍歷，而后根遍歷對應二叉樹的中序遍歷。二叉樹、樹與森林之所以能有以上的對應關系，全拜二叉鏈表所賜。二叉樹使用二叉鏈表分別存放他的左右孩子，樹利用二叉鏈表存儲孩子及兄弟(稱孩子兄弟鏈表)，而森林也是利用

19、二叉鏈表存儲孩子及兄弟。7、圖1. 圖的基本概念：圖的定義和特點，無向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長度，回路，(強)連通圖，(強)連通分量等概念。2. 圖的幾種存儲形式：鄰接矩陣，(逆)鄰接表，十字鏈表及鄰接多重表。在考查時，有的學校是給出一種存儲形式，要求考生用算法或手寫出與給定的結構相對應的該圖的另一種存儲形式。3. 考查圖的兩種遍歷算法：深度遍歷和廣度遍歷深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，這兩個算法對圖一章的重要性等同于“先序、中序、后序遍歷”對于二叉樹一章的重要性。在考查時，圖一章的算法設計題常常是基于這兩種基本的遍歷算法而設計的，比如：“求最長的最短路徑問

20、題”和“判斷兩頂點間是否存在長為K的簡單路徑問題”，就分別用到了廣度遍歷和深度遍歷算法。4. 生成樹、最小生成樹的概念以及最小生成樹的構造：PRIM算法和KRUSKAL算法。考查時，一般不要求寫出算法源碼，而是要求根據這兩種最小生成樹的算法思想寫出其構造過程及最終生成的最小生成樹。5. 拓撲排序問題：拓撲排序有兩種方法，一是無前趨的頂點優先算法，二是無后繼的頂點優先算法。換句話說，一種是“從前向后”的排序，一種是“從后向前”排。當然，后一種排序出來的結果是“逆拓撲有序”的。6. 關鍵路徑問題：這個問題是圖一章的難點問題。理解關鍵路徑的關鍵有三個方面：一是何謂關鍵路徑;二是最早時間是什么意思、如

21、何求;三是最晚時間是什么意思、如何求。簡單地說，最早時間是通過“從前向后”的方法求的，而最晚時間是通過“從后向前”的方法求解的，并且，要想求最晚時間必須是在所有的最早時間都已經求出來之后才能進行。在實際設計關鍵路徑的算法時，還應該注意以下這一點：采用鄰接表的存儲結構，求最早時間和最晚時間要采用不同的處理方法，即：在算法初始時，應該首先將所有頂點的最早時間全部置為0。關鍵路徑問題是工程進度控制的重要方法，具有很強的實用性。7. 最短路徑問題：與關鍵路徑問題并稱為圖一章的兩只攔路虎。概念理解是比較容易的，關鍵是算法的理解。最短路徑問題分為兩種：一是求從某一點出發到其余各點的最短路徑(單源最短路徑)

22、;二是求圖中每一對頂點之間的最短路徑。這個問題也具有非常實用的背景特色，一個典型的應該就是旅游景點及旅游路線的選擇問題。解決第一個問題用DIJSKTRA算法，解決第二個問題用FLOYD算法，注意區分。8、查找(search)先弄清楚以下幾個概念：關鍵字、主關鍵字、次關鍵字的含義;靜態查找與動態查找的含義及區別;平均查找長度ASL的概念及在各種查找算法中的計算方法和計算結果，特別是一些典型結構的ASL值，應該記住。一般將search分為三類：在順序表上的查找;在樹表上的查找;在哈希表上的查找。(1) 線性表上的查找：主要分為三種線性結構：順序表傳統查找方法：逐個比較;有序順序表二分查找法(注意適

23、用條件以及其遞歸實現方法);索引順序表對索引結構，采用索引查找算法。注意這三種表下的ASL值以及三種算法的實現。(2) 樹表上的查找：樹表主要分為以下幾種：二叉排序樹(即二叉查找樹)，平衡二叉查找樹(AVL樹)，B樹，鍵樹。其中，尤以前兩種結構為重，也有部分名校偏愛考B樹的。由于二叉排序樹與平衡二叉樹是一種特殊的二叉樹。二叉排序樹，簡言之，就是“左小右大”，它的中序遍歷結果是一個遞增的有序序列。平衡二叉排序樹是二叉排序樹的優化，其本質也是一種二叉排序樹，只不過，平衡排序二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大于1。對于二叉排序樹，“判斷某棵二叉樹是否二叉排序樹”這一算法經常被考到

24、，可用遞歸，也可以用非遞歸。平衡二叉樹的建立也是一個常考點，但該知識點歸根結底還是關注的平衡二叉樹的四種調整算法，調整的一個參照是：調整前后的中序遍歷結果相同。B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉.排序樹。除B樹的查找算法外，應該特別注意一下B樹的插入和刪除算法，因為這兩種算法涉及到B樹結點的分裂和合并，是一個難點。 鍵樹(keywordtree)，又稱數字搜索樹(digitalsearch tree)或字符樹。trie樹也可說等同于鍵樹或屬于鍵樹的一種。鍵樹特別適用于查找英文單詞的場合。一般不要求能完整描述算法源碼，多是根據算法思想建立鍵樹及描述其大致查找過程。(3)

25、基于哈希表的查找算法：哈希譯自“hash”一詞，意為“散列”或“雜湊”。哈希表查找的基本思想是：根據當前待查找數據的特征，以記錄關鍵字為自變量，設計一個function，該函數對關鍵字進行轉換后，其解釋結果為待查的地址。基于哈希表的考查點有：哈希函數的設計，沖突解決方法的選擇及沖突處理過程的描述。9、內部排序考查你對書本上的各種排序算法及其思想以及其優缺點和性能指標(時間復雜度)能否了如指掌。排序方法分類有：插入、選擇、交換、歸并、計數等五種排序方法。(1)插入排序中又可分為：直接插入、折半插入、2路插入(?)、希爾排序。這幾種插入排序算法的最根本的不同點，說到底就是根據什么規則尋找新元素的插

26、入點。直接插入是依次尋找，折半插入是折半尋找，希爾排序，是通過控制每次參與排序的數的總范圍“由小到大”的增量來實現排序效率提高的目的。(2)交換排序，又稱冒泡排序，在交換排序的基礎上改進又可以得到快速排序。快速排序的思想，一語以敝之：用中間數將待排數據組一分為二。(3)選擇排序可以分為：簡單選擇、樹選擇、堆排序。選擇排序相對于前面幾種排序算法來說，難度大一點。這三種方法的不同點是，根據什么規則選取最小的數。簡單選擇，是通過簡單的數組遍歷方案確定最小數;樹選擇，是通過“錦標賽”類似的思想，讓兩數相比，不斷淘汰較大(小)者，最終選出最小(大)數;而堆排序，是利用堆這種數據結構的性質，通過堆元素的刪

27、除、調整等一系列操作將最小數選出放在堆頂。堆排序中的堆建立、堆調整是重要考點。(4)歸并排序，是通過“歸并”這種操作完成排序的目的，既然是歸并就必須是兩者以上的數據集合才可能實現歸并。所以，在歸并排序中，關注最多的就是2路歸并。算法思想比較簡單，有一點，要銘記在心：歸并排序是穩定排序。(5)基數排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數排序就比較適合于一些特別的場合，比如撲克牌排序問題等。基數排序，又分為兩種：多關鍵字的排序(撲克牌排序)，鏈式排序(整數排序)。基數排序的核心思想也是利用“基數空間”這個概念將問題規模規范、變小，并且，在排序的過程中，只要按照基排的思想，是不用

28、進行關鍵字比較的，這樣得出的最終序列就是一個有序序列。本章各種排序算法的思想以及偽代碼實現，及其時間復雜度都是必須掌握的。/穩定性分析/排序算法的穩定性，通俗地講就是能保證排序前2個相等的數其在序列的前后位置順序和排序后它們兩個的前后位置順序相同。穩定性的好處：若排序算法如果是穩定的，那么從一個鍵上排序，然后再從另一個鍵上排序，第一個鍵排序的結果可以為第二個鍵排序所用。基數排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。另外，如果排序算法穩定，對基于比較的排序算法而言，元素交換的次數可能會少一些(個人感覺，沒有證實)。分析一下常見的排序算法的穩定性，

29、每個都給出簡單的理由。(1) 冒泡排序冒泡排序就是把小的元素往前調或者把大的元素往后調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的;如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩定排序算法。(2) 選擇排序選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果當前元素比一

30、個元素小，而該小的元素又出現在一個和當前元素相等的元素后面，那么交換后穩定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中2個5的相對前后順序就被破壞了，所以選擇排序不是一個穩定的排序算法。(3) 插入排序插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素

31、的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定的。(4) 快速排序快速排序有兩個方向，左邊的i下標一直往右走，當ai acenter_index。如果i和j都走不動了，i j。交換aj和acenter_index，完成一趟快速排序。在中樞元素和aj交換的時候，很有可能把前面的元素的穩定性打亂，比如序列為 5 3 3 4 3 8 9 10 11，現在中樞元素5和3(第5個元素，下標從1開始計)交換就會把元素3的穩定性打亂，所以快速排序是一個不穩定的排序算法，不穩定發生在中樞元素和 aj 交換的時刻。(5) 歸并排序歸并排序是把序列遞歸地分成

32、短序列，遞歸出口是短序列只有1個元素(認為直接有序)或者2個序列(1次比較和交換),然后把各個有序的段序列合并成一個有序的長序列，不斷合并直到原序列全部排好序。可以發現，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也沒有人故意交換，這不會破壞穩定性。那么，在短的有序序列合并的過程中，穩定是是否受到破壞?沒有，合并過程中我們可以保證如果兩個當前元素相等時，我們把處在前面的序列的元素保存在結果序列的前面，這樣就保證了穩定性。所以，歸并排序也是穩定的排序算法。(6) 基數排序基數排序是按照低位先排序，然后收集;再按照高位排序，然后再收集;依次類推，直到最高位。有時候有些屬性是有優先級順

33、序的，先按低優先級排序，再按高優先級排序，最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。基數排序基于分別排序，分別收集，所以其是穩定的排序算法。(7) 希爾排序(shell)希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快;當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。所以，希爾排序的時間復雜度會比o(n2)好一些。由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩定性就會被打亂，所以shell排序是

34、不穩定的。(8) 堆排序我們知道堆的結構是節點i的孩子為2*i和2*i+1節點，大頂堆要求父節點大于等于其2個子節點，小頂堆要求父節點小于等于其2個子節點。在一個長為n 的序列，堆排序的過程是從第n/2開始和其子節點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩定性。但當為n /2-1, n/2-2, .1這些個父節點選擇元素時，就會破壞穩定性。有可能第n/2個父節點交換把后面一個元素交換過去了，而第n/2-1個父節點把后面一個相同的元素沒有交換，那么這2個相同的元素之間的穩定性就被破壞了。所以，堆排序不是穩定的排序算法。冒泡排序 插入排序 二路插入排序 希爾

35、排序 快速排序 選擇排序 歸并排序 堆排序算法的C/C+實現#include using namespace std;/交換兩個數的值void swap(int &a,int &b)int tmp;tmp=a;a=b;b=tmp;/屏幕輸出數組void display(int array,int len)coutthe resultis:ENDL; for (int i = 0 ;i len;i+ )coutARRAYI p ?; 重者在下為止。時間復雜度 o(n2)空間復雜度 o(1)比較次數 n(n+1)/2*/void bubble_sort(int array,int len)for

36、(int i = len-1 ;i = 0;i- )for(int j = 0;j arrayj+1)swap(arrayj,arrayj+1);/*直接插入排序算法思想：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，將它插入到有序表中的適當位置，使之成為新的有序表，重復n-1次可完成排序過程。時間復雜度 o(n2)空間復雜度 o(1)比較次數 n(n+1)/2*/void insert_sort(int array,int len)int tmp,i,j;for(i = 1;i len;i+)

37、if (arrayi = 0;j-)/往后移if (arrayj tmp)arrayj+1 =arrayj;elsearrayj+1 = tmp;break;if(j = -1)arrayj+1 = tmp;/*2-路插入排序算法思想：增加一個輔助空間d,把r1賦值給d1，并將d1看成是排好序后處于中間位置的記錄。然后從r2開始依次插入到d1之前或之后的有序序列中。時間復雜度 o(n2)空間復雜度 o(1)比較次數 n(n+1)/2*/void bi_insert_sort(int array,int len)int* arr_d = (int*)malloc(sizeof(int) * le

38、n);arr_d0 = array0;int head = 0,tail = 0;for (int i = 1;i arr_d0)int j;for ( j= tail;j0;j-)if (arrayi ARR_DJ) arr_dj+1 =arr_dj;elsebreak;arr_dj+1 = arrayi;tail += 1;elseif (head =0)arr_dlen-1 = arrayi;head =len-1;elseint j;for (j = head;j arr_dj)arr_dj-1 =arr_dj;elsebreak;arr_dj-1 = arrayi;head -= 1

39、;for (int i = 0;i = len) pos -= len;arrayi = arr_dpos;free(arr_d);/*希爾排序算法思想：先將整個待排序記錄分割成若干子序列分別進行直接插入排序，待整個序列中的記錄基本有序時，再對全體記錄進行一次直接插入排序時間復雜度 o(n2)空間復雜度 o(1)比較次數 ?*/void shell_insert(int array,int d,int len)int tmp,j;for (int i = d;i len;i+)if(arrayi = 0 &tmp 1);/*快速排序算法思想：將原問題分解為若干個規模更小但結構與原問題相似的子問

40、題。遞歸地解這些子問題，然后將這些子問題的解組合成為原問題的解。時間復雜度 o(nlogn)空間復雜度 o(logn)比較次數 ?*/void quick_sort(int array,int low,int high)if (low high)int pivotloc =partition(array,low,high);quick_sort(array,low,pivotloc-1);quick_sort(array,pivotloc+1,high);int partition(int array,int low,int high)int pivotkey = arraylow;while

41、 (low high)while(low = pivotkey)-high;swap(arraylow,arrayhigh);while(low high &arraylow = pivotkey)+low;swap(arraylow,arrayhigh);arraylow = pivotkey;return low;/*直接選擇排序算法思想：每一趟在n-i+1個記錄中選取關鍵字最小的記錄作為有序序列中的第i個記錄時間復雜度 o(n2)空間復雜度 o(1) ?比較次數 n(n+1)/2*/int SelectMinKey(int array,int iPos,int len)int ret =

42、 0;for (int i = iPos; i arrayi)ret = i;return ret;void select_sort(int array,int len)for (int i = 0; i len; i+)int j =SelectMinKey(array,i,len);if (i != j)swap(arrayi,arrayj);/*歸并排序算法思想：設兩個有序的子文件(相當于輸入堆)放在同一向量中相鄰的位置上：Rlow.m，Rm+1.high，先將它們合并到一個局部的暫存向量R1(相當于輸出堆)中，待合并完成后將R1復制回Rlow.high中。時間復雜度 o(nlogn)空

43、間復雜度 o(n)比較次數 ?*/void merge(int array,int i,int m, int n)int j, k;int iStart = i, iEnd = n;int arrayDest256;for ( j = m + 1,k = i; i = m& j = n; +k)if (arrayi arrayj)arrayDestk = arrayi+;elsearrayDestk = arrayj+;if (i = m)for (;k = n; k+,i+)arrayDestk = arrayi;if(j = n)for (;k = n; k+,j+)arrayDestk

44、= arrayj;for(j = iStart; j = iEnd; j+)arrayj = arrayDestj;void merge_sort(int array,int s,int t)int m;if (s t)m = (s + t )/2;merge_sort(array,s,m);merge_sort(array,m+1,t);merge(array,s,m,t);/*堆排序算法思想：堆排序(Heap Sort)是指利用堆(heaps)這種數據結構來構造的一種排序算法。堆是一個近似完全二叉樹結構，并同時滿足堆屬性：即子節點的鍵值或索引總是小于(或者大于)它的父節點。時間復雜度 o(

45、nlogn)空間復雜度 o(1)比較次數：較多*/void heap_adjust(int array,int i,int len)int rc = arrayi;for(int j = 2 * i; j if(j len & arrayj= arrayj) break;arrayi = arrayj; i = j;arrayi = rc;void heap_sort(int array,int len)int i;for(i = (len-1)/2; i = 0; i-)heap_adjust(array,i,len);for( i = (len-1); i 0; i-)swap(array

46、0,arrayi); /彈出最大值，重新對i-1個元素建堆heap_adjust(array,0,i-1);int main()int array = 45, 56, 76, 234, 1, 34,23, 2, 3, 55, 88, 100;int len = sizeof(array)/sizeof(int);/bubble_sort(array,len); /冒泡排序/*insert_sort(array,len);*/ /插入排序/*bi_insert_sort(array,len);*/ /二路插入排序/*shell_sort(array,len);*/ /希爾排序/*quick_sort(array,0,len-1);*/ /快速排序/*select_sort(array,len);*/ /選擇排序/*merge_sort(array,0,len-1);*/ /歸并排序heap_sort(array,len); /堆排序display(