[其它]ch10內(nèi)部排序(已修改)
2024-10-28 17:39 本頁(yè)面
【正文】 1 第 10章 內(nèi)部排序 排序簡(jiǎn)介 插入排序 快速排序 選擇排序 歸并排序 基數(shù)排序 各種排序方法的比較 2 本章知識(shí)點(diǎn)和要求 各種排序方法的特點(diǎn)并能靈活應(yīng)用 （ 掌握 ） 各種方法的排序過程 （ 掌握 ） 各種排序方法的時(shí)間復(fù)雜度分析 （ 掌握 ） 3 排序簡(jiǎn)介 排序 (sorting)又稱 分類 ，意指把一批雜亂無章的數(shù)據(jù)序列重新排列成有序序列。 排序是程序設(shè)計(jì)中一種重要運(yùn)算。在很多領(lǐng)域中有廣泛的應(yīng)用。譬如，在查找時(shí)，若文件的記錄按關(guān)鍵字預(yù)先排好順序，可以采用 折半查找方法提高查找效率。折半查找的平均查找長(zhǎng)度數(shù)量級(jí)為 O(logn)，而順序查找的平均查找長(zhǎng)度數(shù)量級(jí)為 O(n)。又如，建立二叉排序樹的過程本身就是一個(gè)排序過程。日常生活中的各類競(jìng)賽活動(dòng)，如 歌唱大獎(jiǎng)賽 等，還有各種 升學(xué)考試錄取 工作均離不開排序。 4 排序簡(jiǎn)介 關(guān)鍵字 是數(shù)據(jù)元素中的某個(gè)數(shù)據(jù)項(xiàng)。如果某個(gè)數(shù)據(jù)項(xiàng)可以 唯一地 確定一個(gè)數(shù)據(jù)元素，就將其稱 為主關(guān)鍵字 ；否則，稱為次關(guān)鍵字。 排序 將數(shù)據(jù)元素的任意序列 ,重新 調(diào)整為 一個(gè) 按關(guān)鍵字排列有序 的序列 . 如 :有數(shù)據(jù)元素序列 (r1,r2,r3,r4,r5,r6,r7)其對(duì)應(yīng)關(guān)鍵字值為 :(5, 4, 8, 6, 9, 1,21)。按關(guān)鍵字 非遞減排列得新的數(shù)據(jù)元數(shù)排列 (r6,r2,r1,r4,r3,r5,r7)的操作 . 5 排序簡(jiǎn)介 一般情況下 : 假設(shè)含 n個(gè)記錄的序列為 { R1, R2, ? ， Rn } 其相應(yīng)的關(guān)鍵字序列為 { K1, K2, ? ， Kn } 這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系 Kp1≤K p2≤?≤K pn 按此固有關(guān)系將上式記錄序列重新排列為 { Rp1, Rp2, ? ， Rpn }的操作稱作 排序。 6 ? 排序算法的穩(wěn)定性 如果在待排序的記錄序列中有多個(gè)數(shù)據(jù)元素的 關(guān)鍵字值相同 ，經(jīng)過 排序后 ，這些數(shù)據(jù)元素的 相對(duì)次序保持不變 ，則稱這種排序算法是 穩(wěn)定的 ，否則稱之為不穩(wěn)定的。 ? 內(nèi)部排序與外部排序 根據(jù)在排序過程中待排序的所有數(shù)據(jù)元素是否全部被放置在內(nèi)存中，可將排序方法分為內(nèi)部排序和外部排序兩大類。 內(nèi)部排序 是指在排序的整個(gè)過程中，待排序的所有數(shù)據(jù)元素全部被放置在 內(nèi)存中 ； 外部排序 是指由于待排序的數(shù)據(jù)元素個(gè)數(shù)太多，不能同時(shí)放置在內(nèi)存，而需要將一部分?jǐn)?shù)據(jù)元素放置在內(nèi)存，另一部分?jǐn)?shù)據(jù)元素放置在 外設(shè) 上，整個(gè)排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。 7 排序的基本方法 內(nèi)部排序主要有 5種方法： 插入、交換、選擇、歸并和基數(shù)。 一趟 : 在排序過程中，基本動(dòng)作執(zhí)行一次。 排序算法的效率 評(píng)價(jià)排序算法的效率主要有兩點(diǎn)： ? 一是在數(shù)據(jù)量規(guī)模一定的條件下， 算法執(zhí)行所消耗的平均時(shí)間 ，對(duì)于排序操作，時(shí)間主要消耗在 關(guān)鍵字之間的比較和數(shù)據(jù)元素的移動(dòng) 上，因此我們可以認(rèn)為高效率的排序算法應(yīng)該是盡可能少的比較次數(shù)和盡可能少的數(shù)據(jù)元素移動(dòng)次數(shù)； ? 二是 執(zhí)行算法所需要的輔助存儲(chǔ)空間 ，輔助存儲(chǔ)空間是指在數(shù)據(jù)量規(guī)模一定的條件下，除了存放待排序數(shù)據(jù)元素占用的存儲(chǔ)空間之外，執(zhí)行算法所需要的 其他存儲(chǔ)空間 ，理想的空間效率是算法執(zhí)行期間所需要的輔助空間與待排序的數(shù)據(jù)量無關(guān)。 8 10. 2 插 入 排 序 插入排序的思路 不斷地將待排序的數(shù)值插入到有序段 (序列 )中 ，使有序段 (序列 )逐漸擴(kuò)大，直至所有數(shù)值都進(jìn)入有序段中位置。 ① 直接插入排序 ② 折半插入排序 ③ 希爾排序 9 ? 直接插入排序 1. 首先將待排序記錄序列中的 第一個(gè)記錄作為一個(gè)有序段 。 2. 將記錄序列中的第二個(gè)記錄插入到上述有序段中形成由兩個(gè)記錄組成的有序段 。 3. 再將記錄序列中的第三個(gè)記錄插入到這個(gè)有序段中，形成由三個(gè)記錄組成的有序段 。 4. … 依此類推，每一趟都是將一個(gè)記錄插入到前面的有序段中，假設(shè)當(dāng)前欲處理第 i個(gè)記錄，則應(yīng)該將這個(gè)記錄插入到由前 i1個(gè)記錄組成的有序段中，從而形成一個(gè)由 i個(gè)記錄組成的按關(guān)鍵字值排列的有序序列，直到所有記錄都插入到有序段中。 5. 一共需要經(jīng)過 n1趟 就可以將初始序列的 n個(gè)記錄重新排列成按關(guān)鍵字值大小排列的有序序列 。 10 例 49 38 65 97 76 13 27 i=2 38 (38 49) 65 97 76 13 27 i=3 65 (38 49 65) 97 76 13 27 i=4 97 (38 49 65 97) 76 13 27 i=5 76 (38 49 65 76 97) 13 27 i=6 13 (13 38 49 65 76 97) 27 ( ) i=7 (13 38 49 65 76 97) 27 27j j j j j j 97 76 65 49 38 27 (13 27 38 49 65 76 97) 排序結(jié)果： 0 1 2 3 4 5 6 7 11 ?算法評(píng)價(jià) ? 時(shí)間復(fù)雜度 ?若待排序記錄按關(guān)鍵字從小到大排列 (正序 ) ?記錄移動(dòng)次數(shù)： 0 0 1 2 3 4 5 6 7 13 27 38 49 65 76 97 112????nni?關(guān)鍵字比較次數(shù)： 12 ?關(guān)鍵字比較次數(shù)： 2)1)(2(2?????nnini?記錄移動(dòng)次數(shù)： 2)1)(4()1(2??????nnini 0 1 2 3 4 5 6 7 97 76 65 49 38 27 13 ? 若待排序記錄按關(guān)鍵字從大到小排列 (逆序 ) 13 ?若待排序記錄是 隨機(jī)的 ，取平均值 ?關(guān)鍵字比較次數(shù)： ?記錄移動(dòng)次數(shù)： T(n)=O(n178。) ? 空間復(fù)雜度
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1