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