數據結構第十章ppt課件(編輯修改稿)
2025-05-31 23:32 本頁面
【文章內容簡介】 13 4938 27 65 49* 97 55 76 04 27 38 65 49* 975513 55 7604 5527 04 2704 49 49* 76 38 65 97 55 13 27 04 49 49* 38 76 65 97 13 27 04 49* 76 97 算法分析： 開始時 dk 的值較大，子序列中的對象較少，排序速度較快；隨著排序進展， dk 值逐漸變小，子序列中對象個數逐漸變多，由于前面工作的基礎，大多數對象已基本有序，所以排序速度仍然很快。 r[i] 22 空間效率： O（ 1） —— 因為僅占用 1個緩沖單元 算法的穩(wěn)定性： 不穩(wěn)定 —— 因為 49*排序后卻到了 49的前面 O(）～ O（ ） —— 經驗公式 23 寫出采用 SHELL排序算法排序的每一趟的結果，并標出數據移動情況。 （ 125， 11， 22， 34， 15， 44， 76， 100， 8， 14， 20，2， 5） 交換排序 24 兩兩比較待排序記錄的關鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序為止。 交換排序的主要算法有： 1) 冒泡排序 2) 快速排序 交換排序的基本思想是： 25 基本思路： 每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。 優(yōu)點： 每趟結束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結束排序。 前提： 順序存儲結構 例： 關鍵字序列 T=(21， 25， 49， 25*， 16， 08），請寫出冒泡排序的具體實現過程。 21， 25， 49， 25*， 16， 08 21， 25， 25*， 16， 08 ， 49 21， 25， 16， 08 ， 25*， 49 21， 16， 08 ， 25， 25*， 49 16， 08 ， 21， 25， 25*， 49 08， 16， 21， 25， 25*， 49 初態(tài)： 第 1趟 第 2趟 第 3趟 第 4趟 第 5趟 冒泡排序的算法分析 26 時間效率： O（ n2) — 因為要考慮最壞情況 空間效率： O（ 1） — 只在交換時用到一個緩沖單元 穩(wěn) 定 性： 穩(wěn)定 — 25和 25*在排序前后的次序未改變 27 從待排序列中任取一個元素 (例如取第一個 ) 作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個子表；然后再對各子表重新選擇中心元素并依此規(guī)則調整，直到每個子表的元素只剩一個。此時便為有序序列了。 基本思想： 優(yōu)點： 因為每趟可以確定不止一個元素的位置，而且呈指數增加，所以特別快！ 前提： 順序存儲結構 28 ? 一趟快速排序采用從兩頭向中間掃描的辦法。 ? 假設原始數據已存于一個一維數組 r中，具體的做法是：設兩個指示器 i和 j，初始時 i指向數組中的第一個數據， j指向最末一個數據。 i先不動使 j逐步前移，每次對二者所指的數據進行比較，當遇到 r[i]大于 r[j]的情況時，就將二者對調位置；然后令 j固定使 i逐步后移做數據比較，當遇到r[i]大于 r[j] 時，又進行位置對調；然后又是 i不動使 j前移作數據比較； …… ； ? 如此反復進行，直至 i與 j兩者相遇為止。 具體過程 2022/6/1 29 25*跑到了前面， 不穩(wěn)定 ！ Low=high=3， 本趟停止，將支點定位并返回位置信息 r[i] 0 1 2 3 4 5 6 初態(tài) 21 25 49 25* 16 08 第 1趟 high low 21 08 25 16 49 25* 21pivotkey=21 08 2516 49( 08 ， 16 ） 21 （ 25* ， 49， 25 ） low low high high high 30 ( )， 設以首元素為樞軸中心 21， 25， 49， 25*， 16， 08 初態(tài)： 第 1趟： 第 2趟： 第 3趟： 08， 16， 21， 25， 25*， (49) 21 16， 08 ， ( ) 25， 25*， 49 (08)， 16， 21， 25， (25*， 49) 31 原始序列： 256， 301， 751， 129， 937， 863， 742， 694， 076， 438 第 1趟 第 2趟 第 3趟 第 4趟 256， 301， 751， 129， 937， 863， 742， 694， 076， 438 076， 129， 256， 751， 937， 863， 742， 694， 301， 438 要求模擬算法實現步驟 256 076 301 129 751 256 ， ， ， 438， 301， 694， ， ， 863， 937751 076， 129， 256， 438， 301， 694， 742， 751， 863， 937 ， ， ， 301， ， ， ， ， ，438 076， 129， 256， 301， 438， 694， 742， 751， 863， 937 32
教學課件相關推薦
鄂ICP備17016276號-1