[其它]ch10內(nèi)部排序-在線瀏覽
2024-12-03 17:39本頁面
【正文】 排序樹的過程本身就是一個排序過程。 4 排序簡介 關(guān)鍵字 是數(shù)據(jù)元素中的某個數(shù)據(jù)項。 排序 將數(shù)據(jù)元素的任意序列 ,重新 調(diào)整為 一個 按關(guān)鍵字排列有序 的序列 . 如 :有數(shù)據(jù)元素序列 (r1,r2,r3,r4,r5,r6,r7)其對應(yīng)關(guān)鍵字值為 :(5, 4, 8, 6, 9, 1,21)。 6 ? 排序算法的穩(wěn)定性 如果在待排序的記錄序列中有多個數(shù)據(jù)元素的 關(guān)鍵字值相同 ，經(jīng)過 排序后 ，這些數(shù)據(jù)元素的 相對次序保持不變 ，則稱這種排序算法是 穩(wěn)定的 ，否則稱之為不穩(wěn)定的。 內(nèi)部排序 是指在排序的整個過程中，待排序的所有數(shù)據(jù)元素全部被放置在 內(nèi)存中 ； 外部排序 是指由于待排序的數(shù)據(jù)元素個數(shù)太多，不能同時放置在內(nèi)存，而需要將一部分?jǐn)?shù)據(jù)元素放置在內(nèi)存，另一部分?jǐn)?shù)據(jù)元素放置在 外設(shè) 上，整個排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。 一趟 : 在排序過程中，基本動作執(zhí)行一次。 8 10. 2 插 入 排 序 插入排序的思路 不斷地將待排序的數(shù)值插入到有序段 (序列 )中 ，使有序段 (序列 )逐漸擴(kuò)大，直至所有數(shù)值都進(jìn)入有序段中位置。 2. 將記錄序列中的第二個記錄插入到上述有序段中形成由兩個記錄組成的有序段 。 4. … 依此類推，每一趟都是將一個記錄插入到前面的有序段中，假設(shè)當(dāng)前欲處理第 i個記錄，則應(yīng)該將這個記錄插入到由前 i1個記錄組成的有序段中，從而形成一個由 i個記錄組成的按關(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 ?算法評價 ? 時間復(fù)雜度 ?若待排序記錄按關(guān)鍵字從小到大排列 (正序 ) ?記錄移動次數(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?記錄移動次數(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ù)： ?記錄移動次數(shù)： T(n)=O(n178。) ?空間復(fù)雜度： S(n)=O(1) 16 ? 希爾排序 (縮小增量法 Shell’s Sort) 排序過程 ：先取一個正整數(shù) d1n， 把所有 相隔 d1的記錄放一組， 組內(nèi) 進(jìn)行 直接插入排序 ；然后取 d2d1， 重復(fù)上述分組和排序操作；直至 di=1， 即所有記錄放進(jìn)一個組中排序為止 17 取 d3=1 三趟分組： 13 27 48 55 4 49 38 65 97 76 三趟排序： 4 13 27 38 48 49 55 65 76 97 例 初始： 49 38 65 97 76 13 27 48 55 4 一趟排序： 13 27 48 55 4 49 38 65 97 76 二趟排序： 13 4 48 38 27 49 55 65 97 76 取 d1=5 一趟分組： 49 38 65 97 76 13 27 48 55 4 取 d2=3 二趟分組： 13 27 48 55 4 49 38 65 97 76 18 ? 算法描述 例 49 38 65 97 76 13 27 48 55 4 define T 3 int d[]={5,3,1}。更小，而 T(n)=O(n178。其中 di =di1/2, d0=7 21 朝著最終排序序列相反的方向移動 ， 從而認(rèn)為該排序算法是不穩(wěn)定的 ， 這種說法對嗎 ？ 為什么 ？ ：這種說法不對 。 對 4， 3， 2， 1起泡排序就可否定本題結(jié)論 。) 25 ?快速排序 ?快速排序由霍爾 (Hoare)提出，它是一種對冒泡排序的改進(jìn)。 ?基本思想：通過 一趟 排序，將 待排序記錄 分割成獨(dú)立的 兩部分 ，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄進(jìn)行排序，以達(dá)到整個序列有序 26 ?排序過程 ：對 r[s……t] 中記錄進(jìn)行一趟快速排序，附設(shè)兩個指針 i和 j， 設(shè)樞軸記錄 rp=r[s]， x= 1. 初始時令 i=s,j=t 2. 首先從 j所指位置向前搜索第一個關(guān)鍵字小于 x的記錄，并和 rp交換 3. 再從 i所指位置起向后搜索，找到第一個關(guān)鍵字大于 x的記錄，和 rp交換 4. 重復(fù)上述兩步，直至 i==j為止 5. 再分別對 兩個子序列 進(jìn)行快速排序，直到每個子序列只含有 一個記錄 為止 27 例 初始關(guān)鍵字： 49 38 65 97 76 13 27
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1