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

1、幾種常見算法的介紹及復(fù)雜度分析1. 基本概念1.1穩(wěn)定排序(stable sort)和非穩(wěn)定排序 穩(wěn)定排序是所有相等的數(shù)經(jīng)過某種排序方法后，仍能保持它們?cè)谂判蛑暗南鄬?duì)次序，。反之，就是非穩(wěn)定的排序。比如：一組數(shù)排序前是a1,a2,a3,a4,a5其中a2=a4,經(jīng)過某種排序后為a1,a2,a4,a3,a5,則我們說這種排序是穩(wěn)定的，因?yàn)閍2排序前在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)整它們的存儲(chǔ)順序， 稱為內(nèi)排序； 在排序過程中， 只有部分?jǐn)?shù)被調(diào)入內(nèi)存， 并借助內(nèi)存調(diào)整數(shù)在外存中的存放順序排序方法稱 為外排序。1.3 算法的時(shí)間復(fù)雜度和空間復(fù)雜度所謂算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。2. 幾種常見算法2.1 冒泡排序( Bubble Sort)冒泡排序方法是最簡(jiǎn)單的排序方法。 這種方法的基本思想是， 將待排序的元素看作是豎著排 列的 “氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對(duì)這個(gè)“氣泡 ”序列處理若干遍。 所謂一遍處理， 就是自底向上檢查一遍這個(gè)序列， 并時(shí)刻注意兩個(gè)

3、相鄰的 元素的順序是否正確。如果發(fā)現(xiàn)兩個(gè)相鄰元素的順序不對(duì)，即 “輕”的元素在下面， 就交換它 們的位置。顯然，處理一遍之后， “最輕”的元素就浮到了最高位置；處理二遍之后， “次輕 ” 的元素就浮到了次高位置。在作第二遍處理時(shí)， 由于最高位置上的元素已是 “最輕 ”元素， 所 以不必檢查。一般地，第 i 遍處理時(shí)，不必檢查第 i 高位置以上的元素，因?yàn)榻?jīng)過前面 i-1 遍的處理，它們已正確地排好序。冒泡排序是穩(wěn)定的，算法時(shí)間復(fù)雜度是0(n A2)。2.2 選擇排序( Selection Sort)選擇排序的基本思想是對(duì)待排序的記錄序列進(jìn)行n-1遍的處理，第i遍處理是將Li.n中最小者與 Li

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

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

6、的一種本質(zhì)改進(jìn)。 它的基本思想是通過一趟掃描后， 使得排序序列的 長(zhǎng)度能大幅度地減少。 在冒泡排序中， 一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長(zhǎng)度可能只減少 1。快速排序通過一趟掃描， 就能確保某個(gè)數(shù) （以它為基準(zhǔn)點(diǎn)吧） 的左邊各數(shù)都比它小， 右邊各數(shù)都比它大。 然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止?？焖倥判蚴遣环€(wěn)定的，最理想情況算法時(shí)間復(fù)雜度O（nlog2n），最壞0（n人2）。2.7 希爾排序在直接插入排序算法中，每次插入一個(gè)數(shù)，使有序序列只增加1個(gè)節(jié)點(diǎn)，并且對(duì)插入下一個(gè)數(shù)沒有提供任何幫助。如果比較相隔較遠(yuǎn)距離（稱為 增量）的數(shù)，使得數(shù)移

7、動(dòng)時(shí)能跨過多 個(gè)元素，則進(jìn)行一次比較就可能消除多個(gè)元素交換。 D.L.shell于 1959年在以他名字命名的排序算法中實(shí)現(xiàn)了這一思想。 算法先將要排序的一組數(shù)按某個(gè)增量 d 分成若干組， 每組中記 錄的下標(biāo)相差 d. 對(duì)每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對(duì)它進(jìn)行，在每組 中再進(jìn)行排序。當(dāng)增量減到 1時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。希爾排序是不穩(wěn)定的，其時(shí)間復(fù)雜度為0（n A2）。表一 各種排序比較排序類別時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定1插入排序O(n2)1V2希爾排序O(n2)1X3冒泡排序O(n2)1V4選擇排序O(n2)1X5快速排序O(Nlogn)O(logn)X6堆排序

