數(shù)據(jù)結構知識點總結整理資料

1、數(shù)據(jù)結構知識點總結整理資料數(shù)據(jù)結 構知 識點 總結 整理0 、?？蓟A必知必會A. 排序 : 排序有幾種 , 各種排序的比較 , 哪些排序是穩(wěn)定的 , 快排的算法 ;B. 查找 : 哈希查找、二叉樹查找、折半查找的對比 , 哈希映射和哈希表的區(qū)別 ?C. 鏈表和數(shù)組的區(qū)別 , 在什么情況下用鏈表什么情況下用數(shù)組 ?D. 棧和隊列的區(qū)別 ?E. 多態(tài) , 舉例說明 ;overload和 override的區(qū)別 ?F. 字符串有關的函數(shù) , 比如讓你寫一個拷貝字符串的函數(shù)啊 , 或者字符串反轉啊什么的。 strcpy和 memcpy?G. 繼承、多繼承 ?H. 面向對象有什么好處 ?I. 說說 s

2、tatic 的與眾不同之處 , 如果一個變量被聲明為static,它會被分配在哪里 ?在什么時候分配空間等 ?J. 什么是虛函數(shù)、純虛函數(shù)、虛的析構函數(shù) , 用途 ?K. 內存泄漏及解決方法 ?網絡部分 :OSI 模型 7 層結構 ,TCP/IP模型結構 ?B. TCP/UDP 區(qū)別 ?C. TCP 建立連接的步驟 ?D. 香農定理 ?1 、二叉樹三種遍歷的非遞歸算法( 背誦版 ) 本貼給出二叉樹先序、中序、后序三種遍歷的非遞歸算法, 此三個算法可視為標準算法,直接用于考研答題。1. 先序遍 歷非遞 歸算法#define size 100typedef structBitree Elemsiz

3、e;int top;SqStack;void PreOrderUnrecBitree tSqStacks;StackInits;pt;whilep!null|!StackEmptyswhilep!null/遍歷左子樹visitep-data;pushs,p;pp-lchild;/endwhile if!StackEmptys /通過下一次循環(huán)中的內 嵌while實現(xiàn)右子樹遍歷ppops;pp-rchild;/endif/endwhile/PreOrderUnrec2. 中序遍 歷非遞 歸算法#define size 100typedef structBitree Elemsize;int to

4、p;SqStack;void InOrderUnrecBitree tSqStacks;StackInits;pt;whilep!null|!StackEmptyswhile p!null/遍歷左子樹pushs,p; pp-lchild; /endwhileif !StackEmptys pp-rchild; /ppops; 通 過 下visitep-data;一次循環(huán)實現(xiàn)/ 訪問根結點右子樹遍歷/endif/endwhile/InOrderUnrec3. 后序遍 歷非遞 歸算法#define size 100typedef enumL,R tagtype;typedef structBitr

5、ee ptr;tagtype tag;stacknode;typedef structstacknode Elemsize;int top;SqStack;/ 后序遍歷void PostOrderUnrecBitree tSqStack s;stacknodex;StackInits;pt; do whilep!null/遍歷左子樹 x.ptr p;x.tag L; / pp-lchild; while !StackEmptys標記為左子樹 pushs,x; &&s.Elems.top.tagR x pops;p x.ptr; visitep-data;/tag為R,表示右子樹

6、訪問完畢, 故訪問根結點if !StackEmptyss.Elems.top.tag R; /遍歷右子樹 ps.Elems.top.ptr-rchild; while !StackEmptys;/PostOrderUnrec4. 層次遍 歷算法/ 二叉樹的數(shù)據(jù)結構structBinaryTreeint value; / 不寫模板了 , 暫時用整形代替節(jié)點的數(shù)據(jù)類型 BinaryTree *left;BinaryTree *right;BinaryTree*root; /已知二叉樹的根節(jié)點/ 層次 遍歷voidLevel const BinaryTree *rootQueue *buf new

