《算法與數(shù)據(jù)結構》PPT課件.ppt

《《算法與數(shù)據(jù)結構》PPT課件.ppt》由會員分享，可在線閱讀，更多相關《《算法與數(shù)據(jù)結構》PPT課件.ppt（100頁珍藏版）》請在裝配圖網上搜索。

第5章算法與數(shù)據(jù)結構 5 1算法與數(shù)據(jù)結構的基本概念 5 1 1算法算法 是一個有窮的指令集 是解決某一問題的運算序列 算法一般應具有以下幾個基本特征 1 可行性 2 確定性 3 有窮性 4 有0個或多個輸入 5 有一個或多個輸出 1 算法的兩個基本要素 1 對數(shù)據(jù)對象的運算和操作1 算術運算 主要有加 減 乘 除等運算 2 邏輯運算 主要有與 或 非等運算 3 關系運算 主要有大于 小于 等于 不等于等運算 4 數(shù)據(jù)傳輸 主要包括賦值 輸入 輸出等操作 2 算法的控制結構算法中各操作之間的執(zhí)行順序稱為算法的控制結構 一個算法一般都可以用順序 選擇 循環(huán)三種基本控制結構組合而成 2 算法設計基本方法 1 列舉法列舉法是針對待解決的問題 列舉所有可能的情況 并用問題中給定的條件來檢驗哪些是必需的 哪些是不需要的 2 歸納法歸納法是從特殊到一般的抽象過程 通過分析少量的特殊情況 找出一般的關系 3 遞歸遞歸分為直接遞歸與間接遞歸兩種 如果一個算法A顯式地調用自己則稱為直接遞歸 如果算法A調用另一個算法B 而算法B又調用算法A 則稱為間接遞歸調用 4 回溯法通過對待解決的問題進行分析 找出一個解決問題的線索 然后根據(jù)這個線索進行探測 若探測成功便可得到問題的解 若探測失敗 就要逐步回退 改換別的路經進一步探測 直到問題得到解答或問題最終無解 5 1 2算法的事前估計 我們可以在算法運行之前對算法進行估計 它可以分為空間復雜度和時間復雜度 1 算法的空間復雜度算法的空間復雜度是對算法所需存儲空間的度量 2 算法的時間復雜度所謂算法的時間復雜度 是指執(zhí)行算法所需要的計算工作量 通常 一個算法所用的時間等于編譯時間加上運行時間 5 1 3數(shù)據(jù)結構 數(shù)據(jù)處理 是指對數(shù)據(jù)集合中的各元素以各種方式進行操作 包括插入 刪除 查找 更改等 也包括對數(shù)據(jù)元素進行分析 數(shù)據(jù)的組織方式不同 通常對它進行處理時的效率也不同 如 對兩個存放相同元素的表進行查找時 一個表中的所有數(shù)據(jù)元素是沒有規(guī)律的 而另外一個表中的元素是經過排序的 則對于前者用順序查詢法進行查找 后者采用折半查詢法進行查詢 可見后者效率較高 數(shù)據(jù)結構 是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合 數(shù)據(jù)元素 在數(shù)據(jù)處理領域中 每一個需要處理的對象都可以抽象成數(shù)據(jù)元素 數(shù)據(jù)元素一般簡稱為元素 作為某種處理 其中的數(shù)據(jù)元素一般具有某種共同特征 例如 描述一年四季的季節(jié)名 春 夏 秋 冬 可以作為季節(jié)的數(shù)據(jù)元素 表示家庭成員的各成員名 父親 兒子 女兒 可以作為家庭成員的數(shù)據(jù)元素 表示數(shù)值的各個數(shù) 35 21 44 70 66 可以作為數(shù)值的數(shù)據(jù)元素 一般情況下 在具有相同特征的數(shù)據(jù)元素集合中 各個數(shù)據(jù)元素之間存在著關系 這種關系反映了該集合中的數(shù)據(jù)元素所固有的一種結構 在數(shù)據(jù)處理領域中 通常把數(shù)據(jù)元素之間這種固有的關系簡單地用前后件關系 或直接前驅與直接后繼關系 來描述 例如 一年四個季節(jié)的順序關系時 則 春 是 夏 的前件 即直接前驅 下同 而 夏 是 春 的后件 即直接后繼 下同 1 數(shù)據(jù)的邏輯結構所謂數(shù)據(jù)的邏輯結構 是指描述數(shù)據(jù)元素之間邏輯關系的數(shù)據(jù)結構 數(shù)據(jù)的邏輯結構由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關系 前后件關系 組成 即一個數(shù)據(jù)結構可以表示成 Data Structure D R 上式中Data Structure表示數(shù)據(jù)結構 D是數(shù)據(jù)元素的集合 R是D上的關系 它反映了D中各數(shù)據(jù)元素之間的前后件關系 例如 設a與b是D中的兩個數(shù)據(jù) 則二元組 a b 表示a是b的前件 b是a的后件 例如 一年四季的數(shù)據(jù)邏輯結構可以表示為 B D R D 春 夏 秋 冬 R 春 夏 夏 秋 秋 冬 2 數(shù)據(jù)的物理結構數(shù)據(jù)的物理結構 數(shù)據(jù)的邏輯結構在計算機中的存儲方式稱為數(shù)據(jù)的物理結構 它包括數(shù)據(jù)元素的存儲方式和關系的存儲方式 一種數(shù)據(jù)的邏輯結構根據(jù)需要可以表示成多種存儲結構 常用的存儲結構有順序 鏈接 索引等存儲結構 采用不同的存儲結構 其數(shù)據(jù)處理的效率是不同的 5 1 4線性結構與非線性結構 空的數(shù)據(jù)結構 如果在一個數(shù)據(jù)結構中一個數(shù)據(jù)元素都沒有 則稱該數(shù)據(jù)結構為空的數(shù)據(jù)結構 在一個空的數(shù)據(jù)結構中插入一個新的元素后就變?yōu)榉强盏臄?shù)據(jù)結構 根據(jù)數(shù)據(jù)元素之間關系的不同特性 一般將數(shù)據(jù)結構分為兩大類型 線性結構與非線性結構 線性結構 如果一個非空的數(shù)據(jù)結構滿足下列兩個條件 1 有且只有一個根結點 2 每一個結點最多有一個前件 也最多有一個后件 則稱該數(shù)據(jù)結構為線性結構 線性結構又稱線性表 如一年四季這個數(shù)據(jù)結構就屬于線性結構 如圖所示 在一個線性結構中插入或刪除任何一個結點后還應是線性結構 非線性結構 如果一個數(shù)據(jù)結構不是線性結構 則稱之為非線性結構 如家庭成員間輩分關系的數(shù)據(jù)結構就屬于非線性結構 如圖所示 顯然 在非線性結構中 各數(shù)據(jù)元素之間的前后件關系要比線性結構復雜 因此 對非線性結構的存儲與處理比線性結構要復雜得多 5 2線性表與線性鏈表 5 2 1線性表1 線性表的基本概念線性表是最簡單且最常用的一種數(shù)據(jù)結構 一個線性表是n個數(shù)據(jù)元素的有限序列 表中的每一個數(shù)據(jù)元素 除了第一個外 有且只有一個前件 除了最后一個外 有且只有一個后件 線性表或是一個空表 或可以表示為 a1 a2 ai an 其中ai i 1 2 n 是屬于數(shù)據(jù)對象的元素 通常也稱其為線性表中的一個結點 如26個英文字母的字母表 A B C Z 是一個長度為26的線性表 其中的數(shù)據(jù)元素是單個字母字符 在稍微復雜的線性表中 一個數(shù)據(jù)元素還可以由若干個數(shù)據(jù)項組成 例如 某班的學生情況登記表是一個復雜的線性表 表中每一個學生的情況就組成了線性表中的每一個元素 每一個數(shù)據(jù)元素包括姓名 學號 性別 年齡和健康狀況5個數(shù)據(jù)項 如表所示 2 線性表的順序存儲結構線性表的順序存儲指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素 線性表的順序存儲結構具有以下兩個基本特點 1 線性表中所有元素所占的存儲空間是連續(xù)的 2 線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的 在線性表的順序存儲結構中 如果線性表中各數(shù)據(jù)元素所占的存儲空間 字節(jié)數(shù) 相等 則要在該線性表中查找某一個元素是很方便的 假設線性表中的第一個數(shù)據(jù)元素的存儲地址為LOC b1 每一個數(shù)據(jù)元素占m個字節(jié) 則線性表中第i個元素bi在計算機存儲空間中的存儲地址為 LOC bi LOC b1 i 1 m 在計算機中的順序存儲結構如圖所示 3 順序表的插入操作在一般情況下 要在第i 1 i n 個元素之前插入一個新元素時 首先要從最后一個 即第n個 元素開始 直到第i個元素之間共n i 1元素依次向后移動一個位置 移動結束后 第i個位置就被空出 然后將新元素插入到第i項 插入結束后 線性表的長度就增加了1 圖 a 為長度6的線性表順序存儲在長度為7的存儲空間中 現(xiàn)在要求在第5個元素之前插入一個新元素25 具體操作步驟為 首先從最后一個元素開始直到第5個元素 將其中的每一個元素均依次往后移動一個位置 然后將新元素25插入到第5個位置 插入一個新元素后 線性表的長度變成了7 如圖 b 所示 這時 為線性表開辟的存儲空間已經滿了 如果再要插入 則會造成稱為 上溢 的錯誤 4 順序表的刪除操作在一般情況下 要刪除第i 1 i n 個元素時 則要從第i 1個元素開始 直到第n個元素之間共n i個元素依次向前移動一個位置 刪除結束后 線性表的長度就減小了1 圖 a 為一個長度為6的線性表順序存儲在長度為7的存儲空間中 現(xiàn)在要求刪除線性表中的第3個元素 即刪除元素5 具體操作步驟為 從第4個元素開始直到最后一個元素 將其中的每一個元素均依次往前移動一個位置 此時 線性表的長度變成了5 如圖 b 所示 5 2 2線性鏈表 線性表的順序存儲結構具有簡單 操作方便等優(yōu)點 但在做插入或刪除操作時 需要移動大量的元素 因此 對于大的線性表 特別是元素變動頻繁的大線性表不宜采用順序存儲結構 而是通常采用鏈式存儲結構 在鏈式存儲結構中 存儲數(shù)據(jù)結構的存儲空間可以不連續(xù) 各數(shù)據(jù)結點的存儲順序與數(shù)據(jù)元素之間的邏輯關系可以不一致 鏈式存儲方式既可用于表示線性結構 也可用于表示非線性結構 假設數(shù)據(jù)結構中的每一個數(shù)據(jù)結點對應于一個存儲單元 這種存儲單元稱為存儲結點 簡稱結點 在鏈式存儲方式中 要求每個結點由兩部分組成 一部分用于存放數(shù)據(jù)元素值 稱為數(shù)據(jù)域 另一部分用于存放指針 稱為指針域 其中指針用于指向該結點的前一個或后一個結點 從而可以表示數(shù)據(jù)元素之間的邏輯關系 我們把線性表的鏈式存儲結構稱為線性鏈表 線性鏈表中存儲結點的結構如圖所示 存儲地址i 在線性鏈表中 用一個專門的指針H 稱為頭指針 指向線性鏈表中第一個數(shù)據(jù)元素的結點 即存放線性表中第一個數(shù)據(jù)元素的存儲結點的序號 從頭指針開始 沿著線性鏈表各結點的指針可以掃描到鏈表中的所有結點 線性表中最后一個元素沒有后件 因此 線性鏈表中最后一個節(jié)點的指針域為空 用 NULL或0表示 表示鏈表終止 當頭指針H NULL 或0 時稱為空表 在某些應用中 對線性鏈表中的每個結點設置兩個指針 一個稱為左指針 用以指向其直接前驅 另一個稱為右指針 用以指向其直接后繼 這樣的線性鏈表稱為雙向鏈表 5 2 3對線性鏈表的基本操作 1 在線性鏈表中查找指定的元素在非空線性鏈表中尋找包含指定元素值x的前一個結點n的操作過程為 從頭指針指向的結點開始向后沿指針進行掃描 直到后面已經沒有結點或下一個結點的數(shù)據(jù)域為x為止 因此 由這種方法找到的結點n有兩種可能 當線性鏈表中存在包含元素x的結點時 則找到的n為首次發(fā)現(xiàn)的包含元素x的前一個結點序號 當線性鏈表中不存在包含元素x的結點時 則找到的n為線性鏈表中的最后一個結點序號 2 線性鏈表的插入線性鏈表的插入操作是指在線性鏈表中的指定位置上插入一個新的元素 為了要在線性鏈表中插入一個新元素 首先要為該元素申請一個新結點 以存儲該元素的值 然后將存放新元素值的結點鏈接到線性鏈表中指定的位置 3 線性鏈表的刪除線性鏈表的刪除是指在線性鏈表中刪除包含指定元素的結點 為了在線性鏈表中刪除包含指定元素的結點 首先要在線性鏈表中找到這個結點 然后將要刪除結點釋放 以便于以后再次利用 4 循環(huán)鏈表及其基本操作循環(huán)鏈表的結構與前面所討論的線性鏈表相比 具有以下兩個特點 1 在循環(huán)鏈表中增加了一個表頭結點 表頭結點的數(shù)據(jù)域可以是任意值 也可以根據(jù)需要來設置 指針域指向線性表的第一個元素的結點 循環(huán)鏈表的頭指針指向表頭結點 2 循環(huán)鏈表中最后一個結點的指針域不為空 而是指向表頭結點 從而在循環(huán)鏈表中 所有結點的指針構成了一個環(huán) 5 3棧和隊列 5 3 1棧1 什么是棧棧實際上是一種特殊的線性表 在這種特殊的線性表中 插入與刪除操作都只在線性表的一端進行 因此 棧是指被限定僅在一端進行插入與刪除操作的線性表 在棧中 允許插入與刪除的一端稱為棧頂 而不允許插入和刪除的另一端稱為棧底 棧是按照 后進先出 的原則組織數(shù)據(jù)的 因此 棧也被稱為 后進先出 的線性表 在程序設計語言中 一般用一維數(shù)組作為隊列的順序存儲空間 通常用指針top來指示棧頂?shù)奈恢?用指針bottom指向棧底 向棧中插入一個元素稱為進棧操作 從棧中刪除一個元素稱為出棧操作 棧頂指針top動態(tài)反映了棧中元素的變化情況 圖是棧的示意圖 棧頂top 棧底bottom 進棧出棧 2 對棧的操作對棧的基本操作有兩種 進棧和出棧 1 進棧操作進棧操作是指在棧頂位置插入一個新元素 其過程是 先將棧頂指針加一 然后將新元素放到棧頂指針指向的位置 當棧頂指針已經指向存儲空間的最后一個位置時 說明棧空間已滿 不能再進棧 這種情況稱為棧 上溢 錯誤 2 出棧操作出棧操作是指取出棧頂元素 其過程是 先將棧頂指針指向的元素賦給一個指定的變量 然后將棧頂指針減1 當棧頂指針為0時 說明?？?不能再出棧 這種情況稱為棧 下溢 錯誤 5 3 2隊列 1 什么是隊列隊列是指只允許在一端進行插入 而在另一端進行刪除的線性表 允許插入的一端稱為隊尾 通常用一個稱為尾指針 rear 的指針指向隊尾元素 允許刪除的一端稱為隊頭 通常也用一個隊頭指針 front 指向隊頭元素的前一個位置 隊列是按照 先進先出 的原則組織數(shù)據(jù)的 因此隊列又稱為 后進后出 的線性表 在隊列中 隊尾指針rear與隊頭指針front共同反映了隊列元素中元素動態(tài)變化的情況 下圖是隊列的示意圖 front rear 向隊列的隊尾插入一個元素稱為進隊操作 從隊列的隊頭刪除一個元素稱為出隊操作 由上圖可知 在隊列的末尾插入一個元素 進隊操作 只涉及隊尾指針rear的變化 而要刪除隊列中的隊頭元素 出隊操作 只涉及隊頭指針front的變化 2 循環(huán)隊列及其操作循環(huán)隊列是一種將順序隊列臆造為一個環(huán)狀的空間的方法 通過把存儲隊列元素的表在邏輯上看成一個環(huán) 將隊列存儲空間的第一個位置作為隊列最后一個位置的下一個位置 供隊列循環(huán)使用 循環(huán)隊列的初始狀態(tài)為空 即rear front m 如圖所示 A 1 n n21 在循環(huán)隊列中 用隊尾指針rear指向隊列中的隊尾元素 用隊頭指針front指向隊頭元素的前一個位置 因此 從隊頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素 循環(huán)隊列主要有兩種基本操作 進隊操作與出隊操作 每進行一次進隊操作 隊尾指針加一 當隊尾指針rear n 1時 則置rear 1 每進行一次出隊操作 隊頭指針就加一 當隊頭指針front n 1時 則置front 1 為了能區(qū)分隊列滿還是隊列空 通常還需增加一個標志s s值的定義如下 由此可以得出隊列空與隊列滿的條件如下 隊列空的條件為s 0 隊列滿的條件為s 1且front rear 5 4樹與二叉樹 5 4 1樹的基本概念樹是一種重要的非線性結構 在這種數(shù)據(jù)結構中 所有數(shù)據(jù)元素之間的關系具有明顯的層次特性 并以分支關系定義了層次結構 下圖是一棵樹的例子 現(xiàn)實世界中有很多可以用樹來表示的例子 例如圖中的樹表示了高校中院系之間的關系 樹中每一個結點只有一個直接前驅 稱作父結點 沒有直接前驅的結點只有一個 稱作樹的根結點 簡稱為樹的根 例如 在上圖中 結點沈陽工業(yè)大學是樹的根結點 每一個結點可以有多個直接后繼 它們都稱為該結點的子女 沒有直接后繼的結點稱為葉子結點 如 圖中的結點理學院 數(shù)學教研室等 除樹根以外的其它結點被劃分為多個互不相交的有限集合 每個集合又是一棵樹 被稱為根的子樹 結點所擁有的子樹的棵樹被稱為該結點的度 如上圖中沈陽工業(yè)大學根節(jié)點的度是4 理學院的度是2 樹中所有結點的度的最大值稱為樹的度 例如 圖中所示的樹的度為4 用樹來表示算術表達式的原則如下 1 算術表達式中的每一個運算符對應于樹中的一個結點 2 運算符的任一運算對象皆為該運算符結點的子樹 3 運算對象中的單個變量均為葉子結點 下圖是用樹結構對表達式a b c d x y z e的表示 注意 表示一個表達式的表達式樹可能并不唯一 5 4 2二叉樹及其基本性質 1 什么是二叉樹二叉樹是另一種樹型結構 當然二叉樹也是一種非線性結構 它的特點是 1 非空二叉樹只有一個根結點 2 每一個結點最多有兩棵子樹 順序不能顛倒 分別稱為該結點的左子樹與右子樹 可見在二叉樹中 不存在度大于2的結點 從而所有子樹也均為二叉樹 另外 在二叉樹中 一個結點可以只有左子樹而沒有右子樹 也可以只有右子樹而沒有左子樹 當一個結點既沒有左子樹也沒有右子樹時 該結點即是葉子結點 下圖是一棵深度為3的二叉樹 2 二叉樹的基本性質性質1在二叉樹的第i層上 最多有 i 1 個結點 性質2深度為m的二叉樹最多有 1個結點 性質3在任意一棵二叉樹中 度為0的結點 即葉子結點 總是比度為2的結點多一個 性質4具有n個結點的二叉樹 其深度至少為 log2n 1 其中 log2n 表示取log2n的整數(shù)部分 2i 1 2m 3 滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹 1 滿二叉樹滿二叉樹是一棵深度為m且有 1個結點的二叉樹 該二叉樹每一層上的所有結點數(shù)都達到最大值 2m 2 完全二叉樹完全二叉樹除最后一層外 每一層上的結點數(shù)均達到最大值 在最后一層上只缺少右邊的若干結點 稱之為完全二叉樹 由滿二叉樹與完全二叉樹的特點可以看出 滿二叉樹也是完全二叉樹 而完全二叉樹一般不是滿二叉樹 5 4 3二叉樹的存儲結構 在計算機中 二叉樹通常采用鏈式存儲結構 用于存儲二叉樹中各元素的存儲結點由兩部分組成 數(shù)據(jù)域與指針域 但在二叉樹中 由于每一個元素可以有兩個子結點 因此 用于存儲二叉樹的存儲結點的指針域有兩個 一個用于指向該結點的左子結點 稱左指針域 另一個用于指向該結點的右子結點 稱為右指針域 由于二叉樹的存儲結構中每一個存儲結點有兩個指針域 因此 二叉樹的鏈式存儲結構也稱為二叉樹鏈表 5 4 4二叉樹的遍歷 二叉樹的遍歷 是指不重復地訪問二叉樹中的所有結點 在遍歷二叉樹的過程中 一般先遍歷左子樹 然后再遍歷右子樹 在先左后右的原則下 根據(jù)訪問根結點的次序 二叉樹的遍歷可以分為三種 前序遍歷 中序遍歷 后序遍歷 1 前序遍歷所謂前序遍歷是指首先訪問根結點 然后遍歷左子樹 最后遍歷右子樹 并且 在遍歷左 右子樹時 仍然先訪問根結點 然后遍歷左子樹 最后遍歷右子樹 下面是二叉樹中序遍歷的簡單描述 若二叉樹為空 則結束返回 否則 1 中序遍歷左子樹 2 訪問根結點 3 中序遍歷右子樹 2 中序遍歷所謂中序遍歷是指首先遍歷左子樹 然后訪問根結點 最后遍歷右子樹 并且 在遍歷左 右子樹時 仍然先遍歷左子樹 然后訪問根結點 最后遍歷右子樹 下面是二叉樹中序遍歷的簡單描述 若二叉樹為空 則結束返回 否則 1 中序遍歷左子樹 2 訪問根結點 3 中序遍歷右子樹 3 后序遍歷所謂后序遍歷是指首先遍歷左子樹 然后遍歷右子樹 最后訪問根結點 并且 在遍歷左 右子樹時 仍然先遍歷左子樹 然后遍歷右子樹 最后訪問根結點 下面是二叉樹后序遍歷的簡單描述 若二叉樹為空 則結束返回 否則 1 后序遍歷左子樹 2 后序遍歷右子樹 3 訪問根結點 5 5查找和排序技術 5 5 1查找技術1 順序查找順序查找的基本方法是 從線性表的第一個元素開始 逐個將線性表中的元素與被查元素進行比較 若相等則表示找到 即查找成功 若線性表中所有的元素都與被查元素進行了比較但都不相等 則表示線性表中沒有要找的元素 即查找失敗 雖然順序查找的效率不高 但在下列兩種情況下只能采用順序查找 1 如果線性表為無序表 則只能用順序查找 2 采用鏈式存儲結構的有序線性表 只能采用順序查找 2 折半查找折半查找只適用于順序存儲的有序表 也就是說 線性表中的元素已經按值非遞減排列 假設有序線性表的長度為m 被查元素值為x 則折半查找的方法如下 將x與線性表的中間項的元素值進行比較 若中間項的值等于x 則查找成功 結束返回 若x小于中間項的值 則在線性表的前半部分用相同的方法進行查找 若x大于中間項的值 則在線性表的后半部分用相同的方法進行查找 這個過程一直進行到查找成功或線性表中沒有這個元素為止 5 5 2排序技術 1 插入排序所謂插入排序 是指將無序序列中的各元素依次插入到已經有序的線性表中 1 簡單插入排序簡單插入排序的基本思想是 將一個新元素插入到已經排好序的有序序列中 從而元素的個數(shù)增一 并成為新的有序序列 在簡單插入排序過程中 由于每一次比較后最多去掉一個逆序 因此 這種排序方法的效率在最壞情況下 需要n n 1 2次比較 2 希爾排序希爾排序的基本思想是 將整個初始序列分割成若干個子序列 對每個子序列分別進行簡單插入排序 最后再對全體元素進行一次簡單插入排序 由此可見 希爾排序也是一種插入排序方法 2 交換排序所謂交換排序是指借助數(shù)據(jù)元素之間的互相交換進行排序的一種方法 冒泡排序法與快速排序法都屬于交換類的排序方法 1 冒泡排序冒泡排序的過程簡單 它的基本思想是通過對相鄰元素進行比較 并根據(jù)比較的結果交換位置 從而逐步由任意序列變?yōu)橛行蛐蛄?具體過程是 首先 將第一個元素和第二元素進行比較 若為逆序 則交換之 接下來對第二個元素和第三個元素進行同樣的操作 并依次類推 直到倒數(shù)第二個元素和最后一個元素為止 其結果是將最大的元素交換到了整個序列的尾部 這個過程叫做第一趟冒泡排序 而第二趟冒泡排序是在除去這個最大元素的子序列中從第一個元素起重復上述過程 直到整個序列變?yōu)橛行驗橹?排序過程中 小元素好比水中氣泡逐漸上浮 而大元素好比大石頭逐漸下沉 冒泡排序故此得名 假設初始序列的長度為n 冒泡排序需要經過n 1趟排序 需要的比較次數(shù)為n n 1 2 下圖是冒泡排序的示意圖 初始序列第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后2618181818918262626915323232915185447915264791532915471554 2 快速排序快速排序法就是一種可以通過一次交換而消除多個逆序的排序方法 其基本思想如下 任取待排序序列中的某個元素對象作為基準 按照該元素值的大小 將整個序列劃分為左右兩個子序列 這個過程稱為分割 左側子序列中所有元素的值都小于或等于基準對象元素的值 右側子序列中所有元素的值都大于基準對象元素的值 基準對象元素則排在這兩個子序列中間 這也是該對象最終應該被安放的位置 接下來分別對這兩個子序列重復進行上述過程 直到所有的對象都排在相應位置上為止 3 選擇排序選擇排序的基本思想是 每一趟排序過程都是在當前位置后面剩下的待排序對象中選出元素值最小的對象 放到當前的位置上 1 簡單選擇排序簡單選擇排序的基本步驟是 1 在一組對象S i S n 1 中選擇元素值最小的對象 2 若它不是這組對象中的第一個對象 則將它與這組對象中的第一個對象對調 3 在剩下的對象中重復執(zhí)行上述兩步 直到只剩下一個對象為止 下圖是這種排序法的示意圖 圖中有方框的元素是剛被選出來的最小元素 2 堆排序堆排序法屬于選擇類的排序方法 堆的定義如下 具有n個元素的序列 a1 a2 an 當且僅當滿足 i 1 2 n 2 時稱之為堆 根據(jù)堆的定義和堆的調整過程 可以得到堆排序的方法如下 1 首先將一個無序序列建成堆 2 然后將堆頂元素與堆中最后一個元素交換 并將除了已經換到最后的那個元素之外的其它元素重新調整為堆 反復做第 2 步 直到所有的元素都完成交換為止 從而得到一個有序序列 堆排序的方法對于規(guī)模較小的線性表并不合適 但對于較大規(guī)模的線性表來說是很有效的