8、O(Nlogn)1X7歸并排序O(Nlogn)O(n)V1.1 算法算法： 是解題方案的準(zhǔn)確而完整的描述。 通俗地說，算法就是計(jì)算機(jī)解題的過程。 算法 不等于程序，也不等于計(jì)算方法，程序的編制不可能優(yōu)于算法的設(shè)計(jì)。（1）確定性，算法中每一步驟都必須有明確定義，不允許有模棱兩可的解釋，不允許 有多義性；（2）有窮性，算法必須能在有限的時(shí)間內(nèi)做完，即能在執(zhí)行有限個(gè)步驟后終止；（ 3）可行性，算法原則上能夠精確地執(zhí)行；（4）擁有足夠的情報(bào)。算法效率的度量一算法復(fù)雜度：算法時(shí)間復(fù)雜度和算法空間復(fù)雜度。 算法時(shí)間復(fù)雜度： 指執(zhí)行算法所需要的計(jì)算工作量。 即算法執(zhí)行過程中所需要的基本運(yùn) 算次數(shù)。算法空間復(fù)

9、雜度：指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 數(shù)據(jù)結(jié)構(gòu)：指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；（3）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。線性結(jié)構(gòu)的條件，（一個(gè)非空數(shù)據(jù)結(jié)構(gòu)）：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。1.3線性表及其順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素

10、在存儲(chǔ)空間中是按邏輯順序依次存放的。順序表的運(yùn)算：查找、插入、刪除。1.4線性鏈表數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)。結(jié)點(diǎn)由兩部分組成：（1）用于存儲(chǔ)數(shù)據(jù)元素值，稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個(gè)或后一個(gè)結(jié)點(diǎn)。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的。鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。 線性鏈表的基本運(yùn)算：查找、插入、刪除。1.5棧和隊(duì)列*棧：限定在一端進(jìn)行插入與刪除的線性表。其允許插入與刪除的一

11、端稱為棧頂，用指針top表示棧頂位置。不允許插入與刪除的另一端稱為棧底，用指針bottom表示棧底。棧按照“先進(jìn)后出” （FILO）或“后進(jìn)先出”（LIFO ）組織數(shù)據(jù)，棧具有記憶作用。 棧的存儲(chǔ)方式有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。棧的基本運(yùn)算：（1）入棧運(yùn)算，在棧頂位置插入元素；（2） 退棧運(yùn)算，刪除元素（取出棧頂元素并賦給一個(gè)指定的變量）；（3）讀棧頂元素，將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無(wú)變化。隊(duì)列：指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。UI 隊(duì) -a u c b k r . 人趴t.T konirer用rear指針指向隊(duì)尾，用front指針指向隊(duì)頭元素的前一個(gè)位

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

13、結(jié)點(diǎn)。在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。來(lái)源：考試大所有結(jié)點(diǎn)中最大的度稱為樹的度。樹的最大層次稱為樹的深度。2、二叉樹及其基本性質(zhì)滿足下列兩個(gè)特點(diǎn)的樹，即為二叉樹（1）非空二叉樹只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。二叉樹基本性質(zhì)：性質(zhì)1在二叉樹的第k層上，最多有 燈心 0個(gè)結(jié)點(diǎn)。性質(zhì)2深度為m的二叉樹最多有個(gè)丄 1個(gè)結(jié)點(diǎn)。性質(zhì)3在任意一棵二叉樹中，度數(shù)為 0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總比度為 2的結(jié)點(diǎn)多一個(gè)。性質(zhì)4具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為【嗨M十1 ,其中卩啤瀘表示取 噸瀘的整數(shù)部分3、滿二叉樹與完全二叉樹滿二叉樹：除最后一

14、層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。完全二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。二叉樹的遍歷可以分為以下三種：（1）前序遍歷（DLR:若二叉樹為空，則結(jié)束返回。否則：首先訪問根結(jié)點(diǎn)，然后遍 歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子 樹，最后遍歷右子樹。（2）中序遍歷（LDR：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后訪 問根結(jié)點(diǎn)，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根 結(jié)點(diǎn)，最后遍歷右子樹。（3）后序遍歷（LRD：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后遍 歷右子樹，最后訪問根結(jié)點(diǎn)，并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右 子樹，最后訪問根結(jié)點(diǎn)。UH該二叉樹前序遍歷為：F C A D B E G H P該二叉樹中序遍歷為：A C B D F E H G P該二叉樹后序遍歷為：A B D C H P G E F1.7查找技術(shù)查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。查找結(jié)果：（查找成功：找到；查找不成功：沒找到。）平均查找長(zhǎng)度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。