7、Queue; /定義一個空隊列 , 假設此隊列的節(jié)點數(shù)據(jù)類型也是整形的BinaryTreet;/一個臨時變量buf.push_backroot;/令根節(jié)點入隊whilebuf.emptyfalse/當隊列不為空pbuf.front;/取出隊列的第一個元素coutp-value''ifp-left!NULL/若左子樹不空, 則令其入隊q.push p-left ; ifp-right! NULL /若右子樹不空, 則令其入隊q.pushp-right;buf.pop; /遍歷過的節(jié)點出隊coutendl;2 、線性表(1) 性表的鏈式存儲方式及以下幾種常用鏈表的特點和運算 : 單

8、鏈表、循環(huán)鏈表 , 雙向鏈表 ,雙向循環(huán)鏈表。(2) 單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見的考查方式。(3) 單鏈表中設置頭指針、循環(huán)鏈表中設置尾指針而不設置頭指針以及索引存儲結構的各自好處。3 、棧與隊列你可以問一下自己是不是已經知道了以下幾點:1棧、隊列的定義及其相關數(shù)據(jù)結構的概念,包括:順序棧,鏈棧,共享棧,循環(huán)隊列,鏈隊等。棧與隊列存取數(shù)據(jù) ( 請注意包括 : 存和取兩部分 ) 的特點。 2 遞歸算法。 棧與遞歸的關系 , 以及借助棧將遞歸轉向于非遞歸的經典算法 : n! 階乘問題 ,fib數(shù)列問題 ,hanoi問題 ,背包問題 ,

9、二叉樹的遞歸和非遞歸 遍歷問題,圖的 深 度遍歷與棧的關系等。其中, 涉及到樹與圖的問題 , 多半會在樹與圖的相關章節(jié)中進行考查。 3 棧的應用 : 數(shù) 值表 達式的求解, 括 號的配對等的原理 , 只作原理性了解 , 具體要求考查此為題目的算法設計題不多。4 循環(huán)隊列中判隊空、隊滿條件,循環(huán)隊列中入隊與出隊( 循環(huán)隊列在插入時也要判斷其是否已滿 , 刪除時要判斷其是否已空) 算法?！狙h(huán)隊列的隊空隊滿條件為了方便起見,約定:初始化建空隊時, 令frontrear0,當隊空時:frontrear,當隊滿時:frontrear亦成立,因此只憑等式frontrear無法判斷隊空還是隊滿。有兩種方法

10、處理上述問題:(1)另設一個標志位以區(qū)別隊列是空還是滿。 (2) 少用一個元素空間 , 約定以“隊列頭指針 front 在隊尾指針 rear 的下一個位置上”作為隊列“滿”狀態(tài)的標志。隊空時 : frontrear ,隊滿時 :rear+1%sizefront】如果你已經對上面的幾點了如指掌, 棧與隊列一章可以不看書了。注意, 我說的是可以不看書 , 并不是可以不作題哦。/循環(huán)隊列的主要操作 : 1 創(chuàng)建循環(huán)隊列 2 初始化循環(huán)隊列 3 判斷循環(huán)隊列是否為空 4 判斷循環(huán)隊列是否為滿 5 入隊、出隊 / 空出頭尾之間的一個元素不用 #include #include #define SIZE

11、100typedef struct intelemSIZE;intfront, rear; Quque; /定義隊頭intinitQueQuque *q /初始化*q-front0;*q-rear0; intisFullQuque *q ifq-frontq-rear+1%SIZE/判滿空出一個元素不用 劉勉剛 return 1; else elem ifisFull*qreturnreturn0; int-1;insertQueQuque *q,int *q-elem*q-rearelem;*q-rear*q-rear+1%SIZE;/插入return0; int isEmptyQuque

12、*qifq-frontq-rear/ 判 空 return 1; else return deleteQueQuque * q,int *pelem ifisEmpty*q0;returnint0;*pelem*q-elem*q-front; *q-front*q-front +1%SIZE; return0;4 、串串一章需要攻破的主要堡壘有 :1. 串的基本概念 , 串與線性表的關系 ( 串 是其元 素均 為字符型 數(shù)據(jù)的 特殊線 性表 ), 空串與空格串的區(qū)別 , 串相等的條件 ;2. 串的基本操作 , 以及這些基本函數(shù)的使用 , 包括 : 取子串 , 串連接 , 串替 換, 求串長等等

