幾種常見算法的介紹及復(fù)雜度分析

1、幾種常見算法的介紹及復(fù)雜度分析1. 基本概念1.1穩(wěn)定排序(stable sort)和非穩(wěn)定排序 穩(wěn)定排序是所有相等的數(shù)經(jīng)過某種排序方法后，仍能保持它們在排序之前的相對次序，。反之，就是非穩(wěn)定的排序。比如：一組數(shù)排序前是a1,a2,a3,a4,a5其中a2=a4,經(jīng)過某種排序后為a1,a2,a4,a3,a5,則我們說這種排序是穩(wěn)定的，因為a2排序前在a4的前面，排序后它還是在a4的前面。假如變成 a1,a4,a2,a3,a5就不是穩(wěn)定的了。1.2 內(nèi)排序 ( internal sorting ) 和外排序 ( external sorting)在排序過程中， 所有需要排序的數(shù)都在內(nèi)存， 并在內(nèi)

2、存中調(diào)整它們的存儲順序， 稱為內(nèi)排序； 在排序過程中， 只有部分數(shù)被調(diào)入內(nèi)存， 并借助內(nèi)存調(diào)整數(shù)在外存中的存放順序排序方法稱 為外排序。一個算法的空間復(fù)雜度，一1.3 算法的時間復(fù)雜度和空間復(fù)雜度 所謂算法的時間復(fù)雜度，是指執(zhí)行算法所需要的計算工作量。 般是指執(zhí)行這個算法所需要的內(nèi)存空間。2. 幾種常見算法將待排序的元素看作是豎著排 氣泡 ” 并時刻注意兩個相鄰的 輕”的元素在下面， 就交換它2.1 冒泡排序( Bubble Sort) 冒泡排序方法是最簡單的排序方法。 這種方法的基本思想是，最輕”的元素就浮到了最高位置；處理二遍之后， “次輕 ” 最輕”元素， 所 i-1列的 “氣泡 ”，較

3、小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對這個 序列處理若干遍。 所謂一遍處理， 就是自底向上檢查一遍這個序列， 元素的順序是否正確。如果發(fā)現(xiàn)兩個相鄰元素的順序不對，即 們的位置。顯然，處理一遍之后， 的元素就浮到了次高位置。在作第二遍處理時， 由于最高位置上的元素已是 以不必檢查。一般地，第 i 遍處理時，不必檢查第 i 高位置以上的元素，因為經(jīng)過前面 遍的處理，它們已正確地排好序。冒泡排序是穩(wěn)定的，算法時間復(fù)雜度是0(n人2)。2.2 選擇排序( Selection Sort)選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將Li.n中最小者與 Li 交換

4、位置。這樣，經(jīng)過 i 遍處理之后，前 i 個記錄的位置已經(jīng)是正確的了。選擇排序是不穩(wěn)定的，算法復(fù)雜度是0(n人2 )。2.3 插入排序 ( Insertion Sort)+h丟兩共需要插入排序的基本思想是，經(jīng)過i-1遍處理后丄1.i-1己排好序。第i遍處理僅將Li插入L1.i-1 的適當位置，使得 L1.i 又是排好序的序列。要達到這個目的，我們可以用順序比較的方 法。首先比較Li和Li-1，如果Li- 1 < Li,貝U L1.i已排好序，第i遍處理就結(jié)束了；否 則交換Li與Li-1的位置，繼續(xù)比較 Li-1和Li-2，直到找到某一個位置j(1 wj琲)i,使得 Lj w Lj+時為止

5、。圖1演示了對4個元素進行插入排序的過程，共需要,(b),(c)三次插入。直接插入排序是穩(wěn)定的，算法時間復(fù)雜度是0(n人2)。2.4 堆排序堆排序是一種樹形選擇排序，在排序過程中，將 An 看成是完全二叉樹的順序存儲結(jié)構(gòu)， 利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。 堆排序是不穩(wěn)定的，算法時間復(fù)雜度 0(nlog n) 。2.5 歸并排序Al.m ，Am+1.h ，設(shè)有兩個有序(升序)序列存儲在同一數(shù)組中相鄰的位置上，不妨設(shè)為 將它們歸并為一個有序數(shù)列，并存儲在Al.h 。O(nlog2n) 。其時間復(fù)雜度無論是在最好情況下還是在最壞情況下均是2.6 快速排序 快速排序

6、是對冒泡排序的一種本質(zhì)改進。 它的基本思想是通過一趟掃描后， 使得排序序列的 長度能大幅度地減少。 在冒泡排序中， 一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長度可能只減少 1?？焖倥判蛲ㄟ^一趟掃描， 就能確保某個數(shù) （以它為基準點吧） 的左邊各數(shù)都比它小， 右邊各數(shù)都比它大。 然后又用同樣的方法處理它左右兩邊的數(shù)，直到O(nlog2n)，最壞 0(n 人2)?；鶞庶c的左右只有一個元素為止。 快速排序是不穩(wěn)定的，最理想情況算法時間復(fù)雜度2.7 希爾排序1個節(jié)點，并且對插入下一個 增量）的數(shù)，使得數(shù)移動時能跨過多 D.L.shell 于 1959年在以他名字命名的排 每組中記錄 在

