一：緒論O(1) ：常量時(shí)間階 O (n)：線性時(shí)間階 O(㏒n) ：對(duì)數(shù)時(shí)間階 O(n㏒n) ：線性對(duì)數(shù)時(shí)間階 O (nk)： k≥2 ，k次方時(shí)間階 以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其關(guān)系為： O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3) 指數(shù)時(shí)間的關(guān)系為： O(2n)<O(n!)<O(nn)
算法的空間復(fù)雜度定義為:S(n) = O(g(n)) 表示隨著問(wèn)題規(guī)模 n 的增大，算法運(yùn)行所需存儲(chǔ)量S(n)的增長(zhǎng)率與 g(n) 的增長(zhǎng)率相同，稱S(n)(漸近)空間復(fù)雜度。
二：線性表順序線性表： 設(shè)在線性表L中的第i個(gè)元素之前插入結(jié)點(diǎn)的概率為Pi，不失一般性，設(shè)各個(gè)位置插入是等概率，則Pi=1/(n 1)，而插入時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i 1。 總的平均移動(dòng)次數(shù)： Einsert=∑pi*(n-i 1) (1≦i≦n) ∴ Einsert=n/2 。 鏈?zhǔn)骄€性表： 單鏈表： 例2.1假設(shè)利用兩個(gè)線性表LA和LB分別表示兩個(gè)集合A和B，現(xiàn)要求一個(gè)新的集合A=A∪B。 算法思想：1、擴(kuò)大La，將存在于Lb中而不存在于La中的數(shù)據(jù)元素插入到La中去。2、需要從Lb中依次取得每個(gè)數(shù)據(jù)元素，并依值在La中進(jìn)行查訪，若不存在，則插 之。 例2.3 已知線性表LA和LB中的數(shù)據(jù)元素是按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的線性表LC，且LC中的數(shù)據(jù)元素也是按值非遞減有序排列。 1.初始化 LC 為空表； 2.分別從 LA和LB中取得當(dāng)前元素 ai 和 bj； 3.若 ai≤bj，則將 ai 插入到 LC 中，否則將bj 插入到 LC 中； 4.重復(fù) 2 和 3 兩步，直至 LA 或 LB 中元素被取完為止； 5.將 LA 表或 LB 表中剩余元素復(fù)制插入到LC 表中。 （雙向）循環(huán)鏈表： 約瑟夫問(wèn)題： n 個(gè)人圍成一個(gè)圓圈，首先第1個(gè)人從1開(kāi)始一個(gè)人一個(gè)人順時(shí)針報(bào)數(shù), 報(bào)到第m個(gè)人，令其出列。然后再?gòu)南乱粋€(gè)人開(kāi)始，從1順時(shí)針報(bào)數(shù)，報(bào)到第m個(gè)人，再令其 出列，…，如此下去, 直到圓圈中只剩一個(gè)人為止。此人即為優(yōu)勝者。 例如 n = 8 m = 3
三：棧和隊(duì)列括號(hào)匹配的檢驗(yàn)：（棧） 假設(shè)在表達(dá)式中允許包含兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，即： （［］（））或［（［ ］［ ］）］等為正確的格式， ［（ ］）或（［（ ））或 （（）］)均為不正確的格式。 則 檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來(lái)描述。 算法設(shè)計(jì)： 1） 凡出現(xiàn)左括弧，則進(jìn)棧； 2） 凡出現(xiàn)右括弧，首先檢查棧是否空 若?？?，則表明該“右括弧”多余， 否則和棧頂元素比較， 若相匹配，則“左括弧出?！?， 否則表明不匹配。 3）表達(dá)式檢驗(yàn)結(jié)束時(shí)， 若棧空，則表明表達(dá)式中匹配正確， 否則表明“左括弧”有余。
表達(dá)式求值：（棧） 迷宮求解：（棧） 求迷宮路徑算法的基本思想是：從入口出發(fā)，按某一方向向未走過(guò)的前方探索 若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn) 若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索; 若四周“均無(wú)通路”，則將當(dāng)前位置從路徑中刪除出去。
算法： 設(shè)定當(dāng)前位置的初值為入口位置； do｛ 若當(dāng)前位置可通， 則｛將當(dāng)前位置插入棧頂； 若該位置是出口位置，則算法結(jié)束； 否則切換當(dāng)前位置的東鄰方塊為 新的當(dāng)前位置； ｝ 否則 { ｝ ｝while (棧不空）； 若棧不空且棧頂位置尚有其他方向未被探索， 則設(shè)定新的當(dāng)前位置為: 沿順時(shí)針?lè)较蛐D(zhuǎn) 找到的棧頂位置的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通， 則｛刪去棧頂位置；// 從路徑中刪去該通道塊 若棧不空，則重新測(cè)試新的棧頂位置， 直至找到一個(gè)可通的相鄰塊或出棧至棧空； ｝ 若?？?，則表明迷宮沒(méi)有通路。
棧的另外一個(gè)重要的應(yīng)用：遞歸調(diào)用 用分治法求解遞歸問(wèn)題： 分治法：對(duì)于一個(gè)較為復(fù)雜的問(wèn)題，能夠分解成幾個(gè)相對(duì)簡(jiǎn)單的且解法相同或類(lèi)似的子問(wèn)題來(lái)求解 三個(gè)條件： 1、能將一個(gè)問(wèn)題轉(zhuǎn)變成一個(gè)新問(wèn)題，而新問(wèn)題與原問(wèn)題的解法相同或類(lèi)同，不同的僅是處理的對(duì)象，且這些處理對(duì)象是變化有規(guī)律的
2、可以通過(guò)上述轉(zhuǎn)化而使問(wèn)題簡(jiǎn)化
3、必須有一個(gè)明確的遞歸出口，或稱遞歸的邊界
分治法求解遞歸問(wèn)題算法的一般形式： void p (參數(shù)表) { if （遞歸結(jié)束條件）可直接求解步驟；-----基本項(xiàng) else p（較小的參數(shù)）；------歸納項(xiàng) } longFact ( longn ) { if( n==0) return 1; //基本項(xiàng) else returnn * Fact (n-1); //歸納項(xiàng)} 四：串
簡(jiǎn)單字符串模式匹配算法（BF算法）： 算法思想：從主串S的第pos個(gè)字符起和模式串T的第一個(gè)字符比較之，若相等，則繼續(xù)比較后續(xù)字符；否則從主串的下一個(gè)字符起再重新和模式的字符比較之。依此類(lèi)推，直至模式T中的每個(gè)字符依次和主串S中的一個(gè)連續(xù)的字符序列相等，則稱匹配成功，函數(shù)值為和模式T中第一個(gè)字符相等的字符在主串S中序號(hào)，否則稱匹配不成功，函數(shù)值為零。 首尾字符串匹配算法： 先比較模式串的第一個(gè)字符 再比較模式串的最后一個(gè)字符 最后比較模式串中從第二個(gè)到第n-1個(gè)字符
Kmp算法：（難理解）：復(fù)雜度o（m n） 若設(shè)目標(biāo)串(主串)為s，模式串為p ，并設(shè)i指針和j指針?lè)謩e指示目標(biāo)串和模式串中正待比較的字符，設(shè)i和j的初值均為1。若有si=tj，則i和j分別加1。否則，i不變，j退回到j(luò)=next[j]的位置，再比較si和tj，若相等，則i和j分別加1。否則，i不變，j再次退回到j(luò)=next[j]的位置，依此類(lèi)推，直至下列兩種可能： 一種是j退到某個(gè)next[…]時(shí)字符比較相等，則指針各自增1，繼續(xù)進(jìn)行匹配； 另一種是j退到值為零（即模式的第一個(gè)字符“失配），則此時(shí)需將模式繼續(xù)向右滑動(dòng)一個(gè)位置，即從主串的一個(gè)字符si 1起和模式重新開(kāi)始匹配。
五：數(shù)組和廣義表：數(shù)組，廣義表是線性表的推廣； 特殊矩陣： 對(duì)稱矩陣： 上三角： 下三角：
對(duì)角矩陣：對(duì)角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲(chǔ)到 一維數(shù)組中，且也能找到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。 稀疏矩陣： 稀疏因子：m行n列t個(gè)非零元素
順序存儲(chǔ)：三元組（行數(shù)，列數(shù)，元素值） 轉(zhuǎn)置： 算法的基本思想：第一次從轉(zhuǎn)置前稀疏矩陣source中取出應(yīng)該放置到轉(zhuǎn)置后的稀疏矩陣dest中第一個(gè)位置的元素，行列號(hào)互換后，放于dest中第一個(gè)位置；第二次從source中選取應(yīng)該放到dest中的第二個(gè)位置的元素，……，如此進(jìn)行，依次生成dest中的各元素。 方法一：按m的列序轉(zhuǎn)置 按T.data中三元組次序依次在M.data中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置，即按照矩陣M的列序來(lái)進(jìn)行置換。 為找到M中每一列所有非零元素，需對(duì)其三元組表M.data從第一行起掃描一遍。由于M.data中以M行序?yàn)橹餍?，所以由此得到的恰是T.data中應(yīng)有的順序。 方法二：快速轉(zhuǎn)置 按M.data中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入T.data中恰當(dāng)位置。 此法關(guān)鍵是要預(yù)先確定M中每一列第一個(gè)非零元在T.data中位置，為確定這些位置，轉(zhuǎn)置前應(yīng)先求得M的每一列中非零元個(gè)數(shù)。 鏈?zhǔn)酱鎯?chǔ)：十字鏈表
廣義表：（人工智能）： 廣義表可以看成是線性表的推廣，線性表是廣義表的特例。廣義表的結(jié)構(gòu)相當(dāng)靈活，在某種前提下，它可以兼容線性表、數(shù)組、樹(shù)和有向圖等各種常用的數(shù)據(jù)結(jié)構(gòu)。 A=()，B=(x, y, z)，C=(B, y, z)，D=(x,(y, z))，E=(x, E)
六：樹(shù)與二叉樹(shù)二叉樹(shù)的性質(zhì)：
滿二叉樹(shù)的定義： 法一：若二叉樹(shù)中最多只有最下兩層有度小于2的結(jié)點(diǎn),且最下層的結(jié)點(diǎn)都依次排列在最左邊,則稱此二叉樹(shù)為完全二叉樹(shù)。 法二：深度為k的二叉樹(shù),若第1到第k-1層為深度為k-1的滿二叉樹(shù),第k層的結(jié)點(diǎn)都依次排列在最左邊,則稱此二叉樹(shù)為完全二叉樹(shù)。
二叉樹(shù)的存儲(chǔ)： 順序：適合滿二叉樹(shù)和完全二叉樹(shù) 鏈?zhǔn)剑憾骀湵?，三叉鏈?/p> 特點(diǎn)：n個(gè)結(jié)點(diǎn)，有n 1個(gè)空指針域 二叉樹(shù)的遍歷：前序遍歷，中序遍歷，后序遍歷（前中后是指根結(jié)點(diǎn)） 實(shí)現(xiàn)：遞歸方法 非遞歸方法：用棧
已知前序遍歷和后序遍歷不能求出二叉樹(shù)
線索二叉樹(shù)： 目的：非線性結(jié)構(gòu) –> 線性結(jié)構(gòu) 先序線索二叉樹(shù) 中序線索二叉樹(shù) 后續(xù)線索二叉樹(shù)
樹(shù)的存儲(chǔ)： 雙親表示法 孩子表示法 孩子兄弟表示法（常用）
樹(shù)轉(zhuǎn)二叉樹(shù)：兄弟相連留長(zhǎng)子 特點(diǎn)：其右子樹(shù)一定為空
二叉樹(shù)變樹(shù)：左孩右右連雙親，去掉原來(lái)右孩線
森林變二叉樹(shù)：樹(shù)變二叉根相連
二叉樹(shù)變森林：去掉全部右孩線，孤立二叉再還原
樹(shù)的遍歷與二叉樹(shù)遍歷對(duì)應(yīng)的關(guān)系：
樹(shù)：先序遍歷，后序遍歷 森林：先序遍歷，中序遍歷 二叉樹(shù)：先序遍歷，中序遍歷
Haffman樹(shù)與Haffman編碼： Haffman樹(shù)最優(yōu)樹(shù)：帶權(quán)路徑長(zhǎng)度（WPL）最短的樹(shù) Haffman最優(yōu)二叉樹(shù)：WPL最短的二叉樹(shù)
構(gòu)造Haffman樹(shù)：7 5 5 2 4
Haffman編碼：根據(jù)字符出現(xiàn)頻率編碼，使電文總長(zhǎng)度最短
兩個(gè)問(wèn)題： n個(gè)結(jié)點(diǎn)經(jīng)n-1次合并，每次生成新的結(jié)點(diǎn)，總共 n n-1=2n-1個(gè)結(jié)點(diǎn)，度為2的結(jié)點(diǎn)個(gè)數(shù)為n-1
沒(méi)有度為1的結(jié)點(diǎn)
七：圖無(wú)向圖邊的取值范圍：0<=e<=n(n-1)/2 有向圖弧的取值范圍：0<=e<=n(n-1)
稀疏圖：邊數(shù)或弧數(shù)遠(yuǎn)少于nlogn 連通：無(wú)向圖中，頂點(diǎn)到頂點(diǎn)之間有路徑
圖的生成樹(shù)：一個(gè)連通圖（無(wú)向圖），生成樹(shù)是一個(gè)極小連通子圖，有圖中全部n個(gè)頂點(diǎn)，n-1條邊
對(duì)于非連通圖，每個(gè)連通分量可以構(gòu)造一顆生成樹(shù)，從而構(gòu)成森林 圖構(gòu)成森林:由若干棵有向樹(shù)組成，會(huì)有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹(shù)的弧
圖的存儲(chǔ)：鄰接矩陣，鄰接鏈表，十字鏈表，鄰接多重表，邊表
有向圖的鄰接矩陣：頂點(diǎn)的度 = 第i行元素之和 第j列元素之和
無(wú)向樹(shù)的鄰接矩陣：頂點(diǎn)的度 = 第i行的元素 1 的個(gè)數(shù)
優(yōu)點(diǎn)：容易實(shí)現(xiàn)圖的操作 缺點(diǎn)：空間效率為o（n2）
鄰接表：效率o(n e)
圖的遍歷： 深度優(yōu)先DFS：（Depth_First Search） 基本思想：仿樹(shù)的中序遍歷，分連通圖和非連通圖兩類(lèi) 廣度優(yōu)先BFS：（Breadth First Search） 基本思想：仿樹(shù)的層次遍歷
圖的最小生成樹(shù) 生成樹(shù)的代價(jià)：如果連通圖是一個(gè)帶權(quán)圖，則其生成樹(shù)中的邊也帶權(quán)，生成樹(shù)中所有邊的權(quán)值之和稱為生成樹(shù)的代價(jià) 最小生成樹(shù)MST（Minimun Spanning Tree）:帶權(quán)連通圖中代價(jià)最小的生成樹(shù)
構(gòu)造最小生成樹(shù)的方法： ① Prim算法（以頂點(diǎn)為對(duì)象），時(shí)間復(fù)雜度o(n2),適合稠密圖 ② Kruskal算法（以邊為對(duì)象），時(shí)間復(fù)雜度o(eloge),適合稀疏圖 注意：最小生成樹(shù)可能不唯一 有向無(wú)環(huán)圖及其應(yīng)用： 有向無(wú)環(huán)圖DAG：（Directed Acycling Graph） 拓?fù)渑判颍?/span> ① 在有向圖選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出 （入度為0） ② 從圖中刪除該頂點(diǎn)及它的所有尾 ③ 重復(fù)以上兩步
AOV網(wǎng)：頂點(diǎn)表示活動(dòng)的網(wǎng)（Activity On Vertex network）,不允許有回路，弧表示活動(dòng)之間的優(yōu)先制約關(guān)系 檢測(cè)AOV中是否存在環(huán)：網(wǎng)中所有頂點(diǎn)拓?fù)溆行蛐蛄校ㄍ負(fù)湫蛄胁皇俏ㄒ坏模?/p>
關(guān)鍵路徑：（Critical Path） AOE網(wǎng)（Activity On Eage network）：頂點(diǎn)表示時(shí)間，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)的時(shí)間
關(guān)鍵活動(dòng)：該邊上的權(quán)值增加將使有向圖上的最長(zhǎng)路徑長(zhǎng)度增加，l（i）=e（i）
找關(guān)鍵路徑：必須找到關(guān)鍵活動(dòng) ① 向前遞推 ② 向后遞推 ③ 把l(i)=e(i)的路徑連起來(lái)
最短路徑（Short Path）：交通網(wǎng)絡(luò)問(wèn)題
分兩種：?jiǎn)卧袋c(diǎn)最短路徑，所有頂點(diǎn)最短路徑
單源點(diǎn)最短路徑：
方法一：將源點(diǎn)到終點(diǎn)所有路徑列出來(lái)，選最短的。缺點(diǎn)：隨路徑的增多，效率會(huì)降低 方法二：Dijkstra算法：按路徑長(zhǎng)度遞增次序產(chǎn)生各頂點(diǎn)的最短路徑
每一對(duì)頂點(diǎn)間最短路徑： 方法一：以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法N次，T(n)=o(n3) 方法二：Floyd算法： 思想：逐個(gè)頂點(diǎn)試探，從vi到vj的所有可能存在路徑中，選出一條長(zhǎng)度最短的 實(shí)現(xiàn)： （1）初始時(shí)設(shè)置一個(gè)n階方陣，令其對(duì)角線元素為0，若存在弧<Vi,Vj>，則對(duì)應(yīng)元素為權(quán)值，否則為∞。 （2）逐步試著在原直接路徑中增加中間頂點(diǎn)，若加入中間點(diǎn)后路徑變短，則修改之；否則，維持原值。 （3）所有頂點(diǎn)試探完畢，算法結(jié)束。
八：查找靜態(tài)表查找平均查找長(zhǎng)度ASL：（Average Search Length）：為了確定記錄在表中的位置，需要與給定值進(jìn)行比較關(guān)鍵字的個(gè)數(shù)的期望值 評(píng)價(jià)標(biāo)準(zhǔn)：ASL 順序查找：（順序或鏈?zhǔn)剑?/strong> 思想：從表中最后一個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等，則查找成功，否則查找不成功。
折半查找：（順序） 效率比順序查找高
動(dòng)態(tài)查找表存在關(guān)鍵字為key的記錄，則返回，否則插入
二叉排序樹(shù)：（二叉查找樹(shù)） 特點(diǎn)： i. 左子樹(shù)所有節(jié)點(diǎn)<根節(jié)點(diǎn) ii. 右子樹(shù)所有節(jié)點(diǎn)>根節(jié)點(diǎn) iii. 左右子樹(shù)分別是二叉排序樹(shù) 算法： ① 查找 ② 插入：插入位置由查找過(guò)程得到 ③ 刪除：（分三種情況，定則：保持中序序列不變） a) *p為葉子節(jié)點(diǎn)，只需修改*P雙親*f的指針 b) *P只有左子樹(shù)或右子樹(shù) i. 只有左子樹(shù)：用*P的左孩子代替*p ii. 只有右子樹(shù)：用*p的右孩子代替*p c) *p左右子樹(shù)非空 i. 用*P的直接前驅(qū)取代*p ii. 用*p的直接后繼取代*p iii. 若*p的左子樹(shù)無(wú)右子樹(shù)，用*p左子樹(shù)取代*p
含有 n 個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的平均查找長(zhǎng)度和樹(shù)的形態(tài)有關(guān) 最好情況： ASL=log 2(n 1) – 1; 最壞情況：插入的 n 個(gè)元素從一開(kāi)始就有序， —— 變成單支樹(shù)的形態(tài)！ 此時(shí)樹(shù)的深度為 n; ASL = (n 1) / 2 查找效率與順序查找情況相同。
平衡二叉樹(shù)（AVL樹(shù)）： 性質(zhì)： ① 左右子樹(shù)是平衡二叉樹(shù) ② 所有節(jié)點(diǎn)的左右子樹(shù)深度之差的絕對(duì)值小于等于1
節(jié)點(diǎn)平衡因子：該節(jié)點(diǎn)左子樹(shù)和右子樹(shù)的深度差
構(gòu)造平衡二叉樹(shù)： LL平衡旋轉(zhuǎn)：（B為軸，順時(shí)針旋轉(zhuǎn)） RR平衡旋轉(zhuǎn)：（B為軸，逆時(shí)針旋轉(zhuǎn)） LR平衡旋轉(zhuǎn)：（c為軸，先逆時(shí)針旋轉(zhuǎn)，后順時(shí)針旋轉(zhuǎn)） RL平衡旋轉(zhuǎn)：（c為軸，先順時(shí)針旋轉(zhuǎn)，后逆時(shí)針旋轉(zhuǎn)）
B-樹(shù)：
B 樹(shù)：
散列表： 特點(diǎn)：ASL=0，不需要經(jīng)過(guò)比較
哈希表：根據(jù)設(shè)定的哈希函數(shù)H（key）和所選中的處理沖突的方法建立的查找表
思想：以記錄的關(guān)鍵字為自變量，根據(jù)哈希函數(shù)計(jì)算出對(duì)應(yīng)的哈希地址，并在此存儲(chǔ)該記錄的內(nèi)容
構(gòu)造哈希函數(shù)的方法： 對(duì)數(shù)字：直接定值法，數(shù)字分析法，隨機(jī)數(shù)法 平方取中法（常用），折疊法，除留與余數(shù)法（最常用H(key)=key MOD p p<=m,p為<m的素?cái)?shù)或不含20以下質(zhì)因子的合數(shù)） 非數(shù)字：先進(jìn)行數(shù)字化處理
處理沖突的方法： ① 開(kāi)放定址法：當(dāng)發(fā)生沖突，在沖突位置前后附近尋找可以存放記錄的空閑單元 H0=H(key) Hi=(H(key) di) MOD m i=1,2…. Di有三種取法： a) 線性探測(cè)再散列 ，di = 1,2,…. b) 二次探測(cè)再散列（平方），di = 12-1222-22 c) 為隨機(jī)探測(cè)再散列（雙散列函數(shù)探測(cè)再散列） i. Di=偽隨機(jī)數(shù)列 或者 di = i×H2(key) ② 鏈地址開(kāi)方法（開(kāi)域法）：將所有哈希值相同的記錄都連接在同一鏈表中
九：排序評(píng)價(jià)標(biāo)準(zhǔn)：執(zhí)行時(shí)間，輔助空間，算法穩(wěn)定性
內(nèi)部排序： ① 插入排序 a) 直接插入排序 b) 希爾排序 i. 思想：將整個(gè)待排序記錄分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，對(duì)全體記錄進(jìn)行直接插入排序。 ② 交換排序 a) 冒泡排序 b) 快速排序 i. 思想: 首先選一個(gè)軸值（即比較的基準(zhǔn)），通過(guò)一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，前一部分記錄的關(guān)鍵碼均小于或等于軸值，后一部分記錄的關(guān)鍵碼均大于或等于軸值，然后分別對(duì)這兩部分重復(fù)上述方法，直到整個(gè)序列有序。 ③ 選擇排序 a)簡(jiǎn)單選擇排序（直接選擇排序） b)堆排序（改進(jìn)：查找最小碼的同時(shí)，找出較小值，分大根堆，小根堆） ④ 歸并排序 a) 二路歸并排序：將一個(gè)具有n個(gè)待排序記錄的序列看成是n個(gè)長(zhǎng)度為1的有序序列，然后進(jìn)行兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的有序序列，再進(jìn)行兩兩歸并，得到n/4個(gè)長(zhǎng)度為4的有序序列，……，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。 ⑤ 基數(shù)排序 a) 多關(guān)鍵字排序 i. 最高位優(yōu)先MSD法 ii. 最低位優(yōu)先MSD法 b) 鏈?zhǔn)交鶖?shù)排序 c)基數(shù)排序的時(shí)間復(fù)雜度為O(d(2n r)) 其中：分配為O(n) 收集為O(n r)(r為“基”) d為“分配-收集”的趟數(shù)
外部排序：外排總的時(shí)間還應(yīng)包括內(nèi)部排序所需時(shí)間和逐趟歸并時(shí)進(jìn)行內(nèi)部歸并的時(shí)間
討論： 時(shí)間復(fù)雜度： ① 平均時(shí)間性能： a)時(shí)間復(fù)雜度為 O(nlogn)：快速排序、堆排序和歸并排序 b) 時(shí)間復(fù)雜度為 O(n2)：直接插入排序、起泡排序和簡(jiǎn)單選擇排序 c)時(shí)間復(fù)雜度為 O(n):基數(shù)排序 ② 排元素序列按關(guān)鍵字順序有序 a) 直接插入排序能達(dá)到O(n)的時(shí)間復(fù)雜度， 快速排序的時(shí)間性能蛻化為O(n2) 。 ③ 排序的時(shí)間性能不隨關(guān)鍵字分布而改變的排序 a) 簡(jiǎn)單選擇排序、起泡排序、堆排序和歸并排序的時(shí)間性能不隨元素序列中關(guān)鍵字的分布而改變
穩(wěn)定的排序方法指的是，對(duì)于兩個(gè)關(guān)鍵字相等的元素，它們?cè)谛蛄兄械南鄬?duì)位置，在排序之前和經(jīng)過(guò)排序之后，沒(méi)有改變。
|
|
|
來(lái)自： txs84 > 《待分類(lèi)》