13、。運用串的 基本操 作去完 成特 定的算法是很多學校在基本操作上的考查重點。 3. 順序串與鏈串及塊 鏈串的區(qū)別和聯(lián)系 , 實現(xiàn)方式。4. KMP 算法思想。 KMP 中 next數(shù)組以及 nextval數(shù)組的求法。 明確傳統(tǒng)模式匹配算法的不足,明確 next 數(shù)組需要改進?？赡苓M行的考查方式是 : 求 next 和 nextval 數(shù)組值 , 根據(jù)求得的 next或 nextval數(shù)組值給出運用KMP 算法進行匹配的匹配過程。5 、多維數(shù)組和廣義表矩陣包括 : 對稱 矩陣 ,三角 矩陣 , 具有某種特點的稀疏 矩陣等。熟悉稀疏矩陣的三種不同存儲方式:三元組 , 帶輔 助行 向量的二 元組 ,

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

15、完全二叉樹的性質 ,普通二叉樹的五個性質 :A. 第 i層的最多結點數(shù) ,B. 深度為 k的二叉樹的最多結點數(shù) ,C.n0n2+1 的性質 ,D.n 個結點的完全二叉樹的深度,E.順序存儲二叉樹時孩子結點與父結點之間的換算關系(root從 1 開始 , 則左為 :2*i, 右為 : 2*i+1) 。二叉樹的順序存儲和二叉鏈 表存儲的各自優(yōu)缺點及適用場合, 二叉樹的 三叉鏈 表表示方法。 2 二叉樹的三種遍 歷 算法這一知識點掌握的好壞 , 將直接關系到樹一章的算法能否理解 , 進而關系到樹一章的算法設計題能否順利完成。二叉樹的遍歷算法有三種 : 先序 , 中序和后序。其劃分的依據(jù)是視其每個算法

16、中對 根結點 數(shù)據(jù)的 訪問 順序而定。不僅要熟練掌握三種遍歷的遞歸算法 , 理解其執(zhí)行的實際步驟 , 并且應該 熟練掌 握三 種遍歷的 非遞歸 算法。由于二叉樹一章的很多算法 , 可以直接根據(jù)三種遞歸算法改造而來 ( 比如 : 求葉子個數(shù) ), 所以 , 掌握了三種遍歷的非遞歸算法后 , 對付諸如 :“利用非遞歸算法求二叉樹葉子個數(shù)” 這樣的題目就下筆如有神了。 3 可在三種遍歷算法的基礎上改造完成的其 它二 叉樹算法 : 求葉子個數(shù) , 求二叉樹 結點總數(shù) , 求度為 1 或度 為 2 的結點 總數(shù) , 復制二 叉 樹, 建立 二叉樹 , 交換 左右子 樹, 查找值為n 的某個指定結點 ,

17、刪除 值為 n的某個指定結 點 , 諸如此類等等等等。 如果你可以熟練掌握二叉樹的遞歸和非遞歸遍歷算法 , 那么解決以上問題就是小菜一碟了。 4 線索二叉樹 : 線索二叉樹的引出, 是 為避免如 二叉樹 遍歷時 的遞 歸求解。眾所周知 , 遞歸雖然形式上比較好理解 , 但是消耗了大量的內存資源, 如果遞歸層次一多 , 勢必帶來資源耗盡的危險 , 為了避免此類情況 , 線索二叉樹便堂而皇之地出現(xiàn)了。 對于線索二叉樹 , 應該掌握 : 線索 化的實質 , 三種線索化 的算法 , 線 索化后 二叉樹的 遍歷算 法, 基本線索二叉樹的其它算法問題 ( 如: 查 找某一類線索二叉樹中指定結點的 前驅或后

18、繼結點就是一類?？碱}) 。5 最優(yōu)二叉樹 ( 哈 夫 曼樹 ): 最優(yōu)二叉樹是為了解決特定問題引出的特殊二叉樹結構 , 它的前提是給二叉樹的每條邊賦予了權值 , 這樣 形成的 二叉 樹按權相 加之和 是最小 的。最優(yōu)二叉樹一節(jié) , 直接考查算法源碼的很少 , 一般是給你一組數(shù)據(jù) , 要求你建立基于這組數(shù)據(jù)的最優(yōu)二叉樹, 并求出其最小權值之和 , 此類題目不難 , 屬送分題。 6 樹與森林 : 二叉樹是一種特殊 的樹 , 這種特殊不僅僅在于 其分 支最多為 2 以及其它特征 , 一個最重要的特殊之處是在于 : 二叉樹 是有序的 ! 即 : 二叉 樹的左 右孩子是 不可交 換的 , 如果 交換了就