7、每組中再在直接插入排序算法中，每次插入一個數(shù)，使有序序列只增加 數(shù)沒有提供任何幫助。如果比較相隔較遠距離（稱為 個元素， 則進行一次比較就可能消除多個元素交換。 序算法中實現(xiàn)了這一思想。 算法先將要排序的一組數(shù)按某個增量 d 分成若干組，排序完成。的下標相差d.對每組中全部元素進行排序，然后再用一個較小的增量對它進行， 進行排序。當增量減到 1時，整個要排序的數(shù)被分成一組， 希爾排序是不穩(wěn)定的，其時間復(fù)雜度為0（n人2）。表一 各種排序比較算法： 是解題方案的準確而完整的描述。 通俗地說， 不等于程序，也不等于計算方法，程序的編制不可能優(yōu)于算法的設(shè)計。確定性，（1） 有多義性；算法就是計算機解

8、題的過程。 算法算法中每一步驟都必須有明確定義，不允許有模棱兩可的解釋，不允許有窮性， 可行性， 擁有足夠的情報。算法效率的度量 算法時間復(fù)雜度： 算次數(shù)。算法空間復(fù)雜度：1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念4）算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有限個步驟后終止；算法原則上能夠精確地執(zhí)行；算法復(fù)雜度：算法時間復(fù)雜度和算法空間復(fù)雜度。指執(zhí)行算法所需要的計算工作量。 即算法執(zhí)行過程中所需要的基本運指執(zhí)行這個算法所需要的內(nèi)存空間。排序類別時間復(fù)雜度空間復(fù)雜度穩(wěn)定1插入排序0(n2)1V2希爾排序0(n2)1X3冒泡排序0(n2)1V4選擇排序0(n2)1X5快速排序0(Nlogn)0(logn)X6堆排

9、序0(Nlogn)1X7歸并排序0(Nlogn)0(n)V算法數(shù)據(jù)結(jié)構(gòu)：指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 數(shù)據(jù)結(jié)構(gòu)研究的三個方面：1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；（3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。線性結(jié)構(gòu)的條件，（一個非空數(shù)據(jù)結(jié)構(gòu)）：（1）有且只有一個根結(jié)點；（2）每一個結(jié)點最多有一個前件，也最多有一個后件。非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。1.3線性表及其順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點：（1）線性表中所有元素所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲

10、空間中是按邏輯順序依次存放的。 順序表的運算：查找、插入、刪除。1.4線性鏈表數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點， 簡稱結(jié)點。結(jié)點由兩部分組成：（1）用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。在鏈式存儲結(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。鏈式存儲方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。 線性鏈表的基本運算：查找、插入、刪除。1.5棧和隊列人拱 退桃IHlOfiT%411幻楞慮 holWTT*j! *

11、1top表示棧頂位置。bottom表示棧底。（LIFO ）組織數(shù)據(jù)，棧具有記憶作用。棧：限定在一端進行插入與刪除的線性表。 其允許插入與刪除的一端稱為棧頂，用指針 不允許插入與刪除的另一端稱為棧底，用指針 棧按照 先進后出”（FILO）或 后進先出” 棧的存儲方式有順序存儲和鏈式存儲。棧的基本運算：（1）入棧運算，在棧頂位置插入元素；（2） 退棧運算，刪除元素（取出棧頂元素并賦給一個指定的變量）；（3）讀棧頂元素，將棧頂元素賦給一個指定的變量，此時指針無變化。隊列：指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。ill隊It(:人慎ftorilffflr用 rear隊列是指針

12、指向隊尾，用front指針指向隊頭元素的前一個位置?！?（FIFO）或 后進后出”（LILO）的線性表。先進先出隊列運算：從隊尾插入一個元素從隊頭刪除一個元素（1）入隊運算：（2）退隊運算： 計算循環(huán)隊列的元素個數(shù):尾指針減頭指針”，若為負數(shù)，再加其容量即可。即： 當尾指針-頭指針0時，尾指針-頭指針當尾指針-頭指針0時，尾指針-頭指針+容量 計算棧的個數(shù)：棧底-棧頂+11.6樹與二叉樹1、樹的基本概念樹是一種簡單的非線性結(jié)構(gòu)，其所有元素之間具有明顯的層次特性。在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點。沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)

13、點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。 在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度。來源：考試大所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。RKDn0TA回0F2、二叉樹及其基本性質(zhì)即為二叉樹滿足下列兩個特點的樹，（1）非空二叉樹只有一個根結(jié)點;且分別稱為該結(jié)點的左子樹與右子樹。（2）每一個結(jié)點最多有兩棵子樹,二叉樹基本性質(zhì)： 性質(zhì)1在二叉樹的第k層上，最多有肝（心）個結(jié)點。性質(zhì)2深度為m的二叉樹最多有個2"-'個結(jié)點。性質(zhì)3在任意一棵二叉樹中，度數(shù)為 0的結(jié)點（即葉子結(jié)點）總比度為 2的結(jié)點多一個。性質(zhì)4具有n個結(jié)點的二叉樹，其深度至少為，其中表示取

14、檢瀘的整數(shù)部分3、滿二叉樹與完全二叉樹滿二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。完全二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。歷右子樹，最后訪問根結(jié)點, 子樹，最后訪問根結(jié)點。并且，在遍歷左、右子樹時,En *:I5A二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。二叉樹的遍歷可以分為以下三種：（1）前序遍歷（DLR:若二叉樹為空，則結(jié)束返回。否則：首先訪問根結(jié)點，然后遍 歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時，仍然先訪問根結(jié)點，然后遍歷左子 樹，最后遍歷右子樹。（2）中序遍歷（LDR：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后訪 問根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根 結(jié)點，最后遍歷右子樹。（3）后序遍歷（LRD：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后遍 仍然先遍歷左子樹，然后遍歷右該二叉樹前序遍歷為：該二叉樹中序遍歷為：該二叉樹后序遍歷為：1.7查找技術(shù)查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。 查找結(jié)果：（查找成功：找到；查找不成功：沒找到。）平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。查找