19、 成了另外一棵 二叉樹。 樹與森林的遍 歷 , 不像二叉樹那樣豐富 , 他們只 有兩種 遍歷算法 : 先 根與后根 ( 對于森 林而言 稱作 : 先序與后 序遍歷 ) 。此二者的先根與 后根遍 歷與二 叉樹 中的遍歷算法是有對應關系的 : 先 根遍歷 對應二叉 樹的先 序遍歷 , 而后根遍歷 對應二 叉樹的 中序 遍歷。 二叉樹 、樹與森林 之所以 能有以 上的 對應關系 , 全 拜二叉 鏈表所賜。 二 叉樹使 用二叉 鏈表分 別存放他 的左右孩子 , 樹利 用二叉 鏈表存 儲孩子及 兄弟 ( 稱孩 子兄弟鏈表 ) , 而森 林也是 利用二 叉鏈表存 儲孩子及兄弟 。 7 、圖 1. 圖的基本

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

21、兩種基本的遍歷算法而設計的 , 比如 :“求最 長的 最短路徑問題”和“判 斷兩 頂點間是 否存在長為 K 的簡單 路徑問 題”, 就分別用到了廣度遍歷和深度遍歷算法。 4. 生成樹、最小 生成 樹的概念以及最 小生成 樹的 構造:PRIM 算法和 KRUSKAL算法。考查時 , 一般不要求寫出算法源碼 , 而是要求根據(jù)這兩種最小生成樹的算法思想寫出其構造過程及最終生成的最小生成樹。 5. 拓撲排序問題 : 拓撲排序有兩種方法 , 一是無前 趨的頂 點優(yōu)先算法 , 二是無 后繼的 頂點優(yōu)先算法。換句話說 , 一種是“從前向后”的排序 , 一種是“從后向前”排。當然 , 后一種排序出來的結果是“

22、逆拓撲有序”的。6.關鍵路徑問題 : 這個問題是圖一章的難點問題。理解關鍵路徑的關鍵有三個方面:一是何謂關鍵路徑;二是最早時間是什么意思、如何求;三是最晚時間是什么意思、如何求。簡單地說 , 最早時間是通過 “從前向后” 的方法求的 , 而最晚時間是通過“從后向前”的方法求解的 , 并且 , 要想求最晚時間必須是在所有的最早時間都已經求出來之后才能進行。在實際設計關鍵路徑的算法時, 還應該注意以下這一點 : 采 用鄰接 表的存儲結 構, 求最 早時間和最 晚時間 要采用 不同 的處理方 法, 即 : 在算 法初始時 , 應 該首先 將所有 頂點 的最早時 間全部置為 0 。關鍵路徑問題是工程進

23、度控制的重要方法 , 具有很強的實用性。7. 最短路徑問題 : 與關鍵路徑問題并稱為圖一章的兩只攔路虎。 概念 理解是比 較容易 的, 關 鍵是 算法的理 解。最短路徑問題分為兩種: 一是求從某一點出發(fā)到其余各 點的最短 路徑 ( 單源最短路徑 ); 二是求圖中每一對頂點之間的最短 路徑。這個問題也具有非常實用的背景特色 , 一個典型的應該就是旅游景點及旅游路線的選擇問題。解決第一個問題用DIJSKTRA算法 , 解決第二個問題用FLOYD算法 , 注意區(qū)分。8 、查找 (search )先弄清楚以下幾個概念:關 鍵字、主關鍵字、 次 關鍵字的含義 ;靜態(tài) 查找與動態(tài)查 找的含義及區(qū)別 ; 平

24、均 查找長 度 ASL 的概念及在各種查找算法中的計算方法和計算結果 , 特別是一些典型結構的 ASL 值, 應該記住。一般將 search 分為三類 : 在順序表 上的查 找; 在 樹表 上的查找 ; 在哈 希表上 的查 找。 (1) 線性表上的查找 : 主要分為三種線性 結構:順序表 ?傳統(tǒng)查找方法 : 逐個比較 ;有序順序表?二分查找法 ( 注意適用條件以及其遞歸 實現(xiàn)方法 );索引順序 表?對索引結構 , 采用索引查找算法。 注意這三種表下的 ASL 值以及 三種算法 的實現(xiàn)。 (2)樹表上的查找 : 樹表主要分為以下幾種: 二叉排序樹(即二叉 查找 樹), 平 衡二叉查找樹 (AVL

25、 樹),B樹 , 鍵樹。其中 , 尤以前兩種結構為重 , 也有部分名校偏愛考B 樹的。由于二叉排 序樹與平衡二叉樹是一種特殊的二叉樹。二叉排序樹,簡言之 ,就是“左小右大” ,它的 中序遍歷結果是一個遞增的有 序序 列。 平 衡二叉排序樹是二叉排序樹的優(yōu)化 ,其本質也是一 種二叉排序樹,只不 過,平 衡排序 二叉 樹對左右子樹的深度有了限定 :深度之差 的絕對值不得大于 1 。對于二叉排序樹 , “判 斷某棵 二 叉樹是否二叉排序樹”這一算法經常被考到 ,可用遞歸 ,也可以用非遞歸。 平衡二叉樹的建立也是一個常考點 ,但該知識點歸根結底還是關注的平衡二叉樹的四種調整算法,調整的一個參照是 :調

26、整前后的中序遍歷結果相同。 B樹是二叉排序樹的進一步改進, 也可以把B 樹理 解為三叉、四叉 .排序樹。除 B 樹的查找算法外 , 應該特別注意一下B 樹的插入和刪除算法 , 因為這兩種算法涉及到B 樹 結點的分裂和合并 , 是一個難點。鍵樹(keywordtree),又稱數(shù)字搜索樹(digitalsearch tree)或字符樹。trie樹也可說等同于鍵樹或屬于鍵樹的一種。鍵 樹特別適 用于查找英文 單詞 的場合。一般不要求能完整描述算法源碼, 多是根據(jù)算法思想建立鍵樹及描述其大致查找過程。 (3)基于哈希表的查找算法: 哈希譯自“ hash”一詞, 意為“散列”或“ 雜湊”。哈希 表查找

27、的基本 思想是 : 根據(jù) 當前待查找數(shù) 據(jù)的特 征 , 以記 錄 關鍵字為 自變量 , 設計一個 function , 該函數(shù)對關 鍵字 進行轉換 后,其解釋結 果為待 查的地 址?；诠１淼目疾辄c有 : 哈 希函數(shù)的 設計 , 沖突解 決方 法的選擇及沖突處理過程的描述。9 、內部排序考查你對書本上的各種排序算法及其思想以及其優(yōu)缺點和性能指標(時間復雜度)能否了如指掌。排序方法分類有: 插入、選擇、交換、歸并、計數(shù)等五種排序方法。 (1)插入排序中又可分為:直接插入、折 半插入、2路插 入( ?)、 希爾排序。這幾種插入排序算法的最根本的不同點, 說到底就是根據(jù)什么規(guī)則尋找新 元素的插入點

28、。直接插入是依次尋找 , 折半插入是折半尋找, 希爾排序 , 是通過控制每次參與排序的數(shù)的總范圍“由小到大”的增量來實現(xiàn)排序效率提高的目的。(2) 交換排 序, 又稱冒泡排序 , 在交換排序的基礎上改進又可以得到快速排序?？焖倥判虻乃枷?, 一語以敝之 : 用中 間數(shù) 將待排數(shù) 據(jù)組一 分為二。(3) 選擇排序可以分為 : 簡 單選擇、 樹選擇、 堆 排序。選擇排序相對于前面幾種排序算法來說 , 難度大一點。這三種方法的不同點是 , 根據(jù) 什么 規(guī)則選取最小的 數(shù)。簡單選擇 , 是通過簡單的數(shù)組遍歷方案確定最小數(shù) ;樹選擇 , 是通過“錦標賽” 類似的思想 , 讓兩數(shù)相比 , 不斷淘汰較大 (

29、 小) 者, 最終選出最小 ( 大)數(shù) ;而堆排序 , 是利用堆這種數(shù)據(jù)結構的性質, 通過堆元素的刪除、 調整等一系列操作將最小數(shù)選出放在堆頂。堆排序中的堆建 立、堆調整是重要考點。(4) 歸 并排序 , 是 通過“ 歸并”這 種操作 完成排 序的 目的 ,既然是歸并就必須是兩者以上的數(shù)據(jù)集合才可能實現(xiàn)歸并。所以, 在歸并排序中 ,關注 最 多的就是 2 路歸并。算法思想比較簡單,有一點 , 要銘記在心 : 歸并 排序是穩(wěn) 定排序。 (5) 基數(shù)排序 , 是一種很特別的排序方法 , 也正是由于它的特殊 , 所以 , 基數(shù)排序就比較適合于一些特別的場合 , 比如撲克牌排序問題等。 基數(shù)排序 ,

30、又分為 兩種: 多關鍵 字的排序 ( 撲克牌排序 ),鏈式排序 (整 數(shù)排序 ) ?；鶖?shù)排序的核心思想也是 利用“基數(shù)空 間” 這個概念將問題規(guī)模規(guī)范、變小, 并 且,在排序的過程中 , 只要 按照 基排的思想, 是 不用進行關 鍵字比較的,這樣得出的最終序列就是一個有序序列。本章各種排序算法的思 想以及偽代碼實 現(xiàn), 及其時 間復雜度都是必須掌握的。/穩(wěn)定 性分 析/排序算法的穩(wěn)定性 , 通俗地講就是能 保證排 序前 2 個 相 等的數(shù)其 在序列 的前后 位置 順序和排 序后它們兩個的前后位置順序 相同。穩(wěn)定性的 好處 : 若排 序算法 如果是穩(wěn) 定的 , 那么 從一個鍵上排序 , 然 后再

31、從 另一個 鍵上排序 , 第一個鍵排 序的結 果可以 為第 二個鍵排 序所用?；鶖?shù)排序就是這樣 , 先按低位排序 , 逐次按高位排序 , 低位相同的元素其順序再高位也相同時是不會改變的。另外 ,如果排序算法穩(wěn)定 , 對基于比較的排序算法而言 , 元素交換的次數(shù)可能會少一些個人感覺 , 沒有證實。 分析一下常見的排序算法的穩(wěn)定性 , 每個都給出簡單的理由。 1 冒泡排序 冒泡排序就是把 小的 元素往前 調或者 把大的元素 往后調。 比較是 相鄰的 兩個 元素比較 , 交換也發(fā)生在這兩個元素之間 。所以 , 如果兩個元素相等 , 我想你是不會再無聊地把他們倆交換一下的 ; 如果兩個相等的元素沒有相

32、鄰 , 那么即使通過前面的兩兩交換把兩個相鄰起來 , 這時候也不會交換 , 所以相同元素的前后順序并沒有改變 , 所以 冒泡排序是一種 穩(wěn)定排 序算 法。 2 選擇排序選擇排序是給每個位置選擇當前元素最小的 , 比如給第一個位置選擇最小的 , 在剩余元素里面給第二個元素選擇第二小的, 依次類推 , 直到第 n-1個元素 ,第 n 個元素不用選擇了 , 因為只剩下它一個最大的元素了。 那么 , 在一趟選擇 , 如果當前元素比一個元素小 , 而該小的元素又出現(xiàn)在一個和當前元素相等的元素后面, 那么交換后穩(wěn)定性就被破壞了。比較拗口 ,舉個例子 ,序列 58529,我們知道第一遍選擇第1 個元素5 會

33、和2 交換 , 那么原 序列中 2 個 5 的相對前后順序就被破 壞了, 所以 選擇排序 不是一 個穩(wěn)定 的排 序算法。 3插入排序插入排序是在一 個已 經有序的 小序列 的基礎 上 ,一次插入一個元素。當然 , 剛開始這個有序的小序列只有1 個元素 , 就是第一個元素。比較是從有序序列的末尾開始 , 也就是想要插入的元素和已經有序的最大者開始比起, 如果比它大則直接插入在其后面 , 否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的 ,那么插入元素把想插入 的元 素放在相等元素的后面。所以 ,相等元素的前后順序沒有改變,從原無序序列出去的順序就是排好序后的順序,所以插入排序是

34、穩(wěn)定的。4快速排序快速排序有兩個方向,左邊的 i 下標一直往右走 , 當 ai acenter_index,其中center_index是中樞元素的數(shù)組下標, 一般取為數(shù)組第0 個元素。 而右邊的 j下標一直往左走 ,當 ajacenter_index。如果 i和 j都走不動了 ,i j,交換 ai 和 aj, 重復上面的過程 , 直到ij。交換aj和acenter_index,完成一趟快速排序。在中樞元素和aj交換的時候, 很有可能把前面的元素的穩(wěn)定性打亂, 比如序列為53343891011, 現(xiàn)在中樞元素5和3第5個元素 , 下標從 1開始計交換就會把元素3的穩(wěn)定性打亂 , 所以快速排序是

35、一個 不穩(wěn)定的排序算法 , 不 穩(wěn)定發(fā) 生在中樞元 素和 aj交換的時刻。 5歸并排序歸并排序是把序列遞歸地分成短序列,遞歸出口是短序列只有 1 個元素認為直接有序或者2個序列 1 次比較和交換 , 然后把各個有序的段序列合并成一個有序的長序列 , 不斷合并直到原序列全部排好序。可以發(fā)現(xiàn) , 在 1個或 2個元素時 ,1個元素不會交換 ,2個元素如果大小相等也沒有人故意交換 , 這不會破壞穩(wěn)定性。 那么 , 在短的有序序列合并的過程中 , 穩(wěn)定是是否受到破壞 ?沒有 , 合并過程中我們可以保證如果兩個當前元素相等時 , 我們把處在前面的序列的元素保存在結果序列的前面 , 這樣就保證了穩(wěn)定性。

36、所以 , 歸并排序也是穩(wěn)定的排序算法。 6 基數(shù)排序 基數(shù)排序是按照低位先排序 , 然后收集 ; 再按照高位排序 , 然后再收集 ; 依次類推 , 直到最高位。有時候有些屬性是有優(yōu)先級順序的, 先按低優(yōu)先級排序 ,再按高優(yōu)先級排序 , 最后的次序就是高優(yōu)先級高的在前,高優(yōu)先級相同的低優(yōu)先級高的在前?；鶖?shù)排序基于分別排 序,分 別收集 ,所以其是 穩(wěn)定的 排序算 法。 7 希爾排序 shell 希爾排序是按照不同步長對元素進行插入排序 , 當剛開始元素很無序的時候 , 步長最大,所以插入排序的元素個數(shù)很少 , 速度很快 ; 當元素基本有序了 , 步長很 小, 插 入排序 對于有序 的序列效率很

37、高。所以 , 希爾排序的時間復雜度會比 on2 好一些。由于多次插入排序 , 我們知道一次插入排序是穩(wěn)定的 , 不會改變相同元素的相對順序 , 但在不同的插入排序過程中 , 相同的元素可能在各自的插入排序中移動 , 最后其穩(wěn)定性就會被打亂 , 所以 shell 排序是不 穩(wěn)定的。 8 堆排序 我們知道堆的結構是節(jié)點i的孩子為 2*i和 2*i+1節(jié)點 ,大頂堆要求父節(jié)點大于等于其2個子節(jié)點 , 小頂堆要求父節(jié)點小于等于其2個子節(jié)點。在一個長為 n的序列 , 堆排序的過程是從第n/2開始和其子節(jié)點共3個值選擇最大大頂堆或者最小小頂堆,這 3 個元素之間的選擇當然不會破壞穩(wěn)定性。但當為n /2-1

38、,n/2-2,.1這些個父節(jié)點選擇元素時 , 就會破壞穩(wěn)定性。有可能第 n/2個父節(jié)點交換把后面一個元素交換過去了, 而第 n/2-1個父節(jié)點把后面一個相同的元素沒有交換 , 那么這 2個相同的元素之間的穩(wěn)定性就被破壞了。所以, 堆 排序不 是穩(wěn) 定的排序 算法。/冒泡排序插 入排序二 路 插入排序希 爾排序快速排序選擇排序 歸并排 序堆排序算法的C/C+實現(xiàn)/#includeusing namespace std;/ 交換兩個數(shù)的值void swapint &a,int &bint tmp;tmpa;ab;btmp;/ 屏幕輸出數(shù)組void displayint array,

39、int lencout"theresultis:"endl;forinti0;ilen;i+coutarrayi" "coutendl;/*冒泡排序算法思想 : 將被排序的記錄數(shù)組R1.n垂直排列 , 每個記錄Ri 看作是重量為 Ri.key 的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則 , 從下往上掃描數(shù)組 R: 凡掃描到違反本原則的輕氣泡 , 就使其向上 " 飄浮 " 。如此反復進行 , 直到最后任何兩個氣泡都是輕者在上 , 重者在下為止。時間復雜度 on2空間復雜度 o1比較次數(shù) nn+1/2*/void bubble_sortin

40、t array,int lenforintilen-1;i0;i-forintj0;ji;j+ifarrayj arrayj+1swaparrayj,arrayj+1;/*直接插入排序算法思想 : 把 n個待排序的元素看成為一個有序表和一個無序表, 開始時有序表中只包含一個元素 , 無序表中包含有 n-1 個元素 , 排序過程中每次從無序表中取出第一個元素 , 將它插入到有序表中的適當位置 , 使之成為新的有序表 , 重復 n-1 次可完成排序過程。時間復雜度 on2空間復雜度 o1比較次數(shù) nn+1/2*/void insert_sortint array,int lenint tmp,i,

41、j;fori 1;i len;i+ if arrayi arrayi-1tmparrayi;arrayiarrayi-1;/ 插入到相應位置for j i-2;j 0;j- / arrayj; else往后移 arrayj+1if arrayj tmp arrayj+1tmp;break;ifj-1arrayj+1 tmp;/*2- 路插入排序算法思想 : 增加一個輔助空間d, 把 r1賦值給 d1,并將 d1看成是排好序后處于中間位置的記錄。然后從r2開始依次插入到d1 之前或之后的有序序列中。時間復雜度 on2空間復雜度 o1比較次數(shù) nn+1/2*/void bi_insert_sort

42、int array,int lenint*arr_dint*mallocsizeofintarray0;int head 0,tail 0;for int i 1;i len; i+ ifarrayi arr_d0int j; for j tail;j0;j- if arrayiarr_djarr_dj+1arr_dj;elsebreak;arrayi;tail+1;elseifheadarrayi;head len-1;else int j;for j head;j len-1;j+ifarrayiarr_djarr_dj-1break;arr_dj-1 arrayi;head - 1;fo

43、r int i 0;i len;i+intposi+ head ;ifposlenposarr_dpos; freearr_d;*len;arr_d0arr_dj+10arr_dlen-1arr_dj;else-len;arrayi/*希爾排序算法思想 : 先將整個待排序記錄分割成若干子序列分別進行直接插入排序 , 待整個序列中的記錄基本有序時, 再對全體記錄進行一次直接插入排序時間復雜度 on2空間復雜度 o1比較次數(shù)*/void shell_insertint array,int d,int lenint tmp,j;for int i d;i len;i+ ifarrayi arrayi-d tmp arrayi; j i - d